5

私はいくつかのHaskellを学び、プロジェクトオイラーの問題を進めてきました。私はオイラー問題（私は喜んでブルートフォースすることができます、または他の言語でそれを行うことができます）への答えについては本当に気になりませんが、方法です。

私は妥当な時間内に問題15を実行することに固執しています。20x20グリッドの左上から右下までの非バックトラックルートの数を要求します。ここにリンク

関数をメモ化（sp？）するというアイデアは当然だと思いますが、その方法がよくわかりません。私はグーグルで検索し、Haskell Cafeでこれに出くわしました。これは、素朴に適応しようとしましたが、最終的には次のようになりました。

memRoute :: (Int,Int) -> Int
memRoute (x,y) = fromJust $ lookup (x,y) $ map (\t -> (t,route t)) [(x,y) | x <- [0..20], y <- [0..20]]

route (0,0) = 0
route (_,0) = 1
route (0,_) = 1
route (x,y) = memRoute (x-1,y) + memRoute (x,y-1)

これは見栄えが悪く、パフォーマンスがひどいです（ナイーブバージョンよりもはるかに遅い）。問題は、Haskellのメモ化がどのように機能するのか本当に理解していないことです。

例として私のコードを使用して、誰かがa）私のものがとても遅い理由
b）それがどのように行われるべきか（私が出くわした解決策であった可変性を使用せずに）
c）この場合のメモ化がどのように機能するかを説明したいと思いますか？

4

3 に答える 3

10

私の意見では、「メモ化」は非常に過大評価されています。すべての単一ケースの計算を一般的な計算に変える万能のメモ化手法は (どのプログラミング言語にもありますが) ありません。それぞれの問題を理解し、必要なメモリ量を制御するために整理する必要があります。

この場合、四角形のパスの数を取得するために、すべてのn x m小さい四角形の合計を覚えておく必要はありません。いずれかの方向に 1 段階小さい四角形だけを覚えておく必要があります。したがって、小さな四角形の合計をすべて忘れて、行ごとに積み上げることができます。

Haskell では、怠惰はこの種の状況に最適です。何を覚えて何を忘れるべきかを正確に追跡するすべての作業から解放されます.可能なすべての長方形の合計の無限グリッドを計算するだけで、Haskellに残りの作業を任せることができます.

行が 0 の場合は、一番下の行しかありません。どんなに長くても最後までの道は一本なので、道の数は repeat 1です。

前の行からグリッド内の行を計算するには、1 (どれだけ高くても、まっすぐ下る 1 つのパスのみ) から開始し、各ステップで、前の行の対応するエントリと、前の行の前のステップを合計します。現在の行。全体として、次のものがあります。

iterate (scanl (+) 1 . tail) (repeat 1) !! 20 !! 20

これにより、GHCi プロンプトで即座に答えが計算されます。

于 2010-08-01T13:44:43.753 に答える
5

いくつかのtraceポイントで投げる

memRoute :: (Int,Int) -> Int
memRoute (x,y) = trace ("mem: " ++ show (x,y))
                 fromJust $
                 lookup (x,y) $
                 map (\t -> (t,route t))
                 [(x,y) | x <- [0..20], y <- [0..20]]

route (0,0) = 0
route (_,0) = 1
route (0,_) = 1
route (x,y) = trace ("route: " ++ show (x,y))
              memRoute (x-1,y) + memRoute (x,y-1)

まったくメモ化していないことがわかります。

ghci> memRoute (2,2)
メモリ: (2,2)
ルート: (2,2)
メモリ: (1,2)
ルート: (1,2)
メモリ: (0,2)
メモリ: (1,1)
ルート: (1,1)
メモリ: (0,1)
メモリ: (1,0)
メモリ: (2,1)
ルート: (2,1)
メモリ: (1,1)
ルート: (1,1)
メモリ: (0,1)
メモリ: (1,0)
メモリ: (2,0)
6

サブ計算の再利用は動的計画法です。

import Data.Array

routes :: (Int,Int) -> Int
routes = (rte !)
  where rte = array ((1,1), (n,n))
                    [ ((x,y), route (x,y)) | x <- [1 .. n],
                                             y <- [1 .. n] ]
        route (1,1) = 0
        route (_,1) = 1
        route (1,_) = 1
        route (x,y) = rte ! (x-1,y) + rte ! (x,y-1)
        n = 20

アルゴリズムが正しくないことに注意してください。ただし、少なくとも悪い答えをすぐに取得するのは簡単です!

于 2010-08-01T00:07:56.707 に答える
0

何が起こるかというと、メモ化テーブルはmemRouteへのすべての呼び出しで再計算されます。（幸いなことに！）その全体ではありませんが、少なくとも1回の呼び出しで行われた作業は他の呼び出しと共有されません。私が思いついた最も簡単な書き直しは次のとおりです。

memRoute = let table = map (\t -> (t,route t)) [(x,y) | x <- [0..20], y <- [0..20]]
           in  \(x,y) -> fromJust $ lookup (x,y) $ table

Data.Mapこれは、表現された意図に非常に近いものですが、aを使用し、実際の呼び出しパターンでメモ化する値を決定することで、メモ化を行うためのより良い方法があると思います。

于 2010-08-02T15:29:28.400 に答える