Что такое памятка и как я могу использовать ее в Python?

378

Я только начал Python, и я понятия не имею, что такое памятка и как ее использовать. Кроме того, могу ли я иметь упрощенный пример?

blur959
источник
215
Когда второе предложение соответствующей статьи в Википедии содержит фразу «взаимно-рекурсивный анализ спуска [1] в общем алгоритме синтаксического анализа сверху вниз [2] [3], который учитывает неоднозначность и левую рекурсию в полиномиальном времени и пространстве», я думаю, вполне уместно спросить ТАК, что происходит.
бестолковый
10
@Clueless: этой фразе предшествует «Мемоизация также использовалась в других контекстах (и для других целей, кроме увеличения скорости), например, в». Так что это просто список примеров (и их не нужно понимать); это не часть объяснения запоминания.
ShreevatsaR
1
@StefanGruenwald Эта ссылка мертва. Можете ли вы найти обновление?
JS.
2
Новая ссылка на файл PDF, так как pycogsci.info не работает: people.ucsc.edu/~abrsvn/NLTK_parsing_demos.pdf
Стефан Грюнвальд,
4
@Clueless, в статье на самом деле говорится « простой взаимно-рекурсивный анализ спуска [1] в общем алгоритме синтаксического анализа сверху вниз [2] [3], который учитывает неоднозначность и левую рекурсию в полиномиальном времени и пространстве». Вы пропустили простое , что, очевидно, делает этот пример намного понятнее :).
Studgeek

Ответы:

353

Под «запоминанием» фактически понимается запоминание («памятка» → «меморандум» → запоминание) результатов вызовов метода на основе входных данных метода и затем возвращение запомненного результата, а не его повторный расчет. Вы можете думать об этом как о кеше для результатов метода. Для получения дополнительной информации см. Стр. 387 для определения в разделе Введение в алгоритмы (3e), Cormen et al.

Простой пример вычисления факториалов с использованием мемоизации в Python будет выглядеть примерно так:

factorial_memo = {}
def factorial(k):
    if k < 2: return 1
    if k not in factorial_memo:
        factorial_memo[k] = k * factorial(k-1)
    return factorial_memo[k]

Вы можете усложнить задачу и включить процесс запоминания в класс:

class Memoize:
    def __init__(self, f):
        self.f = f
        self.memo = {}
    def __call__(self, *args):
        if not args in self.memo:
            self.memo[args] = self.f(*args)
        #Warning: You may wish to do a deepcopy here if returning objects
        return self.memo[args]

Затем:

def factorial(k):
    if k < 2: return 1
    return k * factorial(k - 1)

factorial = Memoize(factorial)

В Python 2.4 была добавлена функция, известная как « декораторы », которая позволяет вам просто написать следующее, чтобы выполнить то же самое:

@Memoize
def factorial(k):
    if k < 2: return 1
    return k * factorial(k - 1)

В библиотеке Python Decorator есть похожий декоратор, memoizedкоторый называется несколько более надежным, чем Memoizeкласс, показанный здесь.

Ясон
источник
2
Спасибо за это предложение. Класс Memoize - это элегантное решение, которое можно легко применить к существующему коду без особого рефакторинга.
Капитан Лептон
10
Решение класса Memoize содержит ошибки, оно не будет работать так же, как factorial_memo, потому что factorialвнутренняя часть def factorialвсе еще вызывает старую команду unmemoize factorial.
Адамсмит
9
Кстати, вы также можете написать if k not in factorial_memo:, что читает лучше, чем if not k in factorial_memo:.
ShreevatsaR
5
Должен действительно сделать это в качестве декоратора.
Эмлин О'Реган,
3
@ durden2.0 Я знаю, что это старый комментарий, но argsэто кортеж. def some_function(*args)делает аргументы кортежем
Адам Смит
232

Новое в Python 3.2 есть functools.lru_cache. По умолчанию, он кэширует только 128 недавно использованные звонков, но вы можете установить , maxsizeчтобы Noneуказать , что кэш никогда не должен истекать:

import functools

@functools.lru_cache(maxsize=None)
def fib(num):
    if num < 2:
        return num
    else:
        return fib(num-1) + fib(num-2)

Эта функция сама по себе очень медленная, попробуйте, fib(36)и вам придется подождать около десяти секунд.

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

Флимм
источник
2
Пробовал fib (1000), получил RecursionError: максимальная глубина рекурсии превышена по сравнению
X Æ A-12
5
@Andyk Предел рекурсии Py3 по умолчанию равен 1000. При первом fibвызове он должен вернуться к базовому сценарию, прежде чем произойдет запоминание. Итак, ваше поведение примерно ожидаемо.
Quelklef
1
Если я не ошибаюсь, он кешируется только до тех пор, пока процесс не убит, верно? Или он кешируется независимо от того, убит ли процесс? Например, скажем, я перезагружаю свою систему - будут ли кэшированные результаты все еще кэшироваться?
Kristada673
1
@ Kristada673 Да, он хранится в памяти процесса, а не на диске.
Flimm
2
Обратите внимание, что это ускоряет даже первый запуск функции, поскольку она является рекурсивной функцией и кэширует свои промежуточные результаты. Возможно, было бы хорошо проиллюстрировать нерекурсивную функцию, которая по своей сути медленная, чтобы сделать ее более понятной для чайников, как я. : D
эндолиты
61

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

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

memoised_function = memoise(actual_function)

или выраженный как декоратор

@memoise
def actual_function(arg1, arg2):
   #body
Нуфал Ибрагим
источник
18

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

Вот пример:

def doSomeExpensiveCalculation(self, input):
    if input not in self.cache:
        <do expensive calculation>
        self.cache[input] = result
    return self.cache[input]

Более полное описание можно найти в записи в Википедии о запоминании .

Брайан Оукли
источник
Хм, теперь, если бы это был правильный Python, он бы качался, но, похоже, это не так ... ладно, значит, «кеш» - это не диктат? Потому что, если это так, оно должно быть if input not in self.cache и self.cache[input] ( has_keyустарело, поскольку ... в начале серии 2.x, если не 2.0, self.cache(index)никогда не было верным. IIRC)
Юрген А. Эрхард
15

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

def fact(n):
    if not hasattr(fact, 'mem'):
        fact.mem = {1: 1}
    if not n in fact.mem:
        fact.mem[n] = n * fact(n - 1)
    return fact.mem[n]
Карел Кубат
источник
Это кажется очень дорогой идеей. Для каждого n он кэширует результаты не только для n, но и для 2 ... n-1.
Codeforester,
15

Я нашел это чрезвычайно полезным

def memoize(function):
    from functools import wraps

    memo = {}

    @wraps(function)
    def wrapper(*args):
        if args in memo:
            return memo[args]
        else:
            rv = function(*args)
            memo[args] = rv
            return rv
    return wrapper


@memoize
def fibonacci(n):
    if n < 2: return n
    return fibonacci(n - 1) + fibonacci(n - 2)

fibonacci(25)
mr.bjerre
источник
Посмотрите docs.python.org/3/library/functools.html#functools.wraps, чтобы узнать, почему следует использовать functools.wraps.
Аниспатель
1
Нужно ли вручную очищать, memoчтобы освободить память?
Вся идея заключается в том, что результаты хранятся внутри заметки в течение сеанса. Т.е. ничего не очищается как есть
mr.bjerre
6

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

см. http://scriptbucket.wordpress.com/2012/12/11/introduction-to-memoization/

Пример запоминания Фибоначчи в Python:

fibcache = {}
def fib(num):
    if num in fibcache:
        return fibcache[num]
    else:
        fibcache[num] = num if num < 2 else fib(num-1) + fib(num-2)
        return fibcache[num]
Ромейн Картер
источник
2
Для большей производительности предварительно запишите в ваш fibcache первые несколько известных значений, а затем вы можете использовать дополнительную логику для обработки их из «горячего пути» кода.
jkflying
5

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

Conal
источник
5

Ну, я должен ответить на первую часть в первую очередь: что такое запоминание?

Это просто способ обменять память на время. Подумайте о таблице умножения .

Использование изменяемого объекта в качестве значения по умолчанию в Python обычно считается плохим. Но если использовать его с умом, это может быть полезно для реализации memoization.

Вот пример, адаптированный из http://docs.python.org/2/faq/design.html#why-are-default-values-shared-between-objects

Используя изменяемый dictв определении функции, промежуточные вычисленные результаты могут быть кэшированы (например, при вычислении factorial(10)после вычисления factorial(9)мы можем повторно использовать все промежуточные результаты)

def factorial(n, _cache={1:1}):    
    try:            
        return _cache[n]           
    except IndexError:
        _cache[n] = factorial(n-1)*n
        return _cache[n]
yegle
источник
4

Вот решение, которое будет работать с аргументами типа list или dict без нытья:

def memoize(fn):
    """returns a memoized version of any function that can be called
    with the same list of arguments.
    Usage: foo = memoize(foo)"""

    def handle_item(x):
        if isinstance(x, dict):
            return make_tuple(sorted(x.items()))
        elif hasattr(x, '__iter__'):
            return make_tuple(x)
        else:
            return x

    def make_tuple(L):
        return tuple(handle_item(x) for x in L)

    def foo(*args, **kwargs):
        items_cache = make_tuple(sorted(kwargs.items()))
        args_cache = make_tuple(args)
        if (args_cache, items_cache) not in foo.past_calls:
            foo.past_calls[(args_cache, items_cache)] = fn(*args,**kwargs)
        return foo.past_calls[(args_cache, items_cache)]
    foo.past_calls = {}
    foo.__name__ = 'memoized_' + fn.__name__
    return foo

Обратите внимание, что этот подход можно естественным образом распространить на любой объект, реализовав собственную хеш-функцию в качестве особого случая в handle_item. Например, чтобы этот подход работал для функции, которая принимает набор в качестве входного аргумента, вы можете добавить к handle_item:

if is_instance(x, set):
    return make_tuple(sorted(list(x)))
RussellStewart
источник
1
Хорошая попытка. Без скуля listаргумент [1, 2, 3]может ошибочно считаться другим setаргументом со значением {1, 2, 3}. Кроме того, наборы неупорядочены, как словари, поэтому они также должны быть sorted(). Также обратите внимание, что рекурсивный аргумент структуры данных может вызвать бесконечный цикл.
Мартино
Да, наборы должны обрабатываться специальным регистром handle_item (x) и сортировкой. Я не должен был говорить, что эта реализация обрабатывает наборы, потому что это не так - но дело в том, что ее можно легко расширить с помощью специального кожуха handle_item, и то же самое будет работать для любого класса или итерируемого объекта, пока Вы готовы написать хеш-функцию самостоятельно. Сложная часть - работа с многомерными списками или словарями - уже рассмотрена здесь, поэтому я обнаружил, что с этой функцией памятки гораздо проще работать в качестве основы, чем с простыми типами «Я принимаю только аргументы из-за хэша».
RussellStewart
Проблема, которую я упомянул, связана с тем фактом, что lists и sets «дублируются» в одно и то же и поэтому становятся неотличимыми друг от друга. setsЯ не боюсь, что пример кода для добавления поддержки, описанный в вашем последнем обновлении. Это легко увидеть, отдельно передав [1,2,3]и {1,2,3}в качестве аргумента d-функции «memoize» и посмотрев, вызывается ли она дважды, как и должно быть, или нет.
Мартино
да, я прочитал эту проблему, но я не решил ее, потому что я думаю, что она намного более незначительна, чем та, о которой вы упоминали. Когда в последний раз вы писали памятную функцию, в которой фиксированный аргумент мог быть либо списком, либо множеством, и оба результата приводили к различным результатам? Если бы вы столкнулись с таким редким случаем, вы бы снова переписали handle_item, чтобы добавить, скажем, 0, если элемент является множеством, или 1, если это список.
RussellStewart
На самом деле, есть аналогичная проблема с listс и dictпотому , что это возможно для listиметь точно такую же вещь в нем , что в результате вызова make_tuple(sorted(x.items()))для словаря. Простым решением для обоих случаев было бы включение type()значения в сгенерированный кортеж. Я могу придумать еще более простой способ обработки sets, но он не обобщает.
Мартино
3

Решение, которое работает как с позиционными аргументами, так и с ключевыми словами независимо от порядка, в котором были переданы аргументы ключевого слова (с использованием inspect.getargspec ):

import inspect
import functools

def memoize(fn):
    cache = fn.cache = {}
    @functools.wraps(fn)
    def memoizer(*args, **kwargs):
        kwargs.update(dict(zip(inspect.getargspec(fn).args, args)))
        key = tuple(kwargs.get(k, None) for k in inspect.getargspec(fn).args)
        if key not in cache:
            cache[key] = fn(**kwargs)
        return cache[key]
    return memoizer

Аналогичный вопрос: определение эквивалентных вызовов функции varargs для запоминания в Python

НДПУ
источник
2
cache = {}
def fib(n):
    if n <= 1:
        return n
    else:
        if n not in cache:
            cache[n] = fib(n-1) + fib(n-2)
        return cache[n]
Викрант Сингх
источник
4
Вы могли бы использовать просто if n not in cacheвместо этого. использование cache.keysсоздаст ненужный список в python 2
n611x007
2

Хотелось бы добавить к уже предоставленным ответам, библиотека декоратора Python имеет несколько простых, но полезных реализаций, которые, в отличие от этого, могут также запоминать «не подлежащие обработке типы» functools.lru_cache.

Sid
источник
1
Этот декоратор не запоминает "непригодные виды" ! Просто возвращается к вызову функции без запоминания, против явного лучше идти против неявной догмы.
Острокач