O que é memorização e como posso usá-lo em Python?

378

Acabei de iniciar o Python e não tenho ideia do que é memorização e como usá-la. Além disso, posso ter um exemplo simplificado?

blur959
fonte
215
Quando a segunda frase do artigo relevante da wikipedia contém a frase "análise de descida mutuamente recursiva [1] em um algoritmo geral de análise de cima para baixo [2] [3] que acomoda a ambiguidade e a recursão esquerda no tempo e no espaço polinomiais", acho é inteiramente apropriado perguntar ao SO o que está acontecendo.
Clueless
10
@ Clueless: Essa frase é precedida por "A memorização também foi usada em outros contextos (e para outros fins que não os ganhos de velocidade), como em". Portanto, é apenas uma lista de exemplos (e não precisa ser entendida); não faz parte da explicação da memorização.
precisa saber é o seguinte
11
@StefanGruenwald Esse link está morto. Você pode encontrar uma atualização?
JS.
2
Novo link para o arquivo pdf, uma vez que o pycogsci.info está inoperante: people.ucsc.edu/~abrsvn/NLTK_parsing_demos.pdf
Stefan Gruenwald
4
@ Sem pistas, o artigo na verdade diz " análise simples de descida mutuamente recursiva [1] em um algoritmo geral de análise de cima para baixo [2] [3] que acomoda a ambiguidade e a recursão à esquerda no tempo e no espaço polinomiais". Você perdeu o simples , o que obviamente torna esse exemplo muito mais claro :).
Studgeek

Respostas:

353

Memorização refere-se efetivamente aos resultados de memorização ("memorização" → "memorando" → a ser lembrado) de chamadas de método com base nas entradas do método e, em seguida, retornando o resultado lembrado em vez de computá-lo novamente. Você pode pensar nisso como um cache para obter resultados do método. Para mais detalhes, consulte a página 387 para a definição em Introdução aos algoritmos (3e), Cormen et al.

Um exemplo simples para calcular fatoriais usando memoização em Python seria algo como isto:

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]

Você pode ficar mais complicado e encapsular o processo de memorização em uma classe:

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]

Então:

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

factorial = Memoize(factorial)

Um recurso conhecido como " decoradores " foi adicionado no Python 2.4, que permite que você simplesmente escreva o seguinte para realizar a mesma coisa:

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

A Python Decorator Library possui um decorador semelhante chamado memoizedque é um pouco mais robusto do que a Memoizeclasse mostrada aqui.

Jason
fonte
2
Obrigado por esta sugestão. A classe Memoize é uma solução elegante que pode ser facilmente aplicada ao código existente sem precisar de muita refatoração.
Capitão Lepton
10
A solução da classe Memoize é incorreta, não funcionará da mesma forma que a factorial_memo, porque o factorialinterior def factorialainda chama o antigo desmembrar factorial.
adamsmith
9
A propósito, você também pode escrever if k not in factorial_memo:, que lê melhor que if not k in factorial_memo:.
ShreevatsaR
5
Realmente deve fazer isso como decorador.
Emlyn O'Regan #
3
@ durden2.0 Eu sei que este é um comentário antigo, mas argsé uma tupla. def some_function(*args)faz args uma tupla.
Adam Smith
232

Novo no Python 3.2 é functools.lru_cache. Por padrão, ele armazena em cache apenas as 128 chamadas usadas mais recentemente, mas você pode configurá maxsize-lo Nonepara indicar que o cache nunca deve expirar:

import functools

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

Esta função por si só é muito lenta, tente fib(36)e você terá que esperar cerca de dez segundos.

A adição de lru_cacheanotação garante que, se a função tiver sido chamada recentemente para um valor específico, ela não recalculará esse valor, mas usará um resultado anterior em cache. Nesse caso, isso leva a uma tremenda melhoria de velocidade, enquanto o código não é confuso com os detalhes do cache.

