Иногда мы реализуем некоторые функции на Python, выполнение которых может занять много времени, особенно рекурсивные функции.

Возьмем пример функции Фибоначчи:

def fib(n):
    if n < 2:
        return n
    else:
        return fib(n - 1) + fib(n - 2)
print(fib(10))

Чтобы иметь возможность измерить выполнение нашей функции, мы будем использовать perf_counter из библиотеки времени:

from time import perf_counter
def fib(n):
    if n < 2:
        return n
    else:
        return fib(n - 1) + fib(n - 2)
start = perf_counter()
print(fib(10))
end = perf_counter()
print(f"{end - start} seconds")

Теперь давайте проведем несколько тестов со следующими входными данными: 5, 10, 20, 30, 40:

fib(5):
5
0.0004687000182457268 seconds
fib(10):
55
0.0004478000046219677 seconds
fib(20):
6765
0.0028874999843537807 seconds
fib(30):
832040
0.24202609999338165 seconds
fib(40):
102334155
34.25253349999548 seconds

Как видите, если мы продолжим, это займет очень много времени.

И тут на помощь приходит мемоизация, и нет, это не опечатка. Это называется мемоизация (не запоминание).

Memoization происходит от латинского Memorandum, что означает помнить.

По сути, мемоизация используется для кэширования известных выходных данных, которые мы будем использовать позже, чтобы функция запускалась с уникальным вводом только один раз!

Это удобно, особенно если мы используем рекурсивные функции, потому что они зависят от предыдущего вывода для завершения своего выполнения.

Теперь давайте приступим к реализации этой мемоизации, не так ли? Не волнуйтесь, это очень просто.

Добавим несколько библиотек:

from functools import wraps
from time import perf_counter
def fib(n):
    if n < 2:
        return n
    else:
        return fib(n - 1) + fib(n - 2)
start = perf_counter()
print(fib(10))
end = perf_counter()
print(f"{end - start} seconds")

Затем давайте приступим к реализации декоратора memoize, который мы поместим поверх нашей функции Фибоначчи:

from functools import wraps
from time import perf_counter
def memoize(func):
    cache = {}
    @wraps(func)
    def wrapper(*args, **kwargs):
        key = str(args) + str(kwargs)
        if key not in cache:
            cache[key] = func(*args, **kwargs)
        
        return cache[key]
    return wrapper

@memoize
def fib(n):
    if n < 2:
        return n
    else:
        return fib(n - 1) + fib(n - 2)
start = perf_counter()
print(fib(10))
end = perf_counter()
print(f"{end - start} seconds")

Вот и все!

Давайте теперь объясним добавленный код.

  • def memoize(): Функция memoize имеет функцию в качестве параметра (func), потому что это декоратор.
  • кеш. Начнем с создания переменной кеша. Эта переменная говорит сама за себя, она будет хранить любые вычисления или результаты, которые уже были сделаны, поэтому мы можем использовать ее повторно и сэкономить много памяти и процессорного времени.
  • wrapper(*args, **kwargs): немного выходит за рамки, поэтому я приберегу его для отдельного урока о том, как работают декораторы.
  • key: если ключ (который мы получили из аргумента функции) еще не существует в нашем кеше, мы добавляем его, чтобы мы могли использовать его позже (ключи в этом случае являются результатами функций, которые мы использовали , используя этот декоратор).

Можем ли мы сейчас провести еще один тест?

Давайте поместим те же входные данные, которые мы использовали ранее, и, возможно, добавим больше, потому что мы можем:

fib(5):
5
0.00036979999276809394 seconds
fib(10):
55
0.0003853000234812498 seconds
fib(20):
6765
0.0003789999755099416 seconds
fib(30):
832040
0.0004702000005636364 seconds
fib(40):
102334155
0.0005090999766252935 seconds
# Continuing just for the heck of it
fib(50):
12586269025
0.0005879999953322113 seconds
fib(100):
354224848179261915075
0.0008097999962046742 seconds

Вы что-то заметили? fib(40) выполнялся за 0,0005 секунды (запоминание) против 34,2525 секунды (без запоминания).

Это в 68504 раза быстрее!

Кроме того, вы могли заметить, что продолжительность почти не изменилась, а иногда даже уменьшалась, и это из-за используемого нами кеша.

Большое спасибо за то, что читаете мой контент и следите за мной в среде. Пожалуйста, поделитесь этим со своими друзьями и коллегами, и не стесняйтесь подписываться на меня и отвечать на эту статью, если у вас есть какие-либо вопросы!

Всем удачного программирования!!
K.B.

Если вам нужна работа с Джанго, смело нанимайте меня на https://business.fiverr.com/share/YW9pAz.