Difference between revisions of "Memoization"
Jump to navigation
Jump to 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 :: |
+ | 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 :: |
+ | 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 ..] !!)