Personal tools

Memoization

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(same base case)
(Int type for list indexes)
Line 8: Line 8:
 
Try <hask>slow_fib 30</hask>, not too much higher than that and it hangs.
 
Try <hask>slow_fib 30</hask>, not too much higher than that and it hangs.
 
<haskell>
 
<haskell>
slow_fib :: Integer -> Integer
+
slow_fib :: Int -> Integer
 
slow_fib 0 = 0
 
slow_fib 0 = 0
 
slow_fib 1 = 1
 
slow_fib 1 = 1
Line 18: Line 18:
   
 
<haskell>
 
<haskell>
memoized_fib :: Integer -> Integer
+
memoized_fib :: Int -> Integer
 
memoized_fib =
 
memoized_fib =
 
let fib 0 = 0
 
let fib 0 = 0

Revision as of 20:10, 5 August 2007


Memoization is a technique for storing values of a function instead of recomputing them each time the function is called.

A classic example is the recursive computation of Fibonacci numbers.

The immediate implementation of Fibonacci numbers without memoization is horribly slow.

Try
slow_fib 30
, not too much higher than that and it hangs.
slow_fib :: Int -> Integer
slow_fib 0 = 0
slow_fib 1 = 1
slow_fib n = slow_fib (n-2) + slow_fib (n-1)

The memoized version is much faster.

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


See also