Python: Memoization или кеш результатов вычислений

Memoize (или мемоизация)- это паттерн оптимизации вычислений. Он очень маленький и простой, но может оказаться очень полезным в некоторых случаях:

def memoized(f):
    memory = {}
    def wrapper(*args, **kwargs):
        key = (tuple(args), hash(tuple(sorted(kwargs.items()))))
        if not key in memory:
            memory[key] = f(*args, **kwargs)
        return memory[key]
    return wrapper

Что он нам дает?

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

Посмотрим как декоратор memoized повлияет на всем известную рекурсивную функцию вычисления факториала. К слову, никогда не используйте рекурсию для вычисления факториала, здесь она приведена только как «классика жанра». Итак:

@memoized
def factorial (n):
    print "factorial (%d)" % n
    if n is 0:
        return 1
    else:
        return factorial(n - 1) * n

Попробуем вычислить несколько факториалов:

>>> factorial(3)
factorial (3)
factorial (2)
factorial (1)
factorial (0)
6

>>> factorial(7)
factorial (7)
factorial (6)
factorial (5)
factorial (4)
5040

>>> factorial(6)
720

Как видим, повторных вычислений не производится: каждый факториал считается только один раз, результат запоминается и возвращается при повторном запросе. Такой подход позволяет значительно сэкономить вычислительные ресурсы, особенно, в случае медленных алгоритмов.

Спасибо, что читаете!

Запись опубликована в рубрике На заметку с метками , , . Добавьте в закладки постоянную ссылку.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *