120

このフィボナッチ機能はどのようなメカニズムでメモ化されていますか？

fib = (map fib' [0..] !!)                 
     where fib' 1 = 1                                                        
           fib' 2 = 1                                                        
           fib' n = fib (n-2) + fib (n-1)

そして、関連するメモで、なぜこのバージョンはそうではないのですか？

fib n = (map fib' [0..] !! n)                                               
     where fib' 1 = 1                                                        
           fib' 2 = 1                                                        
           fib' n = fib (n-2) + fib (n-1)
4

4 に答える 4

96

Haskell の評価メカニズムは必要に応じて行われます。値が必要になると、値が計算され、再度要求された場合に備えて準備されます。リストを定義しxs=[0..]、後でその 100 番目の要素 を要求するとxs!!99、リストの 100 番目のスロットが「肉付け」され、番号が保持され、99次のアクセスの準備が整います。

それが、そのトリック、「リストを通過する」が利用しているものです。通常の二重再帰フィボナッチ定義 ではfib n = fib (n-1) + fib (n-2)、関数自体が上から 2 回呼び出され、指数爆発が発生します。しかし、そのトリックを使用して、中間結果のリストを設定し、「リストを調べて」いきます。

fib n = (xs!!(n-1)) + (xs!!(n-2)) where xs = 0:1:map fib [2..]

その秘訣は、そのリストを作成させ、そのリストが への呼び出しの間に (ガベージ コレクションによって) 消えないようにすることですfib。これを実現する最も簡単な方法は、そのリストに名前を付けることです。「名前を付ければ、残ります。」

最初のバージョンは単相定数を定義し、2 番目のバージョンは多相関数を定義します。ポリモーフィック関数は、提供する必要があるさまざまなタイプに対して同じ内部リストを使用できないため、共有はありません。つまり、メモ化はありません。

最初のバージョンでは、コンパイラは私たちに寛大で、その定数部分式 ( ) を取り出してmap fib' [0..]別の共有可能なエンティティにしていますが、そうする義務はありません。実際には、自動的にそれを行いたくない場合があります。

( edit: ) これらの書き直しを検討してください:

fib1 = f                     fib2 n = f n                 fib3 n = f n          
 where                        where                        where                
  f i = xs !! i                f i = xs !! i                f i = xs !! i       
  xs = map fib' [0..]          xs = map fib' [0..]          xs = map fib' [0..] 
  fib' 1 = 1                   fib' 1 = 1                   fib' 1 = 1          
  fib' 2 = 1                   fib' 2 = 1                   fib' 2 = 1          
  fib' i=fib1(i-2)+fib1(i-1)   fib' i=fib2(i-2)+fib2(i-1)   fib' i=f(i-2)+f(i-1)

したがって、本当の話は、ネストされたスコープ定義に関するものであるようです。1番目の定義では外側のスコープはなく、3番目の定義ではouter-scopefib3ではなく、同じレベルを呼び出すように注意していますf。

の新しい呼び出しごとfib2に、入れ子になった定義が新たに作成されるようです。これは、 (理論的には)の値に応じnて定義が異なる可能性があるためです(指摘してくれた Vitus と Tikhon に感謝します)。最初の定義にnは依存する必要がなく、3 番目の定義には依存関係がありますが、fib3呼び出しへの個別の呼び出しごとfに、この特定の呼び出しの内部で、同じレベルのスコープから定義のみを呼び出すように注意するfib3ため、同じものxsを取得しますの呼び出しで再利用 (つまり、共有) されますfib3。

しかし、上記のバージョンのいずれかの内部定義が実際には外部バインディングから独立していることをコンパイラーが認識することを妨げるものは何もありません。最終的にはラムダ リフティングを実行し、完全なメモ化を行います (ポリモーフィック定義を除く)。実際、モノモーフィック型で宣言され、-O2 フラグでコンパイルされた場合、3 つのバージョンすべてでまさにこれが起こります。ポリモーフィック型宣言では、ローカル共有を示し、共有をまったく示しません。nfib3fib2

最終的には、コンパイラ、使用されるコンパイラの最適化、およびそれをテストする方法 (GHCI でファイルをロードするか、コンパイルされているかどうか、-O2 を使用しているかどうか、またはスタンドアロン)、およびモノモーフィック型またはポリモーフィック型のどちらを取得するかによって、動作が異なる場合があります。完全に変更 - ローカル (呼び出しごと) 共有 (つまり、各呼び出しで線形時間)、メモ化 (つまり、最初の呼び出しで線形時間、同じか小さい引数での後続の呼び出しで 0 時間) を示すか、まったく共有しないか (指数時間）。

簡単に言えば、それはコンパイラの問題です。:)

于 2012-07-13T08:39:01.747 に答える
23

私は完全に確信しているわけではありませんが、ここに経験に基づいた推測があります：

fib nコンパイラは、それが別のもので異なる可能性があると想定しているnため、毎回リストを再計算する必要があります。where結局、ステートメント内のビットはに依存する可能性がnあります。つまり、この場合、数値のリスト全体は本質的に の関数ですn。

なし のバージョンでnは、リストを一度作成して関数でラップできます。リストは、渡された の値に依存することはできませんn。これは簡単に確認できます。リストは定数であり、次にインデックスが作成されます。もちろん、これは遅延評価される定数であるため、プログラムは (無限の) リスト全体をすぐに取得しようとしません。これは定数であるため、関数呼び出し間で共有できます。

再帰呼び出しはリスト内の値を検索するだけなので、メモ化されています。バージョンはリストを一度遅延して作成するためfib、冗長な計算を行わずに、答えを得るのに十分な計算を行います。ここで、「遅延」とは、リスト内の各エントリがサンク (未評価の式) であることを意味します。サンクを評価すると値になるため、次にアクセスしても計算は繰り返されません。リストは通話間で共有できるため、次のエントリが必要になるまでに、以前のすべてのエントリがすでに計算されています。

これは基本的に、GHC の遅延セマンティクスに基づいた、巧妙で低コストの動的プログラミングの形式です。標準はnon-strictでなければならないことだけを指定していると思うので、準拠したコンパイラはこのコードをメモ化しないようにコンパイルする可能性があります。ただし、実際には、合理的なコンパイラはすべて遅延します。

2 番目のケースが機能する理由の詳細については、再帰的に定義されたリストを理解する (zipWith に関する fibs) を参照してください。

于 2012-07-13T08:01:33.440 に答える
20

まず、 でコンパイルされた ghc-7.4.2 では、メモ化され-O2ていないバージョンはそれほど悪くはありません。フィボナッチ数の内部リストは、関数のトップレベル呼び出しごとにメモ化されています。しかし、さまざまなトップレベルの呼び出しにまたがってメモすることはできませんし、合理的にもできません。ただし、他のバージョンの場合、リストは通話間で共有されます。

これは、単型性の制限によるものです。

1 つ目は単純なパターン バインディング (名前のみ、引数なし) によってバインドされているため、モノモーフィズムの制限により、モノモーフィック型を取得する必要があります。推測される型は

fib :: (Num n) => Int -> n

そして、そのような制約はデフォルトで（別のことを言うデフォルト宣言がない場合） になりInteger、タイプを次のように固定します

fib :: Int -> Integer

したがって[Integer]、メモする (タイプの) リストは 1 つだけです。

2 つ目は関数の引数で定義されているため、多相的なままであり、内部リストが複数の呼び出しでメモ化されている場合、 の型ごとに 1 つのリストをメモ化する必要がありますNum。それは実用的ではありません。

モノモーフィズムの制限を無効にするか、同じ型シグネチャを使用して両方のバージョンをコンパイルすると、両方がまったく同じ動作を示します。(これは、古いコンパイラ バージョンには当てはまりませんでした。どのバージョンが最初に実行されたかはわかりません。)

于 2012-07-13T08:47:36.923 に答える
5

Haskell の memoize 関数は必要ありません。経験的プログラミング言語だけがその機能を必要とします。ただし、Haskel は関数型言語であり、...

したがって、これは非常に高速なフィボナッチ アルゴリズムの例です。

fib = zipWith (+) (0:(1:fib)) (1:fib)

zipWith は、標準の Prelude の関数です。

zipWith :: (a->b->c) -> [a]->[b]->[c]
zipWith op (n1:val1) (n2:val2) = (n1 + n2) : (zipWith op val1 val2)
zipWith _ _ _ = []

テスト：

print $ take 100 fib

出力：

[1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676221,23416728348467685,37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,420196140727489673,679891637638612258,1100087778366101931,1779979416004714189,2880067194370816120,4660046610375530309,7540113804746346429,12200160415121876738,19740274219868223167,31940434634990099905,51680708854858323072,83621143489848422977,135301852344706746049,218922995834555169026,354224848179261915075,573147844013817084101]

経過時間：0.00018秒

于 2015-04-23T15:19:58.873 に答える