On Wed, Jul 13, 2005 at 03:24:48AM +1000, Jeff Melvaine wrote: > Bengt, > > Thanks for your informative reply, further comments interleaved. > > "Bengt Richter" <[EMAIL PROTECTED]> wrote in message > news:[EMAIL PROTECTED] > > On Mon, 11 Jul 2005 02:37:21 +1000, "Jeff Melvaine" > > <[EMAIL PROTECTED]> 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/ -- http://mail.python.org/mailman/listinfo/python-list
