Am Montag 01 März 2010 17:07:46 schrieb Artyom Kazak:
Hi! I'm learning Haskell, and now I'm trying to make framework for solving searching problems, such as Knight's Tour. For small boards it answers instantly. For 7x8 board - 23 seconds. For 8x8 board - more than 30 minutes (it hasn't finished yet). Where is the root of the evil?
In the algorithm. You investigate far too many dead ends. Since for larger boards, the number of dead ends increases fast, larger boards take much much longer. With one little change, I get $ echo "59 59" | ./knights +RTS -s > /dev/null ./knights +RTS -s 68,243,720 bytes allocated in the heap 5,914,848 bytes copied during GC 36,436,628 bytes maximum residency (6 sample(s)) 8,486,604 bytes maximum slop 58 MB total memory in use (1 MB lost due to fragmentation) Generation 0: 109 collections, 0 parallel, 0.03s, 0.03s elapsed Generation 1: 6 collections, 0 parallel, 0.02s, 0.02s elapsed INIT time 0.00s ( 0.00s elapsed) MUT time 0.05s ( 0.10s elapsed) GC time 0.05s ( 0.05s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 0.10s ( 0.15s elapsed) %GC time 50.0% (32.2% elapsed) Alloc rate 1,421,744,166 bytes per MUT second Productivity 50.0% of total user, 31.3% of total elapsed For a reason I don't understand, if the second dimension is 60 and the first is > 18, it takes much longer, $ echo "19 60" | ./knights +RTS -A8M -H64M-s > /dev/null ./knights +RTS -A8M -H64M -s 2,374,198,988 bytes allocated in the heap 1,873,412 bytes copied during GC 5,611,132 bytes maximum residency (2 sample(s)) 4,934,352 bytes maximum slop 70 MB total memory in use (1 MB lost due to fragmentation) Generation 0: 281 collections, 0 parallel, 0.15s, 0.15s elapsed Generation 1: 2 collections, 0 parallel, 0.00s, 0.01s elapsed INIT time 0.00s ( 0.00s elapsed) MUT time 1.17s ( 1.21s elapsed) GC time 0.15s ( 0.16s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 1.32s ( 1.37s elapsed) %GC time 11.2% (11.6% elapsed) Alloc rate 2,032,579,317 bytes per MUT second Productivity 88.8% of total user, 85.5% of total elapsed The magic change: e ((x, y), arr) p = [(t, arr // [(t, p)]) | t <- changes] where legit ps = [t | t <- allTurns ! ps, arr!t == 0] changes = map snd $ sort [(length $ legit t, t) | t <- allTurns ! (x, y), arr ! t == 0] investigate squares with fewer options first.