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.

Answer 1

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}')