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.

  • 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. – Barmar Mar 08 '19 at 18:24
  • I don't understand your problem. You said you expected the loop to be fastest, and 140 microseconds is fastest. – Barmar Mar 08 '19 at 18:25
  • The memoized version will be fastest if you use it multiple times. – Barmar Mar 08 '19 at 18:26
  • 2
    @Barmer, second number is nanoseconds – CryptoFool Mar 08 '19 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. – Barmar Mar 08 '19 at 18:28
  • @Barmar I was gonna say that. That's exactly why it's magnitudes faster. – blhsing Mar 08 '19 at 18:29
  • 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))`. – blhsing Mar 08 '19 at 18:36
  • @Barmar and blhsing It looks like it's the repeat runs '%timeit' was doing. Testing a single run on a largish number -- up to recursion limit -- it looks like the order is more like: (1) loop; (2) generator; (3) array memo; (4) dict memo. So roughly what I would've guessed before. Thanks, gang. –  Mar 08 '19 at 22:21
  • Your timings will depend on the value of n - what was it? (*"The second is by far the fastest, despite the recursion and lots of function calls."* Well if n ~ len(memo), then there isn't lots of recursion, just list/dict lookup) – smci Mar 08 '19 at 22:57
  • A related consideration is that [lru_cache uses a `cache` dict](https://stackoverflow.com/questions/49883177/how-does-lru-cache-from-functools-work), hence will be less memory-efficient than this approach, a manual list for one single (consecutive) integer argument (passing `memo` as a second argument instead of a global or state variable, will probably muddy things, anyway `lru_cache` can't handle mutable args like dicts). I wonder if anyone's ever looked into alternative list-based implementation of lru_cache for functions taking one integer argument... – smci Mar 09 '19 at 00:20
  • Your first method "simple loop" is the very-well-known tail recursion approach: O(N) time- and O(1) memory-complexity. – smci Mar 09 '19 at 00:28
  • 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. –  Mar 09 '19 at 01:04
  • If you want a faster Fibonacci algorithm, see https://stackoverflow.com/a/40683466/4014959 – PM 2Ring Mar 09 '19 at 11:42

1 Answers1

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})
Barmar
  • 741,623
  • 53
  • 500
  • 612
  • 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. –  Mar 09 '19 at 01:00
  • I can't reproduce that error. I tried `fibonacci(10)` then `fibonacci(5)` and got no error. – Barmar Mar 09 '19 at 01:02
  • You're right. User error, I'm sure. (Too many similarly named alternative implementations bouncing around my workspace, I'm thinking.) What I am sure of is that when the memo is a parameter, subsequent calls see the largest version of memo so far, instead of reinitializing memo to [0,1]. (Although I'm told 'memo' is not defined.) This is *not* true if the main function just wraps a properly initialized memo and the helper function which alone can see it. Same for a hand-rolled wrapper decorator. So where is memo? Is its current value being stored with the function definition?? –  Mar 09 '19 at 04:14
  • 1
    @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](https://stackoverflow.com/a/34036910/4014959). – PM 2Ring Mar 09 '19 at 11:38
  • @PM2Ring Thanks for the link, checking it out. –  Mar 09 '19 at 18:27
  • 1
    See https://stackoverflow.com/questions/1132941/least-astonishment-and-the-mutable-default-argument regarding using a dictionary or list as a default argument value. – Barmar Mar 09 '19 at 18:28
  • 1
    @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. ;) – PM 2Ring Mar 09 '19 at 18:32
  • @Barmar Already reading the thread you just linked! Thanks again. –  Mar 09 '19 at 18:41