0

プロジェクト オイラーの 15 番目の問題、格子パス ( http://projecteuler.net/problem=15 )を解決しようとしています。

私の最初の試みは、問題を 1 行ずつ解決し、最後の行の最後の要素を取得することでした。

number_of_ways_new_line last_line = foldl calculate_values [] last_line
                                    where
                                      calculate_values lst x = lst ++ [(if length lst > 0 then (last lst) + x else head last_line)]

count_ways x = foldl (\ lst _ -> number_of_ways_new_line lst) (take x [1,1..]) [1..x-1]

result_15 = last $ count_ways 21

これは機能し、高速ですが、本当に醜いと思います。そこで、しばらく考えて、再帰を使用して問題を解決する、より慣用的な関数を思いつきました (これが間違っている場合は修正してください)。

lattice :: Int -> Int -> Int
lattice 0 0 = 1
lattice x 0 = lattice (x-1) 0
lattice 0 y = lattice (y-1) 0
lattice x y
  | x >= y    = (lattice (x-1) y) + (lattice x (y-1))
  | otherwise = (lattice y (x-1)) + (lattice (y-1) x)

これは短い数値には適していますが、まったくスケーリングしません。lattice 1 2とlattice 2 1が常に同じになるという事実を利用して、少し最適化しました。なぜこれはとても遅いのですか？Haskell は以前の結果をメモ化していないので、lattice 2 1呼び出されるたびに古い結果が記憶されますか?

4

2 に答える 2

2

この問題は、再帰関係を閉じた形に操作することで数学的に解決できますが、もっと興味深い問題、メモ化に焦点を当てます。

最初に使用できますData.Array（これは怠惰なものです）

 import Data.Array as A

 lattice x y = array ((0, 0), (x, y)) m ! (x, y)
   where m = [(,) (x, y) (lattice' x y) | x <- [0..x], y <- [0..y]
         lattice' 0 0  = 1
         lattice' x 0 = lattice (x-1) 0
         lattice' 0 y = lattice (y-1) 0
         lattice' x y | x >= y    = (lattice (x-1) y) + (lattice x (y-1))
                      | otherwise = (lattice y (x-1)) + (lattice (y-1) x)

現在、これらの繰り返しはマップを通過しますが、マップは遅延しているため、マップエントリが評価されると、サンクは単純な値に変更され、一度だけ計算されるようになります。

memo-combinators素晴らしい図書館も利用できます。

 import Data.MemoCombinators as M
 lattice = memo2 M.integral M.integral lattice'
   where lattice' 0 0 = 1
         lattice' x 0 = lattice (x-1) 0
         lattice' 0 y = lattice (y-1) 0
         lattice' x y | x >= y    = lattice (x-1) y + lattice x (y-1)
                      | otherwise = lattice y (x-1) + lattice (y-1) x
于 2013-10-13T13:28:06.020 に答える
1

同時に複数の再帰に依存しているため、この答えは確かに遅いです。

機能を調べてみましょうlattice。それは何をするためのものか？2 つの関数の合計lattice、別のlattice関数、または 1 のいずれかを返します。

では、例を実行してみましょう: lattice 2 2.
これは に等しいlattice 1 2 + lattice 2 1。
これは に等しいlattice 0 2 + lattice 1 1 + lattice 1 1 + lattice 2 0。
これは...

問題を理解していますか？コードに定数を乗算したり追加したりするケースは 1 つもありません。これは、関数全体が次のように要約されることを意味します。

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + ... + 1

この合計が最終結果です。ただし、上記の合計のすべての 1 は、1 つまたは複数の関数呼び出しの結果です。そのため、関数は結果よりも頻繁に評価されます。

ここでlattice 20 20、約 1,500 億ドルの収益があると考えてください (これは概算なので、あまりネタバレしません)。

これは、関数が約 150 000 000 000 回評価されることを意味します。

うわぁ。

この間違いを気にしないでください。私はかつて言った：

fibbonaci x = fibbonaci (x-1) + fibbonaci (x-2)

なぜこれが悪い考えなのかを理解することをお勧めします。

PS彼らが求めなかったことをうれしく思いますlattice 40 40。これには 10^23 回以上の関数呼び出し、または少なくとも 300 万年かかります。

関数呼び出しの量は減少しませんが、関数呼び出しごとの時間は減少するため、一方の側のみを計算して加速を PPS すると、実行が遅くなるだけです。

免責事項: これは、私が今まで見た Haskell コードの最初の部分です。

于 2015-01-22T17:04:39.860 に答える