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

8 minutos de lectura

¿Que es la memorizacion y como puedo usarla en Python
desenfoque959

Acabo de empezar con Python y no tengo ni idea de qué memorización es y cómo usarlo. Además, ¿puedo tener un ejemplo simplificado?

  • Cuando la segunda oración del artículo relevante de wikipedia contiene la frase “análisis de descenso mutuamente recursivo[1] en un algoritmo general de análisis de arriba hacia abajo[2][3] que acomoda la ambigüedad y la recursividad por la izquierda en el tiempo y el espacio polinomial”, creo que es completamente apropiado preguntarle a SO qué está pasando.

    – Despistado

    2 de enero de 2010 a las 14:17

  • @Clueless: esa frase está precedida por “Memoization también se ha utilizado en otros contextos (y para fines distintos de las ganancias de velocidad), como en”. Así que es solo una lista de ejemplos (y no es necesario que se entienda); no es parte de la explicación de la memorización.

    – ShreevatsaR

    4 de abril de 2014 a las 6:12

  • @StefanGruenwald Ese enlace está muerto. ¿Puedes encontrar una actualización?

    – JS.

    3 de diciembre de 2014 a las 17:39

  • Nuevo enlace al archivo pdf, ya que pycogsci.info está caído: people.ucsc.edu/~abrsvn/NLTK_parsing_demos.pdf

    – Stefan Grünwald

    5 de diciembre de 2014 a las 20:08

  • @Clueless, el artículo en realidad dice “sencillo análisis de descendencia mutuamente recursivo[1] en un algoritmo general de análisis de arriba hacia abajo[2][3] que acomoda la ambigüedad y la recursividad por la izquierda en tiempo y espacio polinomial”. sencillolo que obviamente hace que ese ejemplo sea mucho más claro :).

    – estudioso

    30 de julio de 2017 a las 0:48

1646973549 770 ¿Que es la memorizacion y como puedo usarla en Python
jason

La memorización se refiere efectivamente a recordar (“memoización” → “memorando” → para ser recordado) los resultados de las llamadas a métodos en función de las entradas del método y luego devolver el resultado recordado en lugar de calcular el resultado nuevamente. Puede pensar en ello 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 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]

Luego:

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

factorial = Memoize(factorial)

Una característica conocida como “decoradores” se agregó en Python 2.4, lo 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)

los Biblioteca de decoradores de Python tiene un decorador similar llamado memoized que es un poco más robusto que el Memoize clase que se muestra aquí.

  • 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 mucha refactorización.

    – Capitán Lepton

    11 de abril de 2013 a las 12:41

  • La solución de la clase Memoize tiene errores, no funcionará igual que la factorial_memoporque el factorial en el interior def factorial todavía llama al viejo unmemoize factorial.

    – Adam Smith

    6 de agosto de 2013 a las 7:35

  • Por cierto, también puedes escribir if k not in factorial_memo:que se lee mejor que if not k in factorial_memo:.

    – ShreevatsaR

    4 de abril de 2014 a las 6:34

  • Realmente debería hacer esto como decorador.

    – Emlyn O’Regan

    8 de octubre de 2014 a las 4:23

  • @ durden2.0 Sé que este es un comentario antiguo, pero args es una tupla. def some_function(*args) hace args una tupla.

    – Adam Smith

    13 de diciembre de 2016 a las 18:18

1646973549 836 ¿Que es la memorizacion y como puedo usarla en Python
flim

functools.cache decorador:

Python 3.9 lanzó una nueva función functools.cache. Almacena en la memoria el resultado de una llamada funcional con un conjunto particular de argumentos, que es la memorización. Es fácil de usar:

import functools

@functools.cache
def fib(num):
    if num < 2:
        return num
    else:
        return fib(num-1) + fib(num-2)

Esta funcion sin el decorador es muy lenta, prueba fib(36) y tendrás que esperar unos diez segundos.

Agregando el cache El decorador 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 almacenado en caché. En este caso, conduce a una tremenda mejora en la velocidad, mientras que el código no está abarrotado con los detalles del almacenamiento en caché.

functools.lru_cache decorador:

Si necesita admitir versiones anteriores de Python, functools.lru_cache funciona en Python 3.2+. De manera predeterminada, solo almacena en caché las 128 llamadas utilizadas más recientemente, pero puede configurar el maxsize para None para indicar que el caché nunca debe caducar:

@functools.lru_cache(maxsize=None)
def fib(num):
    # etc

  • Intenté fib (1000), obtuve RecursionError: se excedió la profundidad máxima de recursión en comparación

    – Andreas K.

    28 de septiembre de 2017 a las 12:04


  • @Andyk El límite de recursión predeterminado de Py3 es 1000. La primera vez fib se llama, tendrá que volver al caso base antes de que pueda ocurrir la memorización. Entonces, su comportamiento es casi el esperado.

    – Quelkef

    19 de agosto de 2018 a las 2:07

  • Si no me equivoco, se almacena en caché solo hasta que el proceso no se elimine, ¿verdad? ¿O se almacena en caché independientemente de si el proceso se elimina? Como, digamos que reinicio mi sistema, ¿los resultados almacenados en caché seguirán estando almacenados en caché?

    – Kristada673

    22 de octubre de 2018 a las 2:20


  • @ Kristada673 Sí, está almacenado en la memoria del proceso, no en el disco.

    – Flamm

    22 de octubre de 2018 a las 7:19

  • Tenga en cuenta que esto acelera incluso la primera ejecución de la función, ya que es una función recursiva y almacena en caché sus propios resultados intermedios. Podría ser bueno para ilustrar una función no recursiva que es inherentemente lenta para que sea más claro para tontos como yo. 😀

    – endolito

    2 de agosto de 2019 a las 14:41

Las otras respuestas cubren lo que es bastante bien. No estoy repitiendo eso. Solo algunos puntos que te pueden ser de utilidad.

Por lo general, la memorización es una operación que puede aplicar en cualquier función que calcula algo (costoso) y devuelve un valor. Debido a esto, a menudo se implementa como un 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

1646973549 894 ¿Que es la memorizacion y como puedo usarla en Python
mr.bjerre

He encontrado esto extremadamente útil

from functools import wraps


def memoize(function):    
    memo = {}
        
    @wraps(function)
    def wrapper(*args):

        # add the new key to dict if it doesn't exist already  
        if args not in memo:
            memo[args] = function(*args)

        return memo[args]

    return wrapper
    
    
@memoize
def fibonacci(n):
    if n < 2: return n
    return fibonacci(n - 1) + fibonacci(n - 2)
    
fibonacci(25)

1646973550 361 ¿Que es la memorizacion y como puedo usarla en Python
Bryan Oakley

La memorización es mantener los resultados de cálculos costosos y devolver el resultado almacenado 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]

Una descripción más completa se encuentra en el entrada de wikipedia sobre memorización.

  • Hmm, ahora si eso fuera correcto Python, sería genial, pero parece que no lo es… está bien, ¿entonces “caché” no es un dictado? Porque si lo es, debería serlo. if input not in self.cache y self.cache[input] (has_key está obsoleto desde… principios de la serie 2.x, si no 2.0. self.cache(index) nunca fue correcto. IIRC)

    – Jürgen A. Erhard

    1 de enero de 2010 a las 15:46


¿Que es la memorizacion y como puedo usarla en Python
David

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

  • Hmm, ahora si eso fuera correcto Python, sería genial, pero parece que no lo es… está bien, ¿entonces “caché” no es un dictado? Porque si lo es, debería serlo. if input not in self.cache y self.cache[input] (has_key está obsoleto desde… principios de la serie 2.x, si no 2.0. self.cache(index) nunca fue correcto. IIRC)

    – Jürgen A. Erhard

    1 de enero de 2010 a las 15:46


¿Que es la memorizacion y como puedo usarla en Python
Rusia debe sacar a Putin

La memorización consiste básicamente en guardar los resultados de operaciones pasadas realizadas con algoritmos recursivos para reducir la necesidad de recorrer el árbol recursivo 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]

  • Para obtener un mayor rendimiento, preestablezca su fibcache con los primeros valores conocidos, luego puede tomar la lógica adicional para manejarlos fuera de la “ruta activa” del código.

    – jkflying

    21 de mayo de 2014 a las 5:59

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad