7

メモ化の紹介を読んだ後、より一般的な memoize 関数を使用してフィボナッチの例を再実装しました (学習目的のみ)。

memoizer :: (Int -> Integer) -> Int -> Integer
memoizer f = (map f [0 ..] !!)

memoized_fib :: Int -> Integer
memoized_fib = memoizer fib
    where fib 0 = 0
          fib 1 = 1
          fib n = memoized_fib (n-2) + memoized_fib (n-1)

これは機能しますが、最後の行を次のコードに変更すると、メモ化が予期したとおりに突然機能しなくなります (プログラムが再び遅くなります)。

          fib n = memoizer fib (n-2) + memoizer fib (n-1)

メモ化との決定的な違いはどこにありますか?

4

2 に答える 2

6

明示的共有と暗黙的共有についてです。ものに明示的に名前を付けると、自然に共有できます。つまり、メモリ内に個別のエンティティとして存在し、再利用できます。(もちろん、共有は言語自体の一部ではありません。特定のものを共有するようにコンパイラーを微調整することしかできません)。

しかし、同じ式を 2 回または 3 回記述すると、コンパイラに依存して、共通のサブ式を 1 つの明示的に共有されたエンティティに置き換えます。それは起こるかもしれないし、起こらないかもしれません。

最初のバリアントは次と同等です

memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)  where
        fib 0 = 0
        fib 1 = 1
        fib n = memoized_fib (n-2) + memoized_fib (n-1)

ここでは、エンティティに具体的な名前を付けて、その名前で参照します。しかし、それは機能です。再利用をさらに確実にするために、ここで共有される実際の値のリストに明示的に名前を付けることができます。

memoized_fib :: Int -> Integer
memoized_fib = (fibs !!)  where
        fibs = map fib [0 ..] 
        fib 0 = 0
        fib 1 = 1
        fib n = memoized_fib (n-2) + memoized_fib (n-1)

最後の行は、ここで共有されている実際のエンティティ (上記の手順で名前を付けたリスト) を明示的に参照することで、さらに視覚的にわかりやすくすることができます。fibs

        fib n = fibs !! (n-2) + fibs !! (n-1)

2番目のバリアントはこれと同等です:

memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)  where
        fib 0 = 0
        fib 1 = 1
        fib n = (map fib [0 ..] !!) (n-2) + (map fib [0 ..] !!) (n-1)

ここには、一見独立しているように見える 3 つのmap式があり、コンパイラによって共有される場合と共有されない場合があります。でコンパイルするとghc -O2、共有が再導入され、速度が向上するようです。

于 2012-08-18T21:05:43.773 に答える
3

momoized_fib = ...- それはトップレベルの簡単な定義です。一定の遅延値として読み取られる場合があります（展開する前に追加の引数をバインドする必要はありません。これは、メモ化された値の一種の「ソース」です。

使用(memoizer fib) (n-2)すると、関係のない値の新しいソースが作成memoized_fibされるため、再利用されません。(map fib [0 ..])実際には、2 番目のバリアントで多くのシーケンスを生成するため、ここで GC に多くの負荷を移動します。

より単純な例も考えてみましょう:

f = \n -> sq !! n where sq = [x*x | x <- [0 ..]]
g n = sq !! n where sq = [x*x | x <- [0 ..]]

宣言の先頭にないため、最初に single を生成fし、それに関連付けます。2 番目は、 の異なる値ごとに一連のリストを生成し、(実際の値に制限されることなく) その上を移動して値を取得します。sqnf n

于 2012-08-18T16:37:32.673 に答える