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

#python #programming #tutorial #codequality

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?

Read next

mdarifulhaque profile image

1106. Parsing A Boolean Expression

MD ARIFUL HAQUE -

dm8ry profile image

Resolving Docker Push Errors: "Denied: Requested Access to the Resource is Denied"

Dmitry Romanoff -

arhamrumi profile image

Installing Node.js on Windows: A Complete Tutorial

Arham Rumi -

spwoodcock profile image

FastAPI, Pydantic, Psycopg3: the holy trinity for Python web APIs

Sam -