Memoization
From HaskellWiki
(Difference between revisions)
(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.
Tryslow_fib 30
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.
Trymemoized_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 ..] !!)