Flimm
fonte
2
Fib tentou (1000), obteve RecursionError: profundidade máxima recursão excedeu em comparação
X ® A-12
5
@Andyk O limite de recursão padrão do Py3 é 1000. Na primeira vez em que fibfor chamado, será necessário retornar ao caso base antes que a memorização possa acontecer. Portanto, seu comportamento é praticamente o esperado.
Quelklef
11
Se não me engano, ele armazena em cache apenas até que o processo não seja interrompido, certo? Ou ele faz cache, independentemente de o processo ser morto? Por exemplo, digamos que eu reinicie meu sistema - os resultados armazenados em cache ainda serão armazenados em cache?
Kristada673
11
@ Kristada673 Sim, está armazenado na memória do processo, não no disco.
Flimm 22/10/19
2
Observe que isso acelera até a primeira execução da função, pois é uma função recursiva e está armazenando em cache seus próprios resultados intermediários. Pode ser bom ilustrar uma função não recursiva que é inerentemente lenta para tornar mais clara para bonecos como eu. : D
endólito
61

As outras respostas cobrem o que está muito bem. Eu não estou repetindo isso. Apenas alguns pontos que podem ser úteis para você.

Normalmente, a memória é uma operação que você pode aplicar em qualquer função que calcule algo (caro) e retorne um valor. Por esse motivo, é frequentemente implementado como um decorador . A implementação é simples e seria algo como isto

memoised_function = memoise(actual_function)

ou expresso como um decorador

@memoise
def actual_function(arg1, arg2):
   #body
Noufal Ibrahim
fonte
18

A memorização é manter os resultados de cálculos caros e retornar o resultado em cache, em vez de recalculá-lo continuamente.

Aqui está um exemplo:

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

Uma descrição mais completa pode ser encontrada na entrada da Wikipedia sobre memorização .

Bryan Oakley
fonte
Hmm, agora, se isso era Python correto, seria ótimo, mas parece não ser ... ok, então "cache" não é um ditado? Porque se for, deve ser if input not in self.cache e self.cache[input] ( has_keyé obsoleta desde ... no início da série 2.x, se não for 2.0. self.cache(index)Nunca foi correta IIRC.)
Jürgen A. Erhard
15

Não vamos esquecer a hasattrfunção embutida, para quem deseja criar manualmente. Dessa forma, você pode manter o cache de mem dentro da definição da função (em oposição a um global).

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]
Karel Kubat
fonte
Parece uma ideia muito cara. Para cada n, ele não apenas armazena em cache os resultados para n, mas também para 2 ... n-1.
codeforester
15

Eu achei isso extremamente útil

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
fonte
Veja docs.python.org/3/library/functools.html#functools.wraps para saber por que usar functools.wraps.
Anishpatel
11
Preciso limpar manualmente memopara que a memória seja liberada?
Nos
A idéia é que os resultados sejam armazenados dentro do memorando dentro de uma sessão. Ou seja, nada estão sendo apuradas como é
mr.bjerre
6

A memorização consiste basicamente em salvar os resultados de operações anteriores feitas com algoritmos recursivos, a fim de reduzir a necessidade de percorrer a árvore de recursão se o mesmo cálculo for necessário posteriormente.

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

Exemplo de memorização de Fibonacci em 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]
Romaine Carter
fonte
2
Para obter mais desempenho, pré-propague seu fibcache com os primeiros valores conhecidos, você pode usar a lógica extra para manipulá-los fora do 'caminho ativo' do código.
Jkflying 21/05
5

Memoização é a conversão de funções em estruturas de dados. Normalmente, a conversão é realizada de forma incremental e lenta (sob demanda de um determinado elemento de domínio - ou "chave"). Em linguagens funcionais preguiçosas, essa conversão preguiçosa pode ocorrer automaticamente e, portanto, a memorização pode ser implementada sem efeitos colaterais (explícitos).

Conal
fonte
5

Bem, eu deveria responder a primeira parte primeiro: o que é memorização?

É apenas um método para trocar memória por tempo. Pense na tabela de multiplicação .

Usar objeto mutável como valor padrão no Python geralmente é considerado ruim. Mas se usá-lo com sabedoria, pode ser realmente útil implementar a memoization.

Aqui está um exemplo adaptado de http://docs.python.org/2/faq/design.html#why-are-default-values-shared-between-objects

