Memoization
From HaskellWiki
(Difference between revisions)
(Int type for list indexes) |
(link to The Fibonacci sequence) |
||
| Line 3: | Line 3: | ||
'''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 | + | A classic example is the recursive computation of [[The Fibonacci sequence|Fibonacci numbers]]. |
| - | The | + | The naive implementation of Fibonacci numbers without memoization is horribly slow. |
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> | ||
Revision as of 20:31, 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 naive implementation of Fibonacci numbers without memoization is horribly slow.
Tryslow_fib 30
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.
Trymemoized_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 ..] !!)
