Эффективное запоминание в Python - PullRequest
Новая
       15

Эффективное запоминание в Python

16 голосов
/ 02 февраля 2012

У меня есть какая-то задача, и самая важная часть на данный момент - сделать сценарий максимально эффективным по времени. Одним из элементов, которые я пытаюсь оптимизировать, является запоминание в одной из функций.

Итак, мой вопрос: Какой из следующих 3-4 методов является наиболее эффективным / быстрым способом реализации мемофикации в Python?

Я предоставил код только в качестве примера - если один из методов более эффективен, но не в том случае, который я упомянул, пожалуйста, поделитесь тем, что вы знаете.

Решение 1 - использование изменяемой переменной из внешней области видимости

Это решение часто показывается в качестве примера памятки, но я не уверен, насколько оно эффективно. Я слышал, что использование глобальных переменных (в данном случае это переменная из внешней, а не глобальной области видимости) менее эффективно. 

def main():
    memo = {}
    def power_div(n):
        try:
            return memo[n]
        except (KeyError):
            memo[n] = (n ** 2) % 4  # example expression, should not matter
            return memo[n]
    # extensive usage of power_div() here

Решение 2 - использование изменяемого по умолчанию аргумента

Я нашел где-то, что в прошлом переменные аргументы по умолчанию использовались для передачи переменных из внешней области видимости, когда Python сначала искал переменную в локальной области, а затем в глобальной области, пропуская нелокальную область (в данном случае область действия внутри функции main()). Поскольку аргумент по умолчанию инициализируется только в то время, когда определена функция и доступен только внутри внутренней функции, может быть, это более эффективно? 

def main():
    def power_div(n, memo={}):
        try:
            return memo[n]
        except (KeyError):
            memo[n] = (n ** 2) % 4  # example expression, should not matter
            return memo[n]
    # extensive usage of power_div() here

Или, может быть, следующая версия (фактически являющаяся комбинацией решений 1 и 2) более эффективна? 

def main():
    memo = {}
    def power_div(n, memo=memo):
        try:
            return memo[n]
        except (KeyError):
            memo[n] = (n ** 2) % 4  # example expression, should not matter
            return memo[n]
    # extensive usage of power_div() here

Решение 3 - атрибут функции

Это еще один довольно распространенный пример запоминания в Python - объект запоминания хранится как атрибут самой функции. 

def main():
    def power_div(n):
        memo = power_div.memo
        try:
            return memo[n]
        except (KeyError):
            memo[n] = (n ** 2) % 4  # example expression, should not matter
            return memo[n]
    # extensive usage of power_div() here

Краткое описание

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

Я знаю, что есть и другие решения для запоминания (такие как Memoize декоратор ), но мне трудно поверить, что это более эффективное решение, чем перечисленное выше. Поправь меня, если я ошибаюсь.

Заранее спасибо.

Ответы [ 2 ]

14 голосов
/ 02 февраля 2012

Различные стили доступа к переменной уже рассчитаны и сравнены по адресу: http://code.activestate.com/recipes/577834-compare-speeds-of-different-kinds-of-access-to-var Вот краткое резюме: локальный доступ превосходит нелокальные (вложенные области), которые превосходят глобальный доступ (область видимости модуля), который опережает доступ к встроенным функциям.

Ваше решение № 2 (с локальным доступом) должно победить. Решение № 3 имеет поиск с медленными точками (который требует поиска по словарю). Решение № 1 использует нелокальный (вложенный объем) доступ, который использует переменные ячейки (быстрее, чем поиск в dict, но медленнее, чем локальные).

Также обратите внимание, что исключительный класс KeyError является глобальным поиском и может быть ускорен путем его локализации. Вы можете заменить try / кроме полностью и использовать вместо него memo.get(n, sentinel). И даже это можно ускорить, используя связанный метод. Конечно, ваше самое простое прибавление в скорости может быть получено только после попытки pypy : -)

Короче говоря, есть много способов настроить этот код. Просто убедитесь, что оно того стоит.

2 голосов
/ 09 декабря 2014

В интересах людей, которые сталкиваются с этим вопросом, когда ищут способ сделать памятку в python, я рекомендую fastcache .

Он работает на Python 2 и 3, работает быстрее, чем любой из методов, описанных выше, и дает возможность ограничить размер кэша, чтобы он случайно не стал слишком большим: 

from fastcache import clru_cache

@clru_cache(maxsize=128, typed=False)
def foo(cat_1, cat_2, cat_3):
    return cat_1 + cat_2 + cat_3

Установить fastcache просто, используя pip: 

pip install fastcache

или conda: 

conda install fastcache
...