4

"Base" meaning without just using lru_cache. All of these are "fast enough" -- I'm not looking for the fastest algorithm -- but the timings surprised me so I was hoping I could learn something about how Python "works".

Simple loop (/tail recursion):

def fibonacci(n):
    a, b = 0, 1
    if n in (a, b): return n
    for _ in range(n - 1):
        a, b = b, a + b
    return b

Simple memoized:

def fibonacci(n, memo={0:0, 1:1}):
    if len(memo) <= n:
        memo[n] = fibonacci(n - 1) + fibonacci(n - 2)
    return memo[n]

Using a generator:

def fib_seq():
    a, b = 0, 1
    yield a
    yield b
    while True:
        a, b = b, a + b
        yield b

def fibonacci(n):
    return next(x for (i, x) in enumerate(fib_seq()) if i == n)

I expected the first, being dead simple, to be the fastest. It's not. The second is by far the fastest, despite the recursion and lots of function calls. The third is cool, and uses "modern" features, but is even slower, which is disappointing. (I was tempted to think of generators as in some ways an alternative to memoization -- since they remember their state -- and since they're implemented in C I was hoping they'd be faster.)

Typical results:

loop: about 140 μs
memo: about 430 ns
genr: about 250 μs

So can anyone explain, in particular, why memoization is an order of magnitude faster than a simple loop?

EDIT:

Clear now that I have (like many before me) simply stumbled upon Python's mutable default arguments. This behavior explains the real and the apparent gains in execution speeds.

Improve this question
13
  • The generator is more like the first case, except you're doing a function call between each iteration. Every time you start a new loop it forgets everything, so it's not like memoization. Commented Mar 8, 2019 at 18:24
  • 2
    @Barmer, second number is nanoseconds Commented Mar 8, 2019 at 18:26
  • 4
    Did you get those results by running the function multiple times and averaging? The memoized version doesn't do any recursions on the repeated calls. Commented Mar 8, 2019 at 18:28
  • 2
    Side note: there's no need to use a dict. Use a list instead and it will be even faster. Change memo to default to [0, 1], and change the line of the recursive calls to memo.append(fibonacci(n - 1) + fibonacci(n - 2)). Commented Mar 8, 2019 at 18:36
  • 1
    @smci Thanks very much for your comments. I think the issues I was seeing have to do with the way this implementation passes the memo as a parameter, instead of properly wrapping the function with a memo data structure. Commented Mar 9, 2019 at 1:04

1 Answer 1

Reset to default
0

What you're seeing is the whole point of memoization. The first time you call the function, the memo cache is empty and it has to recurse. But the next time you call it with the same or a lower parameter, the answer is already in the cache, so it returns immediately. if you perform thousands of calls, you're amortizing that first call's time over all the other calls. That's what makes memoization such a useful optimization, you only pay the cost the first time.

If you want to see how long it takes when the cache is fresh and you have to do all the recursions, you can pass the initial cache as an explicit argument in the benchmark call:

fibonacci(100, {0:0, 1:1})
Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

There's something here I don't understand yet about my memo parameter and its persistence. I can get index errors by calling this memoized fib on a higher number then a lower. If instead I memoize less cleverly by just wrapping the memo and a helper function, I get performance almost identical to the loop version, with the generator still trailing a bit behind.
I can't reproduce that error. I tried fibonacci(10) then fibonacci(5) and got no error.
@SrapTasmaner The default memo dict object in your code is created when the function definition is executed to produce the callable function object. If you pass a memo arg when you call the function, the passed in arg shadows the default one. FWIW, using mutable default args like that is the fastest way to do memoization in Python. You can see my timeit tests here.
See stackoverflow.com/questions/1132941/… regarding using a dictionary or list as a default argument value.
@Barmar Fair point. Whenever I use mutable default args I comment them so readers of the code know it's intentional and not a bug. ;)
|

Your Answer

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