Вот так можно мемоизировать питоновскую функцию:
Приём незаслуженно малоизвестный, так что под катом мы разберём, как он работает и для чего нужен.
Сперва о том, как и почему это работает.
Сорян, на Пикабу эта статья не попадёт. Ну да ладно, важно не это. Важно то, что за исключением совсем уж хитрого кода
Если функция уже вызывалась для того же значения, то вычисление значения и, соответственно, пополнение кэша не происходит. Для квадрата выгода небольшая (строго говоря, для квадрата выгода отрицательная, потому что поиск в словаре дороже перемножения двух чисел), но для реальных дорогостоящих функций мемоизация/кэширование может быть полезно. Конечно, обеспечить её в питоне можно более чем одним способом. Вот какие у нас есть альтернативы:
Главное, в чём проигрывает такой способ мемоизации — он не очень идиоматичен. Лично я, наткнувшись на это решение в первый раз, пару минут размышлял о том, что тут вообще происходит и зачем. С другой стороны, за эти пару минут я стал чуть лучше понимать, как устроены питоновские функции и их аргументы. Так что даже если вы не будете пользоваться дефолтными аргументами (для мемоизации или, например, ускорения разрешения имён), знание этого приёма всё равно полезно для любого питонщика.
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__
, к которым довольно сложно обратиться по ошибке. - Запилить полноценный объект с кэшем и сделать функцию его методом. Хорошо с точки зрения архитектуры и тестируемости, позволяет поддерживать сколь угодно сложную логику кэширования, но ещё более громоздко за счёт бойлерплэйта в коде объекта. К тому же непонятно, что от чего наследовать и наследовать ли от чего-нибудь вообще, если мемоизируемых функций больше одной.
Главное, в чём проигрывает такой способ мемоизации — он не очень идиоматичен. Лично я, наткнувшись на это решение в первый раз, пару минут размышлял о том, что тут вообще происходит и зачем. С другой стороны, за эти пару минут я стал чуть лучше понимать, как устроены питоновские функции и их аргументы. Так что даже если вы не будете пользоваться дефолтными аргументами (для мемоизации или, например, ускорения разрешения имён), знание этого приёма всё равно полезно для любого питонщика.