Python3 functools lru_cache RuntimeError

Question

from functool import lru_cache


@lru_cache
def fibonacci(n):
    """0, 1, 1, 2, 3, 5, 8, 13, 21, 34
    """

    if n == 0:
        yield 0
    elif n == 1:
        yield 1
    else:
        yield next(fibonacci(n - 1)) + next(fibonacci(n - 2))

If i call this function with the @lru_cache decorator like this:

for x in range(10):
    print(next(fibonacci(x)))

i get:

StopIteration

The above exception was the direct cause of the following exception:

RuntimeError: generator raised StopIteration

I have done a bunch of searching and i have no idea how to fix this. Without the decorator, everything works fine.

"i have no idea how to fix this. Without the decorator, everything works fine." - Sounds like you **do** know how to fix this. — Kelly Bundy, Aug 11 '20 at 17:46
Hi, I guess `return` would be better _here_ than `yield`. ;) — levif, Aug 11 '20 at 17:46
You are caching generators, that will yield exactly one item each. They will work exactly one time each; retrieving one of them from the cache later will fail because they have no items left. — jasonharper, Aug 11 '20 at 18:27
Basically codewars timed out so I wanted to make it faster. Thought this could do it, but it couldn't, yet removing the decorator doesn't fix the timeout so I wanted to know why this didn't work. I need to be able to get only one value at the time as it needs to be able to get values from different functions in-between if that makes sense and then continue where this left off so using return would keep too much in memory because I have no idea how big the numbers are that get passed to the function. — Sea Wolf, Aug 12 '20 at 18:24

score 2 · Answer 1 · answered Aug 11 '20 at 17:53

2

If you really do want to cache and thus reuse the generator iterators, make sure they actually support that. That is, make them yield their result not just once but repeatedly. For example:

@lru_cache
def fibonacci(n):
    """0, 1, 1, 2, 3, 5, 8, 13, 21, 34
    """

    if n == 0:
        while True:
            yield 0
    elif n == 1:
        while True:
            yield 1
    else:
        result = next(fibonacci(n - 1)) + next(fibonacci(n - 2))
        while True:
            yield result

Test:

>>> for x in range(10):
        print(next(fibonacci(x)))

0
1
1
2
3
5
8
13
21
34

answered Aug 11 '20 at 17:53

superb rain

5,300
2
11
25

I have no idea why yours appears to work, while mine doesn't. Why is it so different? – Sea Wolf Aug 12 '20 at 18:26
@SeaWolf Like I said, you're trying to reuse your generator iterators, trying to get something from each multiple times, but each only yields a single time. So when you ask one for a second time, it'll fail. Mine won't, as my generators yield their result over and over again, as often as they're asked to. – superb rain Aug 12 '20 at 18:29
I don't get it. How will it ever break out of the while loops? I thought generator functions basically acted as a while loop only they return the value one at a time. Nevermind I guess. I'm just hopeless. – Sea Wolf Aug 13 '20 at 04:34
@SeaWolf It never breaks out of the loops. But it yields. – superb rain Aug 13 '20 at 04:36

DarrylG · Accepted Answer · 2020-08-12T18:56:14.330

You can use memoization decorator

Reference: Can I memoize a Python generator? answer by Jasmijn

Code

from itertools import tee
from types import GeneratorType

Tee = tee([], 1)[0].__class__

def memoized(f):
    cache={}
    def ret(*args):
        if args not in cache:
            cache[args]=f(*args)
        if isinstance(cache[args], (GeneratorType, Tee)):
            # the original can't be used any more,
            # so we need to change the cache as well
            cache[args], r = tee(cache[args])
            return r
        return cache[args]
    return ret

@memoized
def Fibonacci(n):
    """0, 1, 1, 2, 3, 5, 8, 13, 21, 34
    """

    if n == 0:
        yield 0
    elif n == 1:
        yield 1
    else:
        yield next(fibonacci_mem(n - 1)) + next(fibonacci_mem(n - 2))

