DEV Community

Cover image for From 100% to 0% CPU with memoization
Jose Angel Munoz
Jose Angel Munoz

Posted on

From 100% to 0% CPU with memoization

I have followed the 30 first minutes of the freecodecamp training named Dynamic Programing for Beginners – How to Solve Coding Challenges with Memoization and Tabulation.

The first part is about programming efficiency and timing but also about infrastructure resources.

The training shows Javascript examples, but I moved to Python ♥️

The code:

def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

print('The first 50 fibonacci numbers are:')
print(','.join([str(fib(n)) for n in range(50)]))
Enter fullscreen mode Exit fullscreen mode

It takes too many CPU resources and it doesn't even finish:

Alt Text

Moving to:

def fib(n, memo={}):
    if n in memo:
        return memo[n]

    if n == 0:
        return 0

    if (n <= 2):
        return 1

    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

print('The first 50 fibonacci numbers are:')
print(','.join([str(fib(n)) for n in range(50)]))
Enter fullscreen mode Exit fullscreen mode

Takes less than a second to run and almost no CPU resorces:

real    0m0.156s
user    0m0.075s
sys     0m0.059s
Enter fullscreen mode Exit fullscreen mode

Top comments (3)

Collapse
 
joaomcteixeira profile image
João M.C. Teixeira • Edited

Great post,
Are you going to expand more on why this is the case?

Btw, going around your implementation, it can be reduced to something like:

# first definitions
i = 50  # fib number
fib = [0, 1, 1]
fiba = fib.append

# application
for i in range(2, i - 1): fiba(fib[-2] + fib[-1])
Enter fullscreen mode Exit fullscreen mode

Both have very similar performances.

Cheers,

Collapse
 
imjoseangel profile image
Jose Angel Munoz

Thank you!! The referred training from Freecodecamp goes deeper on the why and I think is quite cool to follow it. Is it what you mean?

Collapse
 
joaomcteixeira profile image
João M.C. Teixeira

Yeh. I was reading now the original post. I am definitively not an expert in dynamic programming, but definitively I use some those concepts in my daily programming even without knowing it.

Btw, is Fibonacci a good example to teach recursion, anyway?