7

我已经编写了两个版本的 nqueens 问题，我认为它们应该具有相似的效率，但事实并非如此。我认为这是由于 Haskell 的懒惰评估行为。有人可以解释一下它在以下示例中的工作原理吗，

nqueens1 n 1 = [[i] | i <- [1..n]]
nqueens1 n k = [ i:q | i <- [1..n], q <- (nqueens1 n (k - 1)), isSafe i q k]

isSafe i q n  = isSafeHelper i (zip q [(n-1),(n-2)..1]) 
         where isSafeHelper i []  = True
               isSafeHelper i (x:xs) = (i /= fst x) && abs(i - (fst x)) /= abs(n - (snd x)) && 
                                       isSafeHelper i xs
nqueens2 n 1 = [[i] | i <- [1..n]]
nqueens2 n k = [ i:q | i <- [1..n], q <- boards, isSafe i q k]
           where boards = nqueens2  n (k-1)

您可以通过调用 nqueens1 8 8 或 nqueens2 8 8 来评估它们，以评估它是否适合 8 号板。

虽然 nqueens2 的工作效率很高，但 nqueens1 存在性能问题。我相信这是因为递归调用 (nqueens n (k-1)) 被多次评估。根据我对 Haskells 懒惰评估的理解，情况并非如此。

请帮助我理解这种行为。

提前致谢。

4

1 回答 1

10

是的，递归调用被多次评估。具体来说，它对 的每个值进行一次评估i。

如果你想避免这种情况，你可以重新排列生成器，使q <-部分出现在i <-部分之前：

[ i:q | q <- nqueens2 n (k - 1), i <- [1..n], isSafe i q k]

但是，这将改变结果的顺序。如果这不可接受，您可以使用let一次计算递归调用的结果，然后像这样使用它：

[ i:q | let rec = nqueens2 n (k - 1), i <- [1..n], q <- rec, isSafe i q k]
于 2012-07-01T13:35:57.157 回答