[Haskell-cafe] Code Review: Sudoku solver
daniel.is.fischer at web.de
Fri Apr 7 19:06:03 EDT 2006
Am Freitag, 7. April 2006 01:50 schrieben Sie:
> On Apr 6, 2006, at 6:05 PM, Daniel Fischer wrote:
> > I've also written a version using David F. Place's EnumSet instead
> > of [Int],
> > that takes less MUT time, but more GC time, so is slower on the
> > 36,628 test,
> > but faster for a single puzzle.
> That's a curious result. Did you compile with optimization? It
I considered that curious, too.
Everything was compiled with -O2 (does -O3 give better results?, would adding
-optc-On improve performance? I'll try).
What makes it even weirder is that the EnumSet-version does indeed allocate
fewer bytes and performs fewer garbage collections (small difference,
But I got consistent results, when running on a large number of puzzles, the
list-version's faster gc'ing led to shorter overall run times.
The same held when compiled with -O3 -optc-O3, however, I've been stupid,
my excuse is that I was ill this week, the list version spent 46.5% gc'ing and
the set version 53.5%, which is not really cricket, so today I used -AxM,
x <- [10,16,32,64], all reducing GC time to reasonable 0.5 - 2%. That, plus a
few polishings, reduced the running time to about 16 minutes for EnumSet, a
little more for lists.
But, lo and behold, I also tried how plai Array fared in comparison to
DiffArray and ... reduced the running time to under ten minutes (a little
above for the list version), 5% GC time without -AxM, 1.2% with -A8M.
And I thought, DiffArrays were supposed to be fast!
> should compile into primitive bit-twiddling operations and do no
> allocating at all. I'd be curious to see how fast my solver works on
Well, since I've wrapped the sets in the Entry datatype, I wouldn't expect
that, switching from Poss (singleton k) to Def k costs.
I tried making Board a DiffArray (Int,Int) (Set Int), but then I had the
problem that either I lost the information gained by placing & forbidding for
those positions where the number of possibilities dropped to one by
inference, or had to scan the grid and re-place every now and then, both
resulting in poor performance.
> the 36,628 test. I'm afraid to run my ancient limping powerbook in
> such a tight loop for that long. It gets too hot!
> If you'd find it amusing to give it a whirl, I'd love to know the
I ran your incrsud on the first fifteen 17-hint puzzles, took over 20s, so I
decided against the full 36,628 test. Extrapolation makes me believe it'd
take thirteen to fourteen hours.
The really big thing is to include the "if there is only one place to put a
number in a row/column/cell, then put it there" inference step. Further
inference has smaller impact (but the group-inference bought me a 20%
speedup, which isn't bad, is it?).
But using Array instead of DiffArray gave almost 40%, that's impressive.
Attached is the fastest version I have, oddly, compiled with -O2 it's faster
than with -O3 -optc-O3 (on my computer), how come?
setUni +RTS -A8M -sstderr
99,859,933,904 bytes allocated in the heap
104,713,900 bytes copied during GC
150,260 bytes maximum residency (72 sample(s))
11558 collections in generation 0 ( 6.83s)
72 collections in generation 1 ( 0.16s)
13 Mb total memory in use
INIT time 0.00s ( 0.00s elapsed)
MUT time 554.68s (568.29s elapsed)
GC time 6.99s ( 7.22s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 561.67s (575.51s elapsed)
%GC time 1.2% (1.3% elapsed)
Alloc rate 180,031,610 bytes per MUT second
Productivity 98.8% of total user, 96.4% of total elapsed
an average of 0.015s per 17-hint puzzle, cool!
> David F. Place
> mailto:d at vidplace.com
"In My Egotistical Opinion, most people's C programs should be
indented six feet downward and covered with dirt."
-- Blair P. Houghton
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 13960 bytes
Desc: not available
Url : http://www.haskell.org//pipermail/haskell-cafe/attachments/20060408/25180f2d/SudokuSet.bin
More information about the Haskell-Cafe