Memoization в Python

Memoization – свойство функций сохранять (кешировать) результаты вычислений, дабы не вычислять в последствии повторно.

Эта технология оптимизации позволят достичь прироста скорости работы за счет потерь в свободной памяти.

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

Для python декоратор для функции будет выглядеть следующим образом:

import cPickle
def memoized(func):
    memory = {}
    def memo(*args,**kwargs):
       hash = cPickle.dumps((args, sorted(kwargs.iteritems())))
       if hash not in memory:
           memory[hash] = func(*args,**kwargs)
       return memory[hash]
    return memo

Далее, нам достаточно объявить bigfunc как

@memoized
def bigfunc(…):
…

Или переопределить, если она уже объявлена:

bigfunc = memoized(bigfunc)

Декоратор, объявленный в начале статьи, работает только с пиклезуемыми объектами. Если ваша функция работает с непиклезуемыми объектами – вы можете заменить

hash = cPickle.dumps((args, sorted(kwargs.iteritems())))

на

hash = (tuple(args), frozenset(kwargs.items())

но вы потеряете возможность работы с mutable объектами.

Декоратор можно легко модифицировать, для ограничения количества закешированных элементов.