DEV Community ๐Ÿ‘ฉโ€๐Ÿ’ป๐Ÿ‘จโ€๐Ÿ’ป

Cover image for Increase the speed of your program by  1000000 times ๐Ÿคฏ by using this technique!
Aahnik Daw
Aahnik Daw

Posted on

Increase the speed of your program by 1000000 times ๐Ÿคฏ by using this technique!

Open a jupyter notebook to follow along. The following code blocks are cells in an ipynb notebook.

Pre-requisites:

You must know how to find the n-th term of the Fibonacci sequence using recursion.

Fibonacci

Link to video.

image

from timeit import timeit
Enter fullscreen mode Exit fullscreen mode

Now lets first make the standard recursive function.

image

def fibo(n: int) -> int:
    # without memoization
    if n <= 2:
        return 1
    return fibo(n-1) + fibo(n-2)
Enter fullscreen mode Exit fullscreen mode

Now let's try to use memoization, that will reduce the time complexity to n.

image

def memo_fibo(n: int, memo: dict = {}) -> int:
    # with memoization
    if n in memo:
        return memo[n]
    if n <= 2:
        return 1
    memo[n] = memo_fibo(n-1, memo) + memo_fibo(n-2, memo)
    return memo[n]
Enter fullscreen mode Exit fullscreen mode

Let us set a value of n (the term of the Fibonacci sequence we want to find )

n = 40
Enter fullscreen mode Exit fullscreen mode

Let us execute the normal way. (Here I have used a magic command of Jupyter Notebook, to find the execution time)

%%timeit -n 1 -r 10
fibo(n)
Enter fullscreen mode Exit fullscreen mode
33.4 s ยฑ 257 ms per loop (mean ยฑ std. dev. of 10 runs, 1 loop each)
Enter fullscreen mode Exit fullscreen mode

Now let us execute the function that used the memo.

%%timeit -n 1 -r 10
memo_fibo(n)
Enter fullscreen mode Exit fullscreen mode
The slowest run took 86.52 times longer than the fastest. This could mean that an intermediate result is being cached.
3.6 ยตs ยฑ 9.59 ยตs per loop (mean ยฑ std. dev. of 10 runs, 1 loop each)
Enter fullscreen mode Exit fullscreen mode

The difference is stark. From 33.4 s to 3.6 ยตs.

Thus you see, how using memoization brings in a huge difference in time of execution.

The name 'Fibonacci' is due to a 13th-century Italian mathematician Leonardo of Pisa, who later came to be known as Fibonacci.

However, what we popularly call 'Fibonacci numbers' find their earliest mention in the 2nd century BCE work of Indian thinker Acharya Pingala.

Top comments (1)

Collapse
 
hentaichan profile image
ใƒ˜ใƒณใ‚ฟใ‚คใกใ‚ƒใ‚“

or use the closed-form expression of the fibonacci sequence for constant time complexity

๐ŸŒš Friends don't let friends browse without dark mode.

Sorry, it's true.