Вот так можно мемоизировать питоновскую функцию:
def memo_square(a, cache={}):
if a not in cache:
cache[a] = a*a
return cache[a]Приём незаслуженно малоизвестный, так что под катом мы разберём, как он работает и для чего нужен.
Сперва о том, как и почему это работает. memo_square (как и любая другая функция) — это объект класса function, у которого в числе прочих аттрибутов есть заполняемый при создании объекта кортеж memo_square.__defaults__. Сначала он содержит пустой словарь, как и указано в заголовке функции:
>>> memo_square.__defaults__
({},) __defaults__ — обычный кортеж и менять его элементы нельзя. Можно, правда, подменить весь набор дефолтных значений разом, но только на другой кортеж:
>>> def test(a=1, b=2):
... print(a, b)
...
>>> test.__defaults__
(1, 2)
>>> test()
1 2
>>> test.__defaults__ = ('Привет, ', 'Хабр')
>>> test()
Привет, Хабр
>>> test.__defaults__[1] = 'Пикабу'
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment
>>> test.__defaults__ = {0: 'Привет, ', 1: 'Пикабу'}
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: __defaults__ must be set to a tuple object
Сорян, на Пикабу эта статья не попадёт. Ну да ладно, важно не это. Важно то, что за исключением совсем уж хитрого кода func.__defaults__ создаётся один раз за время работы программы вместе со всеми своими элементами. Кортеж и его элементы не будут пересоздаваться с каждым вызовом функции, они будут использоваться до тех пор, пока функция существует. Но вот меняться, если сами элементы мутабельны, им никто не запрещает. Неумение работать с такими элементами — один из самых распространённых способов выстрелить себе в ногу в питоне. Но вообще-то сохранять значения между вызовами функции бывает довольно полезно. После нескольких вызовов memo_square.__defaults__ будет выглядеть вот так:
>>> memo_square(2)
4
>>> memo_square.__defaults__
({2: 4},)
>>> memo_square(5)
25
>>> memo_square.__defaults__
({2: 4, 5: 25},)
>>> memo_square(2)
4
>>> memo_square.__defaults__
({2: 4, 5: 25},)Если функция уже вызывалась для того же значения, то вычисление значения и, соответственно, пополнение кэша не происходит. Для квадрата выгода небольшая (строго говоря, для квадрата выгода отрицательная, потому что поиск в словаре дороже перемножения двух чисел), но для реальных дорогостоящих функций мемоизация/кэширование может быть полезно. Конечно, обеспечить её в питоне можно более чем одним способом. Вот какие у нас есть альтернативы:
- @functools.lru_cache. Декоратор из модуля functools, который запоминает последние вызовы функции. Надёжно и просто, но использует в качестве ключей все параметры функции, а значит, требует их хэшируемости и не может заметить, что два формально разных значения параметра эквивалентны. С первым требованием всё понятно, про функции от множеств, например, можно забыть. Ну или при вызове конвертировать их во frozenset. Что касается второго — у меня, например, есть функция, которая принимает на вход соединение с SQL-базой и число, и совершает некие манипуляции со связанными с этим числом данными. Соединение вполне может быть разорвано и установлено заново за время работы программы, и кэш lru_cache в таком случае слетит. Зато он умеет кэшировать только ограниченное количество вызовов (избегая утечек памяти) и прекрасно задокументирован.
- Кэшировать вне функции:
def square(a): return a**a cache = {} for x in values: if x not in cache: cache[x] = x**x print cache[x]Смысл тот же, но гораздо более громоздко. К тому же переменная cache видна вне функции, хотя ни для чего, кроме её мемоизации, не используется. Кэш при мемоизации дефолтным аргументом доступен снаружи только через
func.__defaults__, к которым довольно сложно обратиться по ошибке. - Запилить полноценный объект с кэшем и сделать функцию его методом. Хорошо с точки зрения архитектуры и тестируемости, позволяет поддерживать сколь угодно сложную логику кэширования, но ещё более громоздко за счёт бойлерплэйта в коде объекта. К тому же непонятно, что от чего наследовать и наследовать ли от чего-нибудь вообще, если мемоизируемых функций больше одной.
Главное, в чём проигрывает такой способ мемоизации — он не очень идиоматичен. Лично я, наткнувшись на это решение в первый раз, пару минут размышлял о том, что тут вообще происходит и зачем. С другой стороны, за эти пару минут я стал чуть лучше понимать, как устроены питоновские функции и их аргументы. Так что даже если вы не будете пользоваться дефолтными аргументами (для мемоизации или, например, ускорения разрешения имён), знание этого приёма всё равно полезно для любого питонщика.
Автор: Алексей Морозов
