Skip to content

Instantly share code, notes, and snippets.

@Diapolo10
Last active December 15, 2021 23:45
Show Gist options
  • Save Diapolo10/e9ea58cb8fe35f6c2da51d623d86bab1 to your computer and use it in GitHub Desktop.
Save Diapolo10/e9ea58cb8fe35f6c2da51d623d86bab1 to your computer and use it in GitHub Desktop.
Order N Fibonacci sequence generator
from collections import deque
from typing import Generator
import warnings
def n_fibonacci(n: int = 2) -> Generator[int, None, None]:
"""
Returns a generator that yields the values of a Fibonacci sequence of a given 'base'.
When `n == 0`, the returned sequence simplifies to an infinite sequence of `0`.
When `n == 1`, the returned sequence simplifies to an infinite sequence of `1`.
When `n == 2`, the returned sequence is a normal Fibonacci sequence.
When `n == 3`, the returned sequence is a Tribonacci sequence.
For higher values of `n`, the respective "N-bonacci" sequence is returned.
The value of `n` is not upper-bound by the function.
Functionality based on: https://oeis.org/wiki/N-bonacci_numbers
Examples:
fib = n_fibonacci()
print([next(fib) for _ in range(10)]) # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
trib = n_fibonacci(3)
print([next(trib) for _ in range(10)]) # [0, 0, 1, 1, 2, 4, 7, 13, 24, 44]
"""
if n < 0:
raise ValueError("Fibonacci base cannot be negative")
elif n < 2:
warnings.warn(f"Fibonacci sequence simplified to an infinite sequence of `{n}`", UserWarning)
vals = [0 for _ in range(n-1)] + [1 if n else 0]
while True:
yield vals[0]
vals[:n-1], vals[n-1] = vals[1:], sum(vals)
def deque_n_fibonacci(n: int = 2) -> Generator[int, None, None]:
"""
A variant of n_fibonacci that uses a deque instead of a list
"""
if n < 0:
raise ValueError("Fibonacci base cannot be negative")
elif n < 2:
warnings.warn(f"Fibonacci sequence simplified to an infinite sequence of `{n}`", UserWarning)
vals = deque([0 for _ in range(n-1)] + [1 if n else 0], maxlen=n)
while True:
yield vals[0]
vals.append(sum(vals))
@Diapolo10
Copy link
Author

Based on quick benchmarks, the deque version is between 15-30% faster for the first 1000 values, depending on the size of n. At around 100000 values, the original version performs better. range was used with zip to limit the number of values generated, and list to force the lazy evaluation to be run.

In [2]: %timeit list(zip(n_fibonacci(2), range(1000)))
303 µs ± 2.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [3]: %timeit list(zip(deque_n_fibonacci(2), range(1000)))
207 µs ± 5.15 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [4]: %timeit list(zip(n_fibonacci(3), range(1000)))
338 µs ± 2.22 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [5]: %timeit list(zip(deque_n_fibonacci(3), range(1000)))
236 µs ± 3.23 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [6]: %timeit list(zip(n_fibonacci(3), range(10000)))
8.54 ms ± 456 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [7]: %timeit list(zip(deque_n_fibonacci(3), range(10000)))
7.2 ms ± 41 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [8]: %timeit list(zip(n_fibonacci(3), range(100000)))
551 ms ± 20.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [9]: %timeit list(zip(deque_n_fibonacci(3), range(100000)))
502 ms ± 22.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [10]: %timeit list(zip(n_fibonacci(9), range(1000)))
528 µs ± 5.72 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [11]: %timeit list(zip(deque_n_fibonacci(9), range(1000)))
408 µs ± 6.25 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [12]: %timeit list(zip(n_fibonacci(15), range(1000)))
706 µs ± 11 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [13]: %timeit list(zip(deque_n_fibonacci(15), range(1000)))
568 µs ± 10.4 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [14]: %timeit list(zip(n_fibonacci(30), range(1000)))
1.13 ms ± 24.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [15]: %timeit list(zip(deque_n_fibonacci(30), range(1000)))
965 µs ± 25.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment