Python
Programming
14 October 2018

Мемоизация дефолтным kwarg в Python

Вот так можно мемоизировать питоновскую функцию:

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__, к которым довольно сложно обратиться по ошибке.
  • Запилить полноценный объект с кэшем и сделать функцию его методом. Хорошо с точки зрения архитектуры и тестируемости, позволяет поддерживать сколь угодно сложную логику кэширования, но ещё более громоздко за счёт бойлерплэйта в коде объекта. К тому же непонятно, что от чего наследовать и наследовать ли от чего-нибудь вообще, если мемоизируемых функций больше одной.

Главное, в чём проигрывает такой способ мемоизации — он не очень идиоматичен. Лично я, наткнувшись на это решение в первый раз, пару минут размышлял о том, что тут вообще происходит и зачем. С другой стороны, за эти пару минут я стал чуть лучше понимать, как устроены питоновские функции и их аргументы. Так что даже если вы не будете пользоваться дефолтными аргументами (для мемоизации или, например, ускорения разрешения имён), знание этого приёма всё равно полезно для любого питонщика.

+6
6k 54
Comments 14
Top of the day