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

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?

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í.

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é.

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

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 .

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]

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)

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]

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).

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]

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)))

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

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]

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.