Timing Test

Summary

Testing n from 1 to 20 orig: original code lru: using lru cache mem: using memorization decoractor

Timing in seconds for 3 runs of each algorithm

Results show lru_cache technique provides the fastest run time (i.e. lower time)

n: 1 orig: 0.000008, lru 0.000006, mem: 0.000015
n: 10 orig: 0.000521, lru 0.000024, mem: 0.000057
n: 15 orig: 0.005718, lru 0.000013, mem: 0.000035
n: 20 orig: 0.110947, lru 0.000014, mem: 0.000040
n: 25 orig: 1.503879, lru 0.000018, mem: 0.000042

Timing Test Code

from itertools import tee
from types import GeneratorType
from functools import lru_cache

Tee = tee([], 1)[0].__class__

def memoized(f):
    cache={}
    def ret(*args):
        if args not in cache:
            cache[args]=f(*args)
        if isinstance(cache[args], (GeneratorType, Tee)):
            # the original can't be used any more,
            # so we need to change the cache as well
            cache[args], r = tee(cache[args])
            return r
        return cache[args]
    return ret
    
def fibonacci(n):
    """0, 1, 1, 2, 3, 5, 8, 13, 21, 34
    """

    if n == 0:
        yield 0
    elif n == 1:
        yield 1
    else:
        yield next(fibonacci(n - 1)) + next(fibonacci(n - 2))

@memoized
def fibonacci_mem(n):
    """0, 1, 1, 2, 3, 5, 8, 13, 21, 34
    """

    if n == 0:
        yield 0
    elif n == 1:
        yield 1
    else:
        yield next(fibonacci_mem(n - 1)) + next(fibonacci_mem(n - 2))

@lru_cache
def fibonacci_cache(n):
    """0, 1, 1, 2, 3, 5, 8, 13, 21, 34
    """

    if n == 0:
        while True:
            yield 0
    elif n == 1:
        while True:
            yield 1
    else:
        result = next(fibonacci_cache(n - 1)) + next(fibonacci_cache(n - 2))
        while True:
            yield result

from timeit import timeit

cnt = 3
for n in [1, 10, 15, 20, 25]:
  t_orig = timeit(lambda:next(fibonacci(n)), number = cnt)
  t_mem = timeit(lambda:next(fibonacci_mem(n)), number = cnt)
  t_cache = timeit(lambda:next(fibonacci_cache(n)), number = cnt)
  print(f'n: {n} orig: {t_orig:.6f}, lru {t_cache:.6f}, mem: {t_mem:.6f}')

Ah thanks this looks like what I'll need. I have no idea what you're doing though. I was hoping the standard library had a memoization function I could decorate with. I thought that's what I was doing with the @lru_cache. I'll try this tomorrow. — Sea Wolf, Aug 12 '20 at 18:18
@SeaWolf--there are standard memoization decorators like the lru_cache that normally work (I've used it successfully many times). However, a recursive generator appears to be a corner case that requires more specialized methods. Let me know if you have further questions and I'll be happy to explain. — DarrylG, Aug 12 '20 at 18:25
@superbrain--ah, you caught me. Just joking :). That's why I include my timing code so others can spot holes in my work. I corrected the error of my ways and updated my post. Happy to say it now looks like the lru_cache (your posting) provides the fastest times (which makes more sense). — DarrylG, Aug 12 '20 at 18:58
Yeah, that's one reason I include my timing code as well (when I write one). Btw, `f = fibonacci_mem(5); next(f); next(f)` of course gives an error (well, StopIteration). So `next(fibonacci_mem(...))` is pretty much the only way to use it. I think single-yield generators don't make sense, should then just be a "normal" function returning the number, used like `fibonacci_mem(...)`. — superb rain, Aug 12 '20 at 19:13

Python3 functools lru_cache RuntimeError

2 Answers2