[PYTHON] Learned memoization

Preface

Recently, I have had several opportunities to undergo internship selection and final selection for Web companies. There was a coding test in the selection of many companies, and since I studied a little this time, I will leave it as a memorandum as a practice of output.

This time about ** memoization **.

What is memoization?

Simply put, it's a technique for speeding up programs.

It is a technique like "When the same function is called many times in recursive processing etc., the calculation result is recorded in the cache (memo), and the cached value is returned for the previously calculated one".

Implementation example

This time, as an implementation example, I will introduce a program that asks for ** what is the nth number in the Fibonacci sequence **.

Fibonacci sequence

a_1=a_2=1 \\
a_n=a_{n−1}+a_{n−2}\\
(1\leqq n)

The Fibonacci sequence can be expressed as a recurrence formula as shown above. I won't go into detail, but the first two terms return 1, and the rest of the terms return the sum of the previous two terms.

Implemented with just recursion

def fibonacci(n):
    if n == 1 or n == 2:
        return 1

    return fibonacci(n - 2) + fibonacci(n - 1)

print(fibonacci(6))  # 8

Implemented by memoization

memo = {1: 1, 2: 1}

def fibonacci(n):
 If n is recorded in # memo, its value is returned.
    if n in memo:
        return memo[n]

 # If not, write it down and return its value
    memo[n] = fibonacci(n - 2) + fibonacci(n - 1)
    return memo[n]

print(fibonacci(6))  # 8

image

When implemented by just recursion, n = 6 is called fibonacci (4) twice and fibonacci (3) three times. You can imagine that as n gets bigger and bigger, the number of calculations increases. If you make a memo, you do not have to calculate the one calculated once from the second time onward, so you can greatly reduce the number of calculations.

Summary

--Memoization is one of the techniques for speeding up programs. --The larger n, the more effective