7

私はnqueens問題の2つのバージョンを書きました、そしてそれらは同様の効率を持つべきだと思いますが、そうではありません。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 88またはnqueens288を呼び出して、サイズ8のボードを評価することで、それらを評価できます。

nqueens2は非常に効率的に機能しますが、nqueens1にはパフォーマンスの問題があります。再帰呼び出し（nqueens n（k-1））が複数回評価されているためだと思います。Haskellsの遅延評価についての私の理解から、これは当てはまらないはずです。

この振る舞いを理解するのを手伝ってください。

前もって感謝します。

4

1 に答える 1

10

はい、再帰呼び出しは複数回評価されます。具体的には、 の値ごとに 1 回評価され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 に答える