Efficiency of using long integers to hold bitmaps

[Jack Diederich]

On Wed, Jul 13, 2005 at 03:24:48AM +1000, Jeff Melvaine wrote:
> Bengt,
> 
> Thanks for your informative reply, further comments interleaved.
> 
> "Bengt Richter" <bokr at oz.net> wrote in message 
> news:42d165d0.311819733 at news.oz.net...
> > On Mon, 11 Jul 2005 02:37:21 +1000, "Jeff Melvaine" 
> > <jeffm at rivernet.com.au> wrote:
> >
> >>I note that I can write expressions like "1 << 100" and the result is 
> >>stored
> >>as a long integer, which means it is stored as an integer of arbitrary
> >>length.  I may need to use a large number of these, and am interested to
> >>know whether the storage efficiency of long integers is in danger of
> >>breaking my code if I use too many.  Would I do better to write a class 
> >>that
> >>defines bitwise operations on arrays of integers, each integer being 
> >>assumed
> >>to contain at most 32 bits?  I cannot find information in the Python 
> >>manuals
> >>for 2.4.1 that would allow me to resolve this question; perhaps the
> >>intention is that programmers should not rely on implementation details.
> >>
> >>Thanks in advance,
> >>
> > Sounds like a possible^H^H^H^H^H^H^H^Hprobable premature optimization 
> > worry ;-)
> >
> I'm writing a Sudoku solver of generic order.  The object is not to make it 
> half a millisecond faster than the guy next door's solver, but I'd like it 
> to be able to do a bit more than just the daily newspaper puzzle, e.g. 
> search for uniquely solvable puzzles with minimal numbers of clues. 
> NP-completeness will put a lid on things sooner or later, but I'd like to 
> get as far as possible before that happens.
> 

I would recommend making a hand-written C extension that does the heavy
lifting - but only in the tiny corner you need it to.  I've done this for
the ICFP[1] competition the last few years.  It is a time-limited competition
so the priorities are getting a pure-python program up and running to 
understand the problem and then making the slow parts go really fast so
you can try as many full games as possible to try out as many new strategies
as possible.

Typically this means just the "game board" representation is done in C.
You'll want the heuristics to be done in python in order to try out variations
easily.  For Sudoku the board implementation will likely have C functions
for copy(), valid() (raise ValueError), and something to return a list
of obviously legal values for a coordinate.  Passing coord tuples in and
list & dictionaries out has worked well for me (easy to use in the python
part of the program).

I keep C modules out of production code unless absolutely necessary, but
I have no qualms about using it in toy/hobby problems, especially because
the C code stays at a manageable few hundred lines for toy problems.
If you aren't much of a C guy check out pyrex[2].  In my darker days I did
C++ for a living so I much prefer writing modules by hand; python makes it
easy to do and it is faster, less buggy, and easier to debug.

-jackdied

[1] http://performancedrivers.com/icfp2002/
    http://performancedrivers.com/icfp2004/
    (other years I botched it badly enough I didn't make a webpage)
    http://performancedrivers.com/icfp2002/icfp_module.c
    http://performancedrivers.com/icfp2002/icfpBoard.c

[2] http://nz.cosc.canterbury.ac.nz/~greg/python/Pyrex/