Haskellメモ化（フィボナッチ）

📅 February 07, 2021

•

⏱️1 min read

すぐ忘れてしまうので、自分のためだけのメモ書き。

フィボナッチとか、普通に書くとこうなる。

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

ただ、これだと、同じ計算を何度もするのでクソ遅い。一度計算したものを参照するメモ化？すると早くなる。

fib :: Int -> Integer
fib n = fibList ! n
        where fibList = listArray (0,n) [fib' x | x <- [0..n]]
              fib' 0 = 0 
              fib' 1 = 1 
              fib' n = fibList ! (n-2) + fibList ! (n-1)

ベクター版

import qualified Data.Vector as V
fib :: Int -> Integer
fib n = fibList V.! n
        where fibList = V.fromList [fib' x | x <- [0..n]]
              fib' 0 = 0 
              fib' 1 = 1 
              fib' n = fibList V.! (n-2) + fibList V.! (n-1)

以上。

← Prev Next →