Performance of dynamic Fibonacci generator and dead rabbits

Question

I would like to improve my code style and its efficiency.

I'm just moving beyond the standard recursive approach to a lot of simple algorithms.

This post has two code snippets with slightly different but related problems. They're both in Python.

---

The first snippet is just to produce Fibonacci numbers. I think I've done this with O(n) time complexity. Do you have suggestions on how to make my code more readable and more efficient?

# Using bottom-up dynamic programming approach, define all fibonacci numbers
def fib(num):

    # First and second generations are trivial
    if num == 1 or num == 2:
        return 1

    # If not trivial, keep going:

    # Set up array
    allGenerations = [None] * (num + 1)
    allGenerations[1] = 1
    allGenerations[2] = 1

    # Fill in the array until you reach the given generation
    for i in range(3, num+1):
        allGenerations[i] = allGenerations[i - 1] + allGenerations[i - 2]
    return allGenerations[num]

---

The second snippet tries to use what I learned from the first snippet to solve a related problem. The numbers represent living rabbits. If rabbits lived forever, their population sizes would follow a fibonacci sequence. In this alteration, rabbits live for a fixed amount of time (input m). Newborn rabbits keep living, adult rabbits produce themselves and one offspring, and rabbits that are about to die just produce one offspring (see http://rosalind.info/problems/fibd/).

I'm not sure how to analyze the time complexity of this problem, but it seems high? So questions are (1) What is the time complexity of my solution? and (2) How can I improve efficiency and readability?

def rabbit(n, m):
    # First two generations are trivial
    if n == 1 or n == 2:
        return 1

    # If not trivial, keep going:

    # Set up array
    allGenerations = [None] * (n + 1)

    # Each index in the generations will be another array whose indicies represent the ages of the rabbits in that generation
    allGenerations[1] = [1]
    allGenerations[2] = [0, 1]

    # Bottom-up filling of generations
    for i in range(3, n + 1):
        # Initalize answer as a list of number of rabbits at each age
        answer = [None] * (i)

        # Get the previous generation
        previous = allGenerations[i - 1]

        # Initalize the number of newborns
        newborns = 0

        # From age 1 (first reproductive age) to either age at death 
        # or the oldest in the previous generation (whichever comes first), produce newborn rabbits
        for j in range(1, min(m, len(previous))):
            newborns += previous[j]

        # The 0-index of the answer represents newborn rabbits
        answer[0] = newborns

        # Move every element in the previous generation up one index into the new generation  
        for k in range(0, len(previous)):
            answer[k + 1] = previous[k]

        # Put this answer into the list of all answers
        allGenerations[i] = answer

    # Return all living rabbits
    return sum(answer[:m])

# Some testcases

import unittest

class mainTest(unittest.TestCase):
    def test(self):
        self.assertEqual(rabbit(1, 3), 1)
        self.assertEqual(rabbit(2, 3), 1)
        self.assertEqual(rabbit(3, 3), 2)
        self.assertEqual(rabbit(4, 3), 2)
        self.assertEqual(rabbit(5, 3), 3)
        self.assertEqual(rabbit(6, 3), 4)
        self.assertEqual(rabbit(7, 3), 5)
        self.assertEqual(rabbit(25, 31), 75025)
        self.assertEqual(rabbit(30, 30), 832040)
        self.assertEqual(rabbit(35, 29), 9227437)
        self.assertEqual(rabbit(40, 28), 102333267)
        self.assertEqual(rabbit(45, 27), 1134880302)

if __name__ == '__main__':
    unittest.main(argv=[''], exit = False)

Answer 1

naming variable

naming the variables clearly and correctly goes a long way in documenting your code. n and m are not clear. I would name them generation and max_age or something

generators

For the simple fibonacci series, instead of storing everything in lists, only store what you need, and yield the results instead of returning the complete list.

And instead of keeping track of how far you are in your list, use an endless generator to yield a stream of fibonacci numbers, and the nth itertools recipe

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

can be found in almost all python handbooks

from itertools import islice
def nth(iterable, n, default=None):
    """
    Returns the nth item or a default value
    https://docs.python.org/3/library/itertools.html#itertools-recipes
    """
    return next(islice(iterable, n, None), default)

def fib_n(n):
    return nth(fib(), n)

dying rabbits

The same approach can be used for the second example, but here you can use a double ended queue with a fixed length instead of a tuple.

def rabbits(max_age):
    generations = deque(islice(fib(1,1), max_age), maxlen=max_age)
    while True:
        yield generations[0]
        new_borns = generations[-1]
        generations.append(sum(generations) - new_borns)

def rabbit(generation, max_age):
    return nth(rabbits(max_age), generation - 1)

The generation - 1 is to account for python's 0-indexing

dynamic solution:

another approach, using recursion and memoization is more in line with dynamic programming.

from functools import lru_cache
@lru_cache(None)
def rabbit_dynamic(generation, max_age):
#     print(f'calling rabbit_dynamic({generation}, {max_age})')
    generation -= 1 # 0-indexing
    if generation < 1:
        return 0
    if generation < max_age:
        return nth(fib(1,1), generation)
    return sum(rabbit_dynamic(generation - i, max_age) for i in range(1, max_age)) 

timings

since you wondered about performance:

%timeit rabbit_OP(45, 27)

183 µs ± 8.68 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

%timeit rabbit(45, 27)

40.6 µs ± 3.1 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

so a 4.5 time speedup by dropping the intermediary lists

rabbit_dynamic.cache_clear()
%timeit -n 1 -r 1 rabbit_dynamic(45,27)

150 µs ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)

%timeit rabbit_dynamic.cache_clear(); rabbit_dynamic(45,27)

155 µs ± 7.51 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

so about the same as your implementation

cache

The caching has a huge influence:

rabbit_dynamic.cache_info()

CacheInfo(hits=399, misses=44, maxsize=None, currsize=44)

without caching:

@lru_cache(0)
def rabbit_dynamic_zero_cache(generation, max_age):
#     print(f'calling rabbit_dynamic({generation}, {max_age})')
    generation -= 1
    if generation < 0:
        return 0
    if generation< max_age:    
        return nth(fib(1,1), generation)    
    return sum(rabbit_dynamic_zero_cache(generation - i, max_age) for i in range(1, max_age)) 

%timeit -n 1 -r 1 rabbit_dynamic_zero_cache(45, 27)    

179 ms ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)

so about 1000 times slower (about 125ms without any lru_cache)

rabbit_dynamic_zero_cache.cache_info()    

CacheInfo(hits=0, misses=67185, maxsize=0, currsize=0)

because of the repeated asking for the same answer (67k function calls instead of 443)

Answer 2

With regard to your time complexity:

With your calculation of the nth Fibonacci number, you could do it in \$O(1)\$ time by using the relation:

$$F_n = \left\lfloor \frac{\varphi^n}{\sqrt{5}} + \frac{1}{2} \right\rfloor$$

So the 484th Fibonacci number would be equal to:

$$\left\lfloor \frac{\varphi^{484}}{\sqrt{5}} + \frac{1}{2} \right\rfloor \approx 6.317 \times 10^{100}$$

If you do not want to use the floor function, you can achieve the exact same result by manipulating the equation and using the nearest-integer function: \$\left[\frac{\varphi^n}{\sqrt5}\right]\$

This will speed up your program if you intend on calculating very large Fibonacci numbers.

Note: when calculating \$\varphi^n\$, use math.pow(x,y) because it uses floating point exponentiation and is always \$O(1)\$, whereas pow(x,y) and x**y can vary. For calculating \$\varphi\$ itself, there are many methods, here is an example.

Answer 3

The loop

    # Move every element in the previous generation up one index into the new generation  
    for k in range(0, len(previous)):
        answer[k + 1] = previous[k]

makes the next allGenerations list one element longer than the previous one. After n iterations you have lists of lengths 1, 2, ... n, making them \$O(n^2)\$ total. Just populating them all has a quadratic time complexity.

The good news is you don't need to make separate lists for each iteration. Do not index rabbits with age, index them with the birthdate instead. Once the first m generations are populated, the rest is just

    for date in range(m, n):
        rabbits.append(sum(rabbits[(date - m):])

with \$O(nm)\$ time complexity.

The next step is to notice that sum is also redundant. The next bunch of newborns is produced by last bunch of newborns, plus all the breeders of the last round, minus those who'd passed away. The breeders of the last round would obviously produce as much as they did at the last round, which is exactly the number of last round newborns:

        rabbits.append(2*rabbits[-1] - rabbits[date - m])

with \$O(n)\$ time complexity.

---

The problem statement asks for all numbers. Your functions however only return the final tally. The first snippet should return allGenerations rather than allGenerations[n].