[Haskell-cafe] Performance of Knight's Tour

[Daniel Fischer]

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.