[Haskell-cafe] memoization
Derek Elkins
derek.a.elkins at gmail.com
Sun Jul 13 14:29:48 EDT 2008
On Sun, 2008-07-13 at 20:24 +0200, Logesh Pillay wrote:
> I know we can perform memoization in Haskell. The well known recursive
> Fibonacci example works v. well. f(10000) returns a virtually instant
> answer which would not be possible otherwise.
>
> My (probably naive) function to give the number of partitions of a number :-
> p = ((map p' [0 .. ]) !!)
> where
> p' 0 = 1
> p' 1 = 1
> p' n = sum [(((-1) ^ (k+1)) * ( p' (n-((k*(3*k-1)) `div` 2)) + p'
> (n-((k*(3*k+1)) `div` 2)))) | k <- [1 .. n]]
>
> It is an attempt to apply the Euler recurrence formula (no 11 in
> http://mathworld.wolfram.com/PartitionFunctionP.html )
>
> It works but it is shockingly slow. It is orders of magnitude slower
> than the Python memoized version which runs very fast.
> parts = {0:1, 1:1}
> def P(n):
> if not n in parts:
> parts[n] = sum ([( ((-1) ** (k+1)) * ( P(n-((k*(3*k-1))//2)) +
> P(n-((k*(3*k+1))//2)) ) ) for k in xrange (1, n+1)])
> return parts[n]
>
> Why? Its as if memoization is being ignored in the haskell version.
That's because you aren't using it.
> How to fix?
Use your memoized function.
More information about the Haskell-Cafe
mailing list