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, though). 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 result.
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 True 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! Cheers, Daniel
-------------------------------- David F. Place mailto:d@vidplace.com
-- "In My Egotistical Opinion, most people's C programs should be indented six feet downward and covered with dirt." -- Blair P. Houghton