Mainly Tech projects on Python and Electronic Design Automation.

Friday, April 10, 2009

Memoization and stack use.

I was caught out today when investigating how to apply memoization to
allow computation of larger values of a recursive function.



Mutual Recursion


I had thought up a new task for Rosetta Code called href="http://www.rosettacode.org/wiki/Mutual_Recursion">Mutual
Recursion, as I had remembered that some languages needed
 at least the signature of a function to be defined before it
could be called, and so creating mutually recursive functions would
allow you to compare the languages in an interesting way - which is
what R.C. is all about.



For the example for implementation I used href="http://en.wikipedia.org/wiki/Hofstadter_sequence#Hofstadter_Female_and_Male_sequences"
target="_blank">Hoffstadters Female and Male
sequences, and produced the following href="http://www.rosettacode.org/wiki/Mutual_Recursion#Python">Python
definitions:


def  color="#008080">F(n): return 1  color="#804040">if n == 0  color="#804040">else n - M(F(n-1))
color="#804040">def color="#008080">M(n): return 0 color="#804040">if n == 0 color="#804040">else n - F(M(n-1))


It seems that other members of R.C. liked the task and soon added many
examples in other languages.



Apart from the computation of the series for 0<=n<20, I
did try to compute F(200) but it blew the stack so I went to bed and
decided to memoize the functions another day.



target="_blank">Wot, no memoize?


Memoization came very easily to mind, so I thought that Python would
have such available as a decorator waiting to be applied. No such luck,
I would have to craft my own . I did remember correctly however that
there was some  helper function that made wrapped functions
look a lot more like what had been wrapped, and so used functools.wrap:


from functools  color="#a020f0">import wraps

color="#804040">def color="#008080">memoize0(func):
' color="#ff00ff"> Adds cache as attribute to wrapped function for ease of access'
color="#a020f0">@wraps(func)
color="#804040">def color="#008080">wrapper(*args):
argsl = tuple(args)
color="#804040">if argsl color="#804040">in wrapper._cache:
color="#804040">return wrapper._cache[argsl]
color="#804040">else:
color="#804040">return wrapper._cache.setdefault(argsl, func(*args))
wrapper._cache = dict()
color="#804040">return wrapper

color="#804040">def color="#008080">memoize(func):
' color="#ff00ff"> Creates closure around locally created cache'
cache = dict()
color="#a020f0">@wraps(func)
color="#804040">def color="#008080">wrapper(*args):
argsl = tuple(args)
color="#804040">if argsl color="#804040">in cache:
color="#804040">return cache[argsl]
color="#804040">else:
color="#804040">return cache.setdefault(argsl, func(*args))
color="#804040">return wrapper




I haven't got over my (probably infantile) lust for attaching
attributes to functions so justified memoize0 as it allows you to look
at the contents of the cache. Combined with the fact that you cannot do
a memoization decorator without applying it to a href="http://en.wikipedia.org/wiki/Fibonacci_function">Fibonacci
number function:


if __name__ == ' color="#ff00ff">__main__':
color="#a020f0">@memoize0
color="#804040">def color="#008080">fib(n): return n color="#804040">if n color="#804040">in (0,1) color="#804040">else fib(n - 1) + fib(n - 2)
color="#a020f0">@memoize0
color="#804040">def color="#008080">fib2(n): color="#804040">return n color="#804040">if n color="#804040">in (0,1) color="#804040">else fib2(n - 1) + fib2(n - 2)
color="#804040">assert fib._cache color="#804040">is color="#804040">not fib2._cache
fib(50); fib2(50)
color="#804040">assert fib._cache == fib2._cache color="#804040">and (fib._cache color="#804040">is color="#804040">not fib2._cache)




It is important that caches are not shared for mutually recursive
functions.

A blown stack


I had initial success with the Male and Female sequence and was easily
able to compute F(200) with:



@ color="#008080">memoize
color="#804040">def color="#008080">F(n):
' color="#ff00ff"> Hofstadters Female Male sequences'
color="#804040">return 1 color="#804040">if n == 0 color="#804040">else n - M(F(n-1))

color="#a020f0">@memoize
color="#804040">def color="#008080">M(n):
' color="#ff00ff"> Hofstadters Female Male sequences'
color="#804040">return 0 color="#804040">if n == 0 color="#804040">else n - F(M(n-1))

color="#804040">assert F(200) == 124




But I got cocky, as F(2000) ran out of stack.



A little thought made me realise that I only had a cached results for F
and M up to around 200 and so a call of F(2000) was going to eat up
huge amounts of stack before recursing down to cached values.

With that knowledge in mind I thought I might gradually jump to higher
values of  n and, indeed, the following worked:


    print ([F(n)  color="#804040">for n  color="#804040">in range(0,20000+1,100)])




In real-world applicatrions, you might have to have some scheme to
reduce or limit cache size if memory rather than the stack becomes an
issue, and I have a great solution that I have just completed in the
margin :-)



- Paddy.

3 comments:

  1. Look up Dynamic Programming in Wikipedia. There's a natural way to reverse the computation of a memoized function from the bottom up and avoid stack limits.

    ReplyDelete
  2. Hi Marius,
    I took a look and Dynamic programming, according to WP, has two methods:
    1) Recursion and memoization - which I am applying above.
    2) The bottom-up approach which amounts to changing recursion into iteration - which I didn't want to do in this case as I was purposefully playing with recursion.

    Thanks for the input though.

    - Paddy.

    ReplyDelete
  3. See sys.setrecursionlimit().
    Python's default limit is 1000.
    Note that the wrapper increases the stack depth by 2 - e.g. to compute F(2000) you want to allow 4000 depth.

    ReplyDelete

Followers

Subscribe Now: google

Add to Google Reader or Homepage

Go deh too!

whos.amung.us

Blog Archive