2

I have this code for computing fibonacci numbers using cache (dictionary).

cache = {} 
def dynamic_fib(n):
    print n
    if n == 0 or n == 1:
        return 1
    if not (n in cache):
        print "caching %d" % n
        cache[n] = dynamic_fib(n-1) + dynamic_fib(n-2)

    return cache[n]

if __name__ == "__main__":
    start = time.time()
    print "DYNAMIC: ", dynamic_fib(2000)
    print (time.time() - start)

I works fine with small numbers, but with more than 1000 as an input, it seems to stop.

This is the result with 2000 as an input.

....
caching 1008
1007
caching 1007
1006
caching 1006
1005
caching 1005

This is a result with 1000 as an input. 

....
8
caching 8
7
caching 7
6
caching 6
5
caching 5

It looks like that after 995 storage into the dictionary, it just hangs. What might be wrong in this? What debugging technique can I use to see what went wrong in python?

I run python on Mac OS X 10.7.5, I have 4G bytes of RAM, so I think some KB (or even MB) of memory usage doesn't matter much.

Improve this question
5
  • 1
    python has recursion limit. Commented Jan 3, 2013 at 17:58
  • 3
    It surprises me that this is hanging for you rather than throwing a RuntimeError: maximum recursion depth exceeded Commented Jan 3, 2013 at 18:00
  • @DavidRobinson After a short hang it does throws that Error on my system. Commented Jan 3, 2013 at 18:03
  • This limit prevents infinite recursion from causing an overflow of the C stack and crashing Python. Commented Jan 3, 2013 at 18:04
  • How large a Fibonacci number will you be calculating, and will you tend to work your way up to that number (thus building a cache) or jump straight to it? If the latter, you will run out of memory due to the large depth of recursion. Commented Jan 3, 2013 at 18:14

4 Answers 4

Reset to default
2

Python has a default recursion limit set to 1000. You need to increase it in your program.

import sys

sys.setrecursionlimit(5000)

From : http://docs.python.org/2/library/sys.html#sys.setrecursionlimit

sys.setrecursionlimit(limit)

Set the maximum depth of the Python interpreter stack to limit. 
This limit prevents infinite recursion from causing an overflow of the C 
stack and crashing Python.
The highest possible limit is platform-dependent. A user may need to set the
limit higher when she  has a program that requires deep recursion and a 
platform that supports a higher limit. This should bedone with care, because
a too-high limit can lead to a crash.
Improve this answer
Sign up to request clarification or add additional context in comments.

12 Comments

While this kind of solves the problem - it doesn't really solve the larger issue, or explain it.
Indeed. On my system, this runs out of memory at about 12000 due to the large number of recursive frames. It might be a good idea to use an iterative solution if that is a possible use case.
@DavidRobinson -- See my "recursive" solution (it only recurses 2 levels deep into the stack), but still caches results as the original did.
The iterative solution is still an order of magnitude faster (for a million runs with n=500, dynamic_fib takes 51 seconds, while iterative_fib takes 7).
@Tinctorius -- I'd be interested to see exactly how you're timing it. dynamic_fib should cache the results meaning that it should only spend the time to calculate it once, every other time it should return the value almost immediately.
|
2

You don't really gain anything by storing the cache as a dictionary since in order to calculate f(n) you need to know f(n-1) (and f(n-2)). In other words, your dictionary will always have keys from 2-n. You might as well just use a list instead (it's only an extra 2 elements). Here's a version which caches properly and doesn't hit the recursion limit (ever):

import time
cache = [1,1]

def dynamic_fib(n):
    #print n
    if n >= len(cache):
        for i in range(len(cache),n):
            dynamic_fib(i)

        cache.append(dynamic_fib(n-1) + dynamic_fib(n-2))
        print "caching %d" % n

    return cache[n]

if __name__ == "__main__":
    start = time.time()
    a = dynamic_fib(4000)
    print "Dynamic",a
    print (time.time() - start)

Note that you could do the same thing with a dict, but I'm almost positive that a list will be faster.

Just for fun, here's a bunch of options (and timings!):

def fib_iter(n):
    a, b = 1, 1
    for i in xrange(n):
        a, b = b, a + b
    return a

memo_iter = [1,1]
def fib_iter_memo(n):
    if n == 0:
        return 1
    else:
        try:
            return memo_iter[n+1]
        except IndexError:
            a,b = memo_iter[-2:]
            for i in xrange(len(memo_iter),n+2):
                a, b = b, a + b
                memo_iter.append(a)
            return memo_iter[-1]

dyn_cache = [1,1]
def dynamic_fib(n):
    if n >= len(dyn_cache):
        for i in xrange(len(dyn_cache),n):
            dynamic_fib(i)

        dyn_cache.append(dynamic_fib(n-1) + dynamic_fib(n-2))

    return dyn_cache[n]

dyn_cache2 = [1,1]
def dynamic_fib2(n):
    if n >= len(dyn_cache2):
        for i in xrange(len(dyn_cache2),n):
            dynamic_fib2(i)

        dyn_cache2.append(dyn_cache2[-1] + dyn_cache2[-2])

    return dyn_cache2[n]

cache_fibo = [1,1]
def dyn_fib_simple(n):
   while len(cache_fibo) <= n:
        cache_fibo.append(cache_fibo[-1]+cache_fibo[-2])
   return cache_fibo[n]

import timeit
for func in ('dyn_fib_simple','dynamic_fib2','dynamic_fib','fib_iter_memo','fib_iter'):
    print timeit.timeit('%s(100)'%func,setup='from __main__ import %s'%func),func


print fib_iter(100)
print fib_iter_memo(100)
print fib_iter_memo(100)
print dynamic_fib(100)
print dynamic_fib2(100)
print dyn_fib_simple(100)

And the results:

0.269892930984 dyn_fib_simple
0.256865024567 dynamic_fib2
0.241492033005 dynamic_fib
0.222282171249 fib_iter_memo
7.23831701279 fib_iter
573147844013817084101
573147844013817084101
573147844013817084101
573147844013817084101
573147844013817084101
573147844013817084101
Improve this answer

4 Comments

+1 for the list cache, I was writing a similar answer but yours would have won anyways :)
@l4mpi -- Don't dicts have an O(1) length check as well? I would expect that indexing would be slightly faster with the lists since you don't have to hash (although that's cheap for ints I'd think). Mainly, I just think that a list is a more sane data structure for this since it provides the exact same mapping that a dict would -- with less memory overhead and faster indexing
Ah you're right of course, dict lookup is O(1) as well (if there's no collisions at least). I also think a list is more sane here, a dict might be the more natural choiche though as you can only use a list for specific functions like fib / fac and similar recursive sequences. The only advantage a dict would have here is that you could sparsely populate it with precomputed values to speed up initial computation of un-cached values.
When stack space is sufficient, this solution is slower than OP's solution (5.1 seconds versus 8.8 seconds for 10000 runs with n=500)(an iterative solution takes 0.7 seconds with the same parameters).
1

A recursion free version:

def fibo(n):
   cache=[1,1]
   while len(cache) < n:
       cache.append(cache[-1]+cache[-2])
   return cache
Improve this answer

2 Comments

This doesn't actually cache the results for subsequent calls though, it just gives you the entire series up to n.
You mean return cache[-1]. Still, since you're only accessing the last two elements, this version performs worse than it could.
0

It's probably because of the limit of stack depth, which results in an RuntimeError. You can increase the stack's recursion limit by calling

sys.setrecursionlimit(<number>)

of the sys module.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.