¿Qué es la memorización y cómo puedo usarla en Python?

378

Acabo de comenzar Python y no tengo idea de qué es la memorización y cómo usarla. Además, ¿puedo tener un ejemplo simplificado?

blur959
fuente
215
Cuando la segunda oración del artículo relevante de Wikipedia contiene la frase "análisis de descenso recursivo mutuo [1] en un algoritmo general de análisis de arriba hacia abajo [2] [3] que acomoda la ambigüedad y la recursión izquierda en el tiempo y el espacio polinomiales", creo Es totalmente apropiado preguntar a SO qué está pasando.
Clueless
10
@Clueless: esa frase está precedida por "La memorización también se ha utilizado en otros contextos (y para fines distintos de las ganancias de velocidad), como en". Entonces es solo una lista de ejemplos (y no necesita ser entendido); No es parte de la explicación de la memorización.
ShreevatsaR
1
@StefanGruenwald Ese enlace está muerto. ¿Puedes por favor encontrar una actualización?
JS.
2
Nuevo enlace al archivo pdf, ya que pycogsci.info está caído: people.ucsc.edu/~abrsvn/NLTK_parsing_demos.pdf
Stefan Gruenwald
44
@Clueless, el artículo en realidad dice " análisis de descenso recursivo simple recursivo [1] en un algoritmo de análisis general de arriba hacia abajo [2] [3] que acomoda la ambigüedad y la recursión izquierda en el tiempo y el espacio polinomiales". Te perdiste lo simple , lo que obviamente hace que ese ejemplo sea mucho más claro :).
studgeek

Respuestas:

353

La memorización se refiere efectivamente a recordar ("memorización" → "memorando" → para ser recordado) los resultados de las llamadas a métodos basadas en las entradas del método y luego devolver el resultado recordado en lugar de calcular el resultado nuevamente. Puede pensarlo como un caché para los resultados del método. Para más detalles, consulte la página 387 para la definición en Introducción a los algoritmos (3e), Cormen et al.

Un ejemplo simple para calcular factoriales usando la memorización en Python sería algo como esto:

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]

Puede volverse más complicado y encapsular el proceso de memorización en una clase:

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]

Entonces:

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

factorial = Memoize(factorial)

Se agregó una característica conocida como " decoradores " en Python 2.4 que le permite ahora simplemente escribir lo siguiente para lograr lo mismo:

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

La biblioteca de decoradores de Python tiene un decorador similar llamado memoizedque es ligeramente más robusto que la Memoizeclase que se muestra aquí.

jason
fuente
2
Gracias por esta sugerencia La clase Memoize es una solución elegante que se puede aplicar fácilmente al código existente sin necesidad de una gran refactorización.
Capitán Lepton el
10
La solución de la clase Memoize es defectuosa, no funcionará igual que el factorial_memo, porque el factorialinterior def factorialtodavía llama a lo antiguo unmemoize factorial.
adamsmith
99
Por cierto, también puedes escribir if k not in factorial_memo:, que se lee mejor que if not k in factorial_memo:.
ShreevatsaR
55
Realmente debería hacer esto como decorador.
Emlyn O'Regan
3
@ durden2.0 Sé que este es un comentario antiguo, pero argses una tupla. def some_function(*args)hace args una tupla.
Adam Smith
232

Nuevo en Python 3.2 es functools.lru_cache. Por defecto, sólo se almacena en caché los 128 llamadas utilizados más recientemente, pero se puede ajustar la maxsizea Nonepara indicar que la caché nunca debe 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 función por sí sola es muy lenta, intente fib(36)y tendrá que esperar unos diez segundos.

Agregar lru_cacheanotaciones asegura que si la función ha sido llamada recientemente para un valor en particular, no volverá a calcular ese valor, sino que usará un resultado anterior en caché. En este caso, conduce a una mejora de velocidad tremenda, mientras que el código no está abarrotado con los detalles del almacenamiento en caché.

Flimm
fuente
2
Intenté fib (1000), obtuve RecursionError: la profundidad máxima de recursión excedida en comparación
X Æ A-12
55
@Andyk El límite de recursión Py3 predeterminado es 1000. La primera vez que fibse llama, tendrá que volver al caso base antes de que pueda ocurrir la memorización. Entonces, su comportamiento es casi esperado.
Quelklef
1
Si no me equivoco, solo se almacena en caché hasta que no se elimine el proceso, ¿verdad? ¿O se almacena en caché independientemente de si el proceso se cancela? Por ejemplo, digamos que reinicio mi sistema: ¿los resultados almacenados en caché seguirán almacenados?
Kristada673
1
@ Kristada673 Sí, está almacenado en la memoria del proceso, no en el disco.
Flimm
2
Tenga en cuenta que esto acelera incluso la primera ejecución de la función, ya que es una función recursiva y está almacenando en caché sus propios resultados intermedios. Podría ser bueno ilustrar una función no recursiva que es inherentemente lenta para que sea más clara para tontos como yo. : D
endolito el
61

Las otras respuestas cubren lo que está bastante bien. No estoy repitiendo eso. Solo algunos puntos que pueden serle útiles.

Por lo general, la memorización es una operación que puede aplicar en cualquier función que calcule algo (costoso) y devuelva un valor. Debido a esto, a menudo se implementa como decorador . La implementación es sencilla y sería algo como esto

memoised_function = memoise(actual_function)

o expresado como decorador

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

Memoization es mantener los resultados de cálculos caros y devolver el resultado en caché en lugar de volver a calcularlo continuamente.

Aquí hay un ejemplo:

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

Se puede encontrar una descripción más completa en la entrada de wikipedia sobre memorización .

Bryan Oakley
fuente
Hmm, ahora si eso fuera correcto Python, se movería, pero parece no ser ... bueno, ¿entonces "caché" no es un dict? Porque si es así, debería ser if input not in self.cache y self.cache[input] ( has_keyes obsoleto desde ... al principio de la serie 2.x, si no 2.0. self.cache(index)Nunca fue correcto. IIRC)
Jürgen A. Erhard
15

No olvidemos la hasattrfunción incorporada, para aquellos que quieran hacer manualidades. De esa manera, puede mantener la memoria caché de mem dentro de la definición de la función (en lugar de una 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
fuente
Esto parece una idea muy cara. Por cada n, no solo almacena en caché los resultados para n, sino también para 2 ... n-1.
codeforester
15

He encontrado esto extremadamente ú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)
Sr. Bjerre
fuente
Consulte docs.python.org/3/library/functools.html#functools.wraps para saber por qué se debe usar functools.wraps.
anishpatel
1
¿Necesito borrar manualmente el memopara que se libere la memoria?
nos
La idea es que los resultados se almacenan dentro de la nota dentro de una sesión. Es decir, no se están limpiando, ya que es
mr.bjerre
6

Básicamente, la memorización guarda los resultados de operaciones anteriores realizadas con algoritmos recursivos para reducir la necesidad de atravesar el árbol de recursión si se requiere el mismo cálculo en una etapa posterior.

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

Ejemplo de memorización de Fibonacci en 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
fuente
2
Para obtener más rendimiento antes de sembrar su fibcache con los primeros valores conocidos, puede tomar la lógica adicional para manejarlos fuera de la 'ruta de acceso' del código.
jkflying
5

La memorización es la conversión de funciones en estructuras de datos. Por lo general, uno quiere que la conversión se produzca de forma incremental y perezosa (a pedido de un elemento de dominio determinado, o "clave"). En lenguajes funcionales perezosos, esta conversión diferida puede ocurrir automáticamente y, por lo tanto, la memorización se puede implementar sin efectos secundarios (explícitos).

Conal
fuente
5

Bueno, primero debería responder la primera parte: ¿qué es la memorización?

Es solo un método para intercambiar memoria por tiempo. Piensa en la tabla de multiplicar .

Usar objetos mutables como valor predeterminado en Python generalmente se considera malo. Pero si lo usa sabiamente, en realidad puede ser útil implementar a memoization.

Aquí hay un ejemplo adaptado de http://docs.python.org/2/faq/design.html#why-are-default-values-shared-between-objects

Usando un mutable dicten la definición de la función, los resultados computados intermedios pueden almacenarse en caché (por ejemplo, al calcular factorial(10)después de calcular factorial(9), podemos reutilizar todos los resultados intermedios)

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

Aquí hay una solución que funcionará con argumentos de tipo list o dict sin quejarse:

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

Tenga en cuenta que este enfoque puede extenderse naturalmente a cualquier objeto mediante la implementación de su propia función hash como un caso especial en handle_item. Por ejemplo, para hacer que este enfoque funcione para una función que toma un conjunto como argumento de entrada, puede agregar a handle_item:

if is_instance(x, set):
    return make_tuple(sorted(list(x)))
RussellStewart
fuente
1
Buen intento Sin quejarse, un listargumento de [1, 2, 3]puede considerarse erróneamente igual que un setargumento diferente con un valor de {1, 2, 3}. Además, los conjuntos están desordenados como diccionarios, por lo que también deberían serlo sorted(). También tenga en cuenta que un argumento de estructura de datos recursiva causaría un bucle infinito.
Martineau
Sí, los conjuntos deben manejarse con una carcasa especial handle_item (x) y ordenando. No debería haber dicho que esta implementación maneja conjuntos, porque no lo hace, pero el punto es que puede extenderse fácilmente para hacerlo mediante una carcasa especial handle_item, y lo mismo funcionará para cualquier clase u objeto iterable siempre que estás dispuesto a escribir la función hash tú mismo. La parte difícil, tratar con listas o diccionarios multidimensionales, ya se trata aquí, por lo que descubrí que esta función de memorizar es mucho más fácil de usar como base que los tipos simples "Solo tomo argumentos hashables".
RussellStewart
El problema que he mencionado se debe al hecho de que lists y sets son "tupleized" en el mismo y por lo tanto no se pueden distinguir unos de otros. El código de ejemplo para agregar soporte para setsdescrito en su última actualización no evita que me temo. Esto se puede ver fácilmente pasando por separado [1,2,3]y {1,2,3}como un argumento para una función de prueba d "memorizar" y ver si se llama dos veces, como debería ser o no.
Martineau
sí, leí ese problema, pero no lo solucioné porque creo que es mucho más pequeño que el otro que mencionaste. ¿Cuándo fue la última vez que escribió una función memorable en la que un argumento fijo podría ser una lista o un conjunto, y los dos dieron como resultado resultados diferentes? Si se topara con un caso tan raro, nuevamente volvería a escribir handle_item para anteponer, digamos un 0 si el elemento es un conjunto o un 1 si es una lista.
RussellStewart
En realidad, hay un problema similar con listsys dictporque es posible que lista tenga exactamente lo mismo que resultó de llamar make_tuple(sorted(x.items()))a un diccionario. Una solución simple para ambos casos sería incluir el type()valor de la tupla generada. Puedo pensar en una forma aún más simple específicamente para manejar sets, pero no generaliza.
Martineau
3

Solución que funciona con argumentos posicionales y de palabras clave independientemente del orden en que se pasaron los argumentos de palabras clave (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

Pregunta similar: la identificación de funciones varargs equivalentes requiere memorización en Python

ndpu
fuente
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
fuente
44
podrías usar simplemente en su if n not in cachelugar. usar cache.keyscrearía una lista innecesaria en python 2
n611x007
2

Solo quería agregar a las respuestas ya proporcionadas, la biblioteca decoradora de Python tiene algunas implementaciones simples pero útiles que también pueden memorizar "tipos no compartibles", a diferencia functools.lru_cache.

Sid
fuente
1
¡Este decorador no memoriza "tipos no compartibles" ! Simplemente recurre a llamar a la función sin memorización, ir en contra de lo explícito es mejor que el dogma implícito .
ostrokach 01 de