提高滑块解算器的性能

Question

作为练习，我决定编写一个滑动拼图解算器(比如8个拼图或15个拼图)。现在，解决方案就在那里，它正在工作，但我现在面临的问题是运行时。我想请求一些帮助来优化解决方案(如果可能的话)。我很有兴趣看看可以采取哪些步骤来提高他们的Haskell程序的性能。

我的实现可以在这里找到：https://gist.github.com/anonymous/166d8a3323a3f96eab04

示例输入文件：

4
5  4  3  8 
9  2  6  1 
0 13 14  7 
15 11 10 12

如果您在分析器下运行它，您将看到我们生成的数据量约为9 9Gb。“有问题的”函数是manhattan和boardDistance。我现在不知道如何处理这些函数来优化它们(如果可能的话)。寻求您的帮助！

引用“有问题的”文章：

-- | Manhattan distance of a tile at vector index on a board with dimensions n x n
manhattan :: Int -> Int -> Int -> Int
manhattan tile n index = if tile == 0 then 0 else rowDistance + columnDistance
    where
        (row, column) = v2m n index -- convert vector index to matrix index
        rowDistance = abs (row - ((tile - 1) `div` n))
        columnDistance = abs (column - ((tile - 1) `mod` n))

-- | Manhattan distance of the entire board
boardDistance :: BoardDimension -> Board -> Int
boardDistance n currentBoard = sum $ map (\index -> manhattan (currentBoard ! index) n index) [0..n*n-1]

Answer 1

看看这种解决方案的类型，我怀疑你的很多性能损失都来自于免费monad的糟糕性能(Maybe是一个免费monad)。这是codensity transformation获胜的一个最好的例子。或者，您可以使用专为组合搜索而设计的monad，如logict。