15

フィボナッチ数を計算する簡単な関数を次に示します。

fib :: [Int]
fib = 1 : 1 : zipWith (+) fib (tail fib)

ghci では、シリーズをすばやく計算できます。実際、少し実験すると、計算がほぼ線形時間で実行されることがわかります。

ghci> last $ take 100000 fib
354224848179261915075         -- takes under a second

型シグネチャをポリモーフィックに変更すると、次のようになります。

fib :: Num a => [a]
fib = 1 : 1 : zipWith (+) fib (tail fib)

その後、アルゴリズムは遅くなります。実際、指数時間で実行されるようになりました。

ポリモーフィック型シグネチャへの切り替えは、リストが各段階で完全に再計算されることを意味しますか? もしそうなら、なぜですか？

4

2 に答える 2

15

はい、ポリモーフィック型シグネチャは、各段階で再計算されていることを意味します。ghc-7.4.2 によって生成されたコア-O2:

lvl_rcZ :: GHC.Integer.Type.Integer
[GblId, Str=DmdType]
lvl_rcZ = __integer 1

Rec {
PolyFib.fib [Occ=LoopBreaker]
  :: forall a_a9W. GHC.Num.Num a_a9W => [a_a9W]
[GblId, Arity=1, Str=DmdType L]
PolyFib.fib =
  \ (@ a_aal) ($dNum_aam :: GHC.Num.Num a_aal) ->
    GHC.Types.:
      @ a_aal
      (GHC.Num.fromInteger @ a_aal $dNum_aam lvl_rcZ)
      (GHC.Types.:
         @ a_aal
         (GHC.Num.fromInteger @ a_aal $dNum_aam lvl_rcZ)
         (GHC.List.zipWith
            @ a_aal
            @ a_aal
            @ a_aal
            (GHC.Num.+ @ a_aal $dNum_aam)
            (PolyFib.fib @ a_aal $dNum_aam)
            (case PolyFib.fib @ a_aal $dNum_aam of _ {
               [] -> GHC.List.tail1 @ a_aal;
               : _ xs_abD -> xs_abD
             })))
end Rec }

その理由は、 に属する各型のフィボナッチ数のリストをキャッシュするのは現実的Numでfibはなく、明示的にポリモーフィックな値であるため、まったくキャッシュされないためです。

少なくとも各タイプの計算のためにキャッシュしたい場合は、ローカルリストを使用してください

pfibs :: Num a => [a]
pfibs = res
  where
    res = 1 : 1 : zipWith (+) res (tail res)

pfibs !! 500リストは各計算で単相的であるため、計算ごとにキャッシングを行います（したがって、高速です）。クエリごとに再計算されますが (単形名にバインドしない限り)、単一のリスト要素ごとには再計算されません。

*PolyFib> pfibs !! 999999 :: Int
-4249520595888827205
(0.31 secs, 137462088 bytes)
于 2012-06-21T19:54:23.283 に答える
15

これは辞書の翻訳によるものです。

fib :: [Int]

トップレベルの定数です。

でもこれは：

fib :: Num a => [a]
fib = 1 : 1 : zipWith (+) fib (tail fib)

Num実行時にディクショナリに適用される最上位の関数です。そのようです：

fib d = 1 : 1 : zipWith (d.+) (fib d) (tail (fib d))

したがって、これを最適化せずにコンパイルして、特殊化が発生しないようにすると、関数呼び出しごとにリストが最初から再構築されるため、指数関数的な時間 fib になります。これはもはや遅延データ構造ではありません。

于 2012-06-21T20:02:48.987 に答える