DEV Community

Testing Different Fibonacci Generator Techniques in Python

kaelscion on December 19, 2018

Hey all! So, yesterday I posted a practice solution for finding the 200,000th number in the Fibonacci sequence as quickly and efficiently as possib...

Read full post

Raunak Ramakrishnan • Dec 20 '18

The generator code takes more memory because we are creating a list out of it in: fibs = [next(g) for _ in range(200000)]. The memory consumption is because of the list, not the generator itself.

Also, the generator example makes a list of all the 200000 fibonacci numbers whereas the iterative one just returns the 200,000th fibonacci. We can test the time for just the 200000th Fibonacci using another generator function called skip which simply skips the first n-1 results

def skip(g,n):
    for x in range(n-1):
        next(g)
    return next(g)
g = gen_fib()
print(skip(g,200000))

The generator one will be slightly slower than the iterative one but it has more versatility e.g without changing the function itself, you can return (say) the odd fibonaccis only or skip every 10 numbers or zip with other iterators. Another important point is that they are lazy i.e the results are not calculated till the generator is finally called.

On my machine, the iterative one takes 825ms while the generator takes 840ms, not that much of a performance hit.

Thank you for taking the time to profile the code. TIL about mprof :)

kaelscion • Dec 21 '18

Thanks for the clarification. I see the list comp in the original solution that I admittedly kinda scanned the first time 🙈🙈. I’ll run your solution through the test suite later today. I’ll also re-run the tests on my macbook pro which doesn’t have several VMs and a small docker environment running on it like my server does. Admittedly, the times my server got seemed totally insane even for numbers that big. But I decided that most developers here would understand that run times for the same code are relative to the system’s load at run time and wouldn’t really care about the actual figures, but the differences.

Either way, thank you so much for clarifying and for suggesting a generator in the first place. It has caused me to take another look at generators and dig a bit deeper into the Python docs surrounding them. I have a few applications in development right now that I think could benefit from being a bit leaner on memory. Seeing as I obstinately refuse to spin up DO droplets that are more than 5$, making as much use of 1GB RAM as possible is kind of a thing for me 😁. Couple that with my unreasonable love of data-structure comprehensions (they love my back just as much. I don’t care how many times they block my number. DONT TELL ME NOT TO LOVE YOU COMPREHENSIONS.....ahem) and I think generators would help. Plus I don’t access lists by index all that often seeing as I deal a lot with web automation which doesn’t allow me to get or set data in a predictable order.

Raunak Ramakrishnan • Dec 22 '18

There is a lot to love about comprehensions. The nice thing is that there are generator comprehensions also which are just a minor syntactic difference from list comprehensions.

# List of squares
sq_list = [x*x for x in range(200000)]
# generator of squares
sq_gen = (x*x for x in range(200000))

List comprehensions are very convenient but as you mentioned in your post, they have a memory cost and many times we do not need all results at once. Generator comprehensions are a nice addition for this purpose.

Comment deleted

kaelscion • Dec 20 '18

Awesome! I'm halfway through the comments and have enjoyed the discussion so far!