Usando um mutável dictna definição da função, os resultados intermediários calculados podem ser armazenados em cache (por exemplo, ao calcular factorial(10)após o cálculo factorial(9), podemos reutilizar todos os resultados intermediários)

def factorial(n, _cache={1:1}):    
    try:            
        return _cache[n]           
    except IndexError:
        _cache[n] = factorial(n-1)*n
        return _cache[n]
yegle
fonte
4

Aqui está uma solução que funcionará com argumentos de lista ou tipo de ditado sem reclamar:

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

Observe que essa abordagem pode ser estendida naturalmente a qualquer objeto, implementando sua própria função de hash como um caso especial no handle_item. Por exemplo, para fazer essa abordagem funcionar para uma função que aceita um conjunto como argumento de entrada, você pode adicionar ao handle_item:

if is_instance(x, set):
    return make_tuple(sorted(list(x)))
RussellStewart
fonte
11
Boa tentativa. Sem se queixar, um listargumento de [1, 2, 3]pode erroneamente ser considerado o mesmo que um setargumento diferente com um valor de {1, 2, 3}. Além disso, os conjuntos não são ordenados como dicionários, portanto, também precisam ser sorted(). Observe também que um argumento recursivo da estrutura de dados causaria um loop infinito.
martineau
Sim, os conjuntos devem ser manipulados pela caixa especial handle_item (x) e pela classificação. Eu não deveria ter dito que essa implementação lida com conjuntos, porque não - mas o ponto é que ela pode ser facilmente estendida para isso por uma caixa especial handle_item, e o mesmo funcionará para qualquer classe ou objeto iterável, desde que você está disposto a escrever a função de hash você mesmo. A parte complicada - lidar com listas ou dicionários multidimensionais - já é abordada aqui, então eu descobri que essa função de memorização é muito mais fácil de trabalhar como base do que os tipos simples de "eu só aceito argumentos laváveis".
precisa saber é o seguinte
O problema que mencionei se deve ao fato de que se listes setsão "tuplaizados" na mesma coisa e, portanto, tornam-se indistinguíveis um do outro. O código de exemplo para adicionar suporte setsdescrito em sua atualização mais recente não evita que eu tenha medo. Isso pode ser facilmente visto passando separadamente [1,2,3]e {1,2,3}como argumento para uma função de teste "memoize" d e ver se é chamado duas vezes, como deveria ser ou não.
martineau
sim, li esse problema, mas não o resolvi porque acho que é muito menor do que o outro que você mencionou. Quando foi a última vez que você escreveu uma função memorizada em que um argumento fixo poderia ser uma lista ou um conjunto, e os dois resultaram em saídas diferentes? Se você se deparar com um caso tão raro, basta reescrever o handle_item para acrescentar antes, digitar 0 se o elemento for um conjunto ou 1 se for uma lista.
precisa saber é o seguinte
Na verdade, há um problema semelhante com lists e dicts porque é possível que lista tenha exatamente a mesma coisa que resultou da chamada make_tuple(sorted(x.items()))de um dicionário. Uma solução simples para os dois casos seria incluir o type()valor of na tupla gerada. Posso pensar em uma maneira ainda mais simples de lidar especificamente com sets, mas isso não generaliza.
martineau
3

Solução que funciona com argumentos posicionais e de palavras-chave, independentemente da ordem em que os argumentos das palavras-chave foram transmitidos (usando 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

Pergunta semelhante: Identificar funções varargs equivalentes exige memorização em Python

ndpu
fonte
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]
Vikrant Singh
fonte
4
você poderia usar simplesmente em if n not in cachevez disso. usando cache.keyscriaria uma lista desnecessária em python 2
n611x007
2

Só queria acrescentar às respostas já fornecidas, a biblioteca decoradora Python tem algumas implementações simples, mas úteis, que também podem memorizar "tipos laváveis", ao contrário functools.lru_cache.

Sid
fonte
11
Este decorador não memoriza "tipos laváveis" ! Apenas recorre à chamada da função sem memorização, ir contra o explícito é melhor do que o dogma implícito .
Ostrokach #