memoization

[Logesh Pillay-3]

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.  
How to fix?

 

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Derek Elkins]

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.

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Ketil Malde-5]

Logesh Pillay <lpillay@...> writes:

> Why?  Its as if memoization is being ignored in the haskell version.
> How to fix?

Shouldn't the definition of p' call (the memoized) p somewhere?  In
other words, I can't see any memoization, you seem to just map a
normal, expensive, recursive function p' over a list.

(Another difference is that Python's associative arrays are likely to
be faster than Haskell's linear-time indexed lists.)

-k
--
If I haven't seen further, it is by standing in the footprints of giants
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Henning Thielemann]

On Sun, 13 Jul 2008, 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]]

You don't use memoization here - so why do you expect it would take place?

I have a fast implementation:
   http://darcs.haskell.org/htam/src/Combinatorics/Partitions.hs

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe