DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’» is a community of 963,864 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Create account Log in
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.

Oldest comments (1)

Collapse
 
hentaichan profile image
γƒ˜γƒ³γ‚Ώγ‚€γ‘γ‚ƒγ‚“

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

DEV has this feature:

Settings

Go to your customization settings to nudge your home feed to show content more relevant to your developer experience level. πŸ›