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

Question

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

Answer 1

Под "запоминанием" фактически понимается запоминание ("памятка" → "меморандум" → запоминаемое) результатов вызовов метода на основе входных данных метода, а затем возвращение запомненного результата, а не его повторное вычисление. Вы можете думать об этом как о кеше для результатов метода. Для получения дополнительной информации см. Стр. 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 класс показан здесь.

Answer 2

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

Answer 3

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

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

memoised_function = memoise(actual_function)

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

@memoise
def actual_function(arg1, arg2):
   #body

Answer 4

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

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)

Answer 5

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

Вот пример:

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

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

Answer 6

Давайте не будем забывать встроенный 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]

Answer 7

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

см. 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]

Answer 8

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

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

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

Вот пример, адаптированный из http://docs.python.org/2/faq/design.html

Использование изменяемого 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]

Answer 9

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

Answer 10

Вот решение, которое будет работать с аргументами типа 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)))

Answer 11

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

Answer 12

Решение, которое работает с позиционными аргументами и аргументами ключевых слов независимо от порядка, в котором были переданы аргументы ключевого слова (с использованием 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

Answer 13

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]

Answer 14

Если важна скорость:

• @functools.cacheа также @functools.lru_cache(maxsize=None)одинаково быстры, за 0,122 секунды (лучший из 15 прогонов) зацикливаются миллион раз в моей системе
• глобальная переменная кеша работает намного медленнее: 0,180 секунды (лучший из 15 прогонов) зацикливается миллион раз в моей системе.
• а self.cacheпеременная класса еще немного медленнее: 0,214 секунды (лучший из 15 прогонов) зацикливается миллион раз в моей системе.

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

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

Один открытый вопрос для меня будет заключаться в том, как проводить модульное тестирование чего-то, что имеет functoolsдекоратор. Можно ли как-то очистить кеш? Модульные тесты кажутся наиболее чистыми при использовании метода класса (где вы можете создать экземпляр нового класса для каждого теста) или, во-вторых, метода глобальной переменной (поскольку вы можете yourimportedmodule.cachevariable = {}чтобы его опустошить).