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

memoization

Question

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

Answer 1

Aquí hay una solución que funcionará con los 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 implementando 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 un argumento de entrada, podría agregarlo a handle_item:

if is_instance(x, set):
    return make_tuple(sorted(list(x)))

Answer 2

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

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

El uso de objetos mutables como valor predeterminado en Python generalmente se considera malo. Pero si lo usa con prudencia, en realidad puede ser útil para implementar una memoization .

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

Al usar un dict mutable en la definición de la función, los resultados calculados intermedios se pueden almacenar 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]

Answer 3

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)

Answer 4

La memoización es la conversión de funciones en estructuras de datos. Por lo general, uno quiere que la conversión se realice de forma incremental y perezosa (a petición de un elemento de dominio determinado, o "clave"). En los lenguajes funcionales perezosos, esta conversión perezosa puede suceder automáticamente y, por lo tanto, la memoria puede implementarse sin efectos secundarios (explícitos).

Answer 5

La memorización consiste básicamente en guardar los resultados de operaciones anteriores realizadas con algoritmos recursivos para reducir la necesidad de atravesar el árbol de recursiones si se requiere el mismo cálculo en una etapa posterior.

vea 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]

Answer 6

La memorización es mantener los resultados de cálculos costosos y devolver el resultado almacenado en caché en lugar de recalcularlo 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 memoization .

Answer 7

La memorización se refiere efectivamente a los resultados de las llamadas de método basadas en las entradas del método ("memoización" → "memorándum" → a recordar) y luego devuelve el resultado recordado en lugar de calcular nuevamente el resultado. Puedes considerarlo 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 utilizando 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 obtener 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 " decorators " 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 Python Decorator tiene un decorador similar llamado memoized que es ligeramente más robusto que la clase Memoize muestra aquí.

Answer 8

Las otras respuestas cubren lo que está bastante bien. No estoy repitiendo eso. Sólo algunos puntos que pueden ser útiles para usted.

Por lo general, memoisation 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 un decorator . La implementación es sencilla y sería algo así.

memoised_function = memoise(actual_function)

o expresado como decorador

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

Answer 9

No olvidemos la función hasattr incorporada, para aquellos que quieren hacer manualidades. De esa manera puede mantener la memoria caché de mem dentro de la definición de la función (a diferencia 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]

Answer 10

Nuevo en Python 3.2 es functools.lru_cache . De forma predeterminada, solo almacena en caché las 128 llamadas utilizadas más recientemente, pero puede establecer el maxsize en None para indicar que el caché nunca debe caducar:

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í misma es muy lenta, intente con fib(36) y tendrá que esperar unos diez segundos.

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

Answer 11

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

Answer 12

Solución que funciona con argumentos de palabras clave y posicionales independientemente del orden en que se pasaron los argumentos de palabras clave (utilizando 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: Identificar las funciones de varargs equivalentes para la memorización en 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]