Personal tools

Memoization

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(short explanation)
 
(Fibonacci, memoization with a simple list)
Line 2: Line 2:
   
 
'''Memoization''' is a technique for storing values of a function instead of recomputing them each time the function is called.
 
'''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 number]]s.
  +
  +
The immediate implementation of Fibonacci numbers without memoization is horribly slow.
  +
Try <hask>slow_fib 30</hask>, not too much higher than that and it hangs.
  +
<haskell>
  +
slow_fib :: Integer -> Integer
  +
slow_fib 1 = 1
  +
slow_fib 2 = 1
  +
slow_fib n = slow_fib (n-2) + slow_fib (n-1)
  +
</haskell>
  +
  +
The memoized version is much faster.
  +
Try <hask>memoized_fib 10000</hask>.
  +
  +
<haskell>
  +
memoized_fib :: Integer -> Integer
  +
memoized_fib =
  +
let fib' 0 = 0
  +
fib' 1 = 1
  +
fib' n = memoized_fib (n-2) + memoized_fib (n-1)
  +
in (map fib' [0 ..] !!)
  +
</haskell>
  +
   
 
== See also ==
 
== See also ==

Revision as of 20:02, 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 :: Integer -> Integer
slow_fib 1 = 1
slow_fib 2 = 1
slow_fib n = slow_fib (n-2) + slow_fib (n-1)

The memoized version is much faster.

Try
memoized_fib 10000
.
memoized_fib :: Integer -> 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