14.10.2018 10:42
synedra 14 2900 Источник
Вот так можно мемоизировать питоновскую функцию:

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

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

Комментарии (14)


  1. pehat
    14.10.2018 13:55
    #19233819
    +1

    Приём настолько известный, что считается антипаттерном из-за своих последствий. docs.quantifiedcode.com/python-anti-patterns/correctness/mutable_default_value_as_argument.html


    1. synedra Автор
      14.10.2018 14:26
      #19233903

      Вообще-то нет. Описанный по ссылке антипаттерн возникает, если полагать, что массив/словарь инициализируется заново в каждом вызове функции:


      A programmer wrote the append function below under the assumption that the append function would return a new list every time that the function is called without the second argument. In reality this is not what happens.

      А описанный здесь приём основывается как раз на том, что значение будет общим для всех вызовов.


      1. a-tk
        14.10.2018 22:23
        #19235123
        +1

        Ещё бы спрятать его из публичного API для полного счастья.


  1. Zanak
    14.10.2018 14:30
    #19233909
    +1

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


    1. synedra Автор
      14.10.2018 14:50
      #19233949

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


      Насчёт интерфейса не согласен, потому что публичный интерфейс функции никак не отличается от некэшируемого аналога. Новые аттрибуты не появляются, старые не удаляются. У любой функции есть __defaults__, у любой функции в него можно залезть. Разве что у некэшируемой меньше вероятность найти там что-то интересное, но и тут эксплицитное обращение к function.__defaults__[0][query_value] не нормальный интерфейс, а хак вокруг хака.


      1. KennyGin
        14.10.2018 15:41
        #19234053

        Насчёт интерфейса не согласен, потому что публичный интерфейс функции никак не отличается от некэшируемого аналога


        Как же не отличается, если вводится дополнительная переменная cache, который ещё и можно инвалидировать извне функции?


  1. synedra Автор
    14.10.2018 14:49
    #19233947

    Ошибся веткой


  1. evocatus
    14.10.2018 15:47
    #19234071

    В случае с базой (как в статье) можно использовать 2 функции: одна принимает полный набор параметров (некоторые из которых нехэшируемые), а затем вызывает другую функцию с меньшим набором параметров(все хэшируемые), и она уже использует @lru_cache


    1. saluev
      15.10.2018 15:45
      #19237785

      И всё это — вместо того, чтобы улучшить архитектуру.


  1. robert_ayrapetyan
    14.10.2018 19:03
    #19234561

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


    1. synedra Автор
      14.10.2018 20:11
      #19234747

      В случае с моей базой не меняются, пока я не накачу апдейт (каковые выходят раз в несколько месяцев). Но в общем случае согласен.


  1. saluev
    14.10.2018 22:02
    #19235055
    +2

    Я бы сказал, что это заслуженно малоизвестный приём. Меняется интерфейс функции, да и код с декоратором гораздо чище.


  1. iroln
    14.10.2018 22:22
    #19235111
    +2

    @functools.lru_cache. Декоратор из модуля functools, который запоминает последние вызовы функции. Надёжно и просто, но использует в качестве ключей все параметры функции, а значит, требует их хэшируемости и не может заметить, что два формально разных значения параметра эквивалентны.

    А у вас разве как-то иначе? Вы тоже используете значения как ключи словаря, что требует, чтобы они были hashable.


    if a not in cache: 
    cache[a] = a*a


    1. synedra Автор
      15.10.2018 07:47
      #19235717

      Разница в том, что я не обязан хэшировать все параметры функции. Если я могу себе позволить игнорировать часть ключей при кэшировании (см. пример с соединением до базы), то игнорируемые ключи могут быть хэшируемыми, нехэшируемыми, гарантированно менять значение между вызовами функции, etc.