generics - descripcion - ¿Para qué sirve la memoria y es realmente tan útil?

meta title html (12)

Como ejemplo de cómo usar la memorización para mejorar el rendimiento de un algoritmo, lo siguiente se ejecuta aproximadamente 300 veces más rápido para este caso de prueba en particular. Antes, tardaba unos 200 segundos; 2/3 memoized.

class Slice: __slots__ = ''prefix'', ''root'', ''suffix'' def __init__(self, prefix, root, suffix): self.prefix = prefix self.root = root self.suffix = suffix ################################################################################ class Match: __slots__ = ''a'', ''b'', ''prefix'', ''suffix'', ''value'' def __init__(self, a, b, prefix, suffix, value): self.a = a self.b = b self.prefix = prefix self.suffix = suffix self.value = value ################################################################################ class Tree: __slots__ = ''nodes'', ''index'', ''value'' def __init__(self, nodes, index, value): self.nodes = nodes self.index = index self.value = value ################################################################################ def old_search(a, b): # Initialize startup variables. nodes, index = [], [] a_size, b_size = len(a), len(b) # Begin to slice the sequences. for size in range(min(a_size, b_size), 0, -1): for a_addr in range(a_size - size + 1): # Slice "a" at address and end. a_term = a_addr + size a_root = a[a_addr:a_term] for b_addr in range(b_size - size + 1): # Slice "b" at address and end. b_term = b_addr + size b_root = b[b_addr:b_term] # Find out if slices are equal. if a_root == b_root: # Create prefix tree to search. a_pref, b_pref = a[:a_addr], b[:b_addr] p_tree = old_search(a_pref, b_pref) # Create suffix tree to search. a_suff, b_suff = a[a_term:], b[b_term:] s_tree = old_search(a_suff, b_suff) # Make completed slice objects. a_slic = Slice(a_pref, a_root, a_suff) b_slic = Slice(b_pref, b_root, b_suff) # Finish the match calculation. value = size + p_tree.value + s_tree.value match = Match(a_slic, b_slic, p_tree, s_tree, value) # Append results to tree lists. nodes.append(match) index.append(value) # Return largest matches found. if nodes: return Tree(nodes, index, max(index)) # Give caller null tree object. return Tree(nodes, index, 0) ################################################################################ def search(memo, a, b): # Initialize startup variables. nodes, index = [], [] a_size, b_size = len(a), len(b) # Begin to slice the sequences. for size in range(min(a_size, b_size), 0, -1): for a_addr in range(a_size - size + 1): # Slice "a" at address and end. a_term = a_addr + size a_root = a[a_addr:a_term] for b_addr in range(b_size - size + 1): # Slice "b" at address and end. b_term = b_addr + size b_root = b[b_addr:b_term] # Find out if slices are equal. if a_root == b_root: # Create prefix tree to search. key = a_pref, b_pref = a[:a_addr], b[:b_addr] if key not in memo: memo[key] = search(memo, a_pref, b_pref) p_tree = memo[key] # Create suffix tree to search. key = a_suff, b_suff = a[a_term:], b[b_term:] if key not in memo: memo[key] = search(memo, a_suff, b_suff) s_tree = memo[key] # Make completed slice objects. a_slic = Slice(a_pref, a_root, a_suff) b_slic = Slice(b_pref, b_root, b_suff) # Finish the match calculation. value = size + p_tree.value + s_tree.value match = Match(a_slic, b_slic, p_tree, s_tree, value) # Append results to tree lists. nodes.append(match) index.append(value) # Return largest matches found. if nodes: return Tree(nodes, index, max(index)) # Give caller null tree object. return Tree(nodes, index, 0) ################################################################################ import time a = tuple(range(50)) b = (48, 11, 5, 22, 28, 31, 14, 18, 7, 29, 49, 44, 47, 36, 25, 27, 34, 10, 38, 15, 21, 16, 35, 20, 45, 2, 37, 33, 6, 30, 0, 8, 13, 43, 32, 1, 40, 26, 24, 42, 39, 9, 12, 17, 46, 4, 23, 3, 19, 41) start = time.clock() old_search(a, b) stop = time.clock() print(''old_search() ='', stop - start) start = time.clock() search({}, a, b) stop = time.clock() print(''search() ='', stop - start)

Referencia: ¿Cómo se puede aplicar la memoria a este algoritmo?

Hay algunas bibliotecas automáticas de memorización disponibles en Internet para varios idiomas diferentes; pero sin saber para qué sirven, dónde usarlos y cómo funcionan, puede ser difícil ver su valor. ¿Cuáles son algunos argumentos convincentes para usar la memoización y en qué dominio del problema sobresale la memoización? La información para los no informados sería especialmente apreciada aquí.

Creo que casi todo el mundo ha cubierto los conceptos básicos de la memoización, pero te daré algunos ejemplos prácticos en los que se puede usar el movimiento para hacer algunas cosas bastante sorprendentes (imho):

En C # puede reflejar una función y crear un delegado para ella, luego puede invocar dinámicamente al delegado ... ¡pero esto es REALMENTE lento! Es aproximadamente 30 veces más lento que invocar el método directamente. Si memoriza la invocación del método, puede hacer la invocación casi tan rápido como invocar el método directamente.
En la Programación genética puede reducir la sobrecarga de llamar repetidamente la misma función con parámetros de entrada similares para cientos y miles de especímenes en la población.
En la ejecución de los árboles de expresiones: no tiene que volver a evaluar el árbol de expresiones si ya lo ha memorizado ...

Por supuesto, hay muchos más ejemplos prácticos donde se puede utilizar la memoria, pero estos son solo algunos.

En mi blog discuto la memoization y la reflection separado, pero voy a publicar otro artículo sobre el uso de la memoria en los métodos reflejados ...

En mi opinión, los cálculos de Fibonacci y factoriales no son realmente los mejores ejemplos. Memoisation realmente entra en su propio cuando tienes:

Una amplia gama de posibles entradas al cálculo en cuestión, pero el rango todavía está claramente restringido y es conocido
Usted sabe de antemano que cualquier uso real del programa solo usará un pequeño subconjunto de posibles entradas para su cálculo (Fibonacci y factorial fallan esto)
No sabe qué entradas en particular se usarán en tiempo de ejecución, y por lo tanto, qué resultados en particular deberán memorizarse (Fibonacci y factorial también fallan, hasta cierto punto)

Obviamente, si conoce todas las entradas posibles y el espacio lo permite, puede considerar reemplazar la función con una búsqueda (que es lo que haría para, por ejemplo, una implementación de CRC32 incrustada con un generador conocido).

... incluso mejor que el # 2 es si para cualquier ejecución particular del programa , inmediatamente puede decir "el rango de entradas potenciales se restringirá a un subconjunto que satisfaga estas condiciones ...".

Tenga en cuenta que gran parte de esto podría ser probabilístico (o intuitivo); claro, alguien podría probar todas las 10 ^ 13 entradas posibles para su cálculo mágico, pero sabe que, de manera realista, no lo harán. Si lo hacen, la sobrecarga de la memoria realmente no les beneficiará. Pero bien puede decidir que esto es aceptable, o permitir eludir la memoria en tales circunstancias.

Aquí hay un ejemplo, y espero que no sea demasiado complicado (o generalizado) para ser informativo.

En algún firmware que he escrito, una parte del programa toma una lectura de un ADC, que puede ser cualquier número de 0x000 a 0xFFF y calcula una salida para alguna otra parte del programa. Este cálculo también toma un conjunto de números ajustables por el usuario, pero estos solo se leen al inicio del programa. Este cálculo es un éxito la primera vez que se ejecuta.

Crear una tabla de búsqueda antes de tiempo es ridículo. El dominio de entrada es el producto cartesiano de [ 0x000 , ..., 0xFFF ] y (un rango grande de valores de punto flotante) y (otro rango grande ...) y ... No, gracias.

Pero ningún usuario requiere o espera que el dispositivo funcione bien cuando las condiciones cambian rápidamente, y prefieren que funcione mejor cuando las cosas son estables. Así que hago una compensación en el comportamiento computacional que refleja estos requisitos: quiero que este cálculo sea agradable y rápido cuando las cosas son estables, y no me importa cuándo no lo son.

Dada la definición de "condiciones que cambian lentamente" que el usuario típico espera, ese valor de ADC se irá a un valor particular y se mantendrá dentro de aproximadamente 0x010 de su valor establecido. Qué valor depende de las condiciones.

Por lo tanto, el resultado del cálculo se puede memorizar para estas 16 entradas potenciales. Si las condiciones ambientales cambian más rápido de lo esperado, se descarta el ADC "más lejano" de los más recientes (por ejemplo, si he almacenado en caché 0x210 a 0x21F, y luego leo 0x222, descarto el resultado 0x210).

El inconveniente aquí es que si las condiciones ambientales cambian mucho, ese cálculo ya lento se ejecuta un poco más lento. Ya hemos establecido que este es un caso de uso inusual, pero si alguien más adelante revela que realmente quiere operarlo en condiciones inusualmente inestables, puedo implementar una manera de evitar la memoisación.

La memoización brilla en problemas donde las soluciones a los subproblemas se pueden reutilizar. Hablando simplemente, es una forma de almacenamiento en caché. Veamos la función factorial como ejemplo.

3! es un problema en sí mismo, pero también es un subproblema para n! donde n> 3 como 4! = 4 * 3! 4! = 4 * 3! Una función que calcula factoriales puede funcionar mucho mejor con la memorización porque solo calculará 3! Una vez y almacenar el resultado internamente en una tabla hash. Cada vez que se encuentra con 3! de nuevo, buscará el valor en la tabla en lugar de recalcularlo.

Cualquier problema en el que las soluciones de subproblema puedan reutilizarse (cuanto más frecuentemente mejor) es un candidato para usar la memorización.

La memoización es esencialmente almacenar en caché el valor de retorno de una función para una entrada determinada. Esto es útil si va a repetir una llamada a la función muchas veces con la misma entrada, y especialmente si la función tarda algún tiempo en ejecutarse. Por supuesto, dado que los datos deben almacenarse en algún lugar, la memoria utilizará más memoria. Es un intercambio entre el uso de CPU y el uso de RAM.

La memorización puede acelerar radicalmente los algoritmos. El ejemplo clásico es la serie Fibonocci, donde el algoritmo recursivo es increíblemente lento, pero la memorización lo hace automáticamente tan rápido como la versión iterativa.

La respuesta factorial popular aquí es una especie de respuesta de juguete. Sí, la memorización es útil para invocaciones repetidas de esa función, pero la relación es trivial: en el caso de "impresión factorial (N) para 0..M", simplemente está reutilizando el último valor.

Muchos de los otros ejemplos aquí son simplemente ''caching''. Lo cual es útil, pero ignora las asombrosas implicaciones algorítmicas que la palabra memoización conlleva para mí.

Mucho más interesantes son los casos en los que diferentes ramas de una sola invocación de una función recursiva alcanzan subproblemas idénticos, pero en un patrón no trivial tal que realmente la indexación en algún caché es realmente útil.

Por ejemplo, considere matrices tridimensionales de enteros cuyos valores absolutos suman k. Por ejemplo, para n = 3, k = 5 [1, -4,0], [3, -1,1], [5,0,0], [0,5,0] serían algunos ejemplos. Sea V (n, k) el número de arreglos únicos posibles para un n, k dado. Su definición es:

V(n,0)=1; V(0,k)=0; V(n,k) = V(n-1,k) + V(n,k-1) + V(n-1,k-1);

Esta función da 102 para n = 3, k = 5.

Sin la memoria, esto se vuelve muy lento para calcular incluso para números bastante modestos. Si visualiza el procesamiento como un árbol, cada nodo es una invocación de V () expandiéndose a tres hijos que tendría 186,268,135,991,213,676,920,832 V (n, 0) = 1 hojas en el cálculo de V (32,32) ... Implementado ingenuamente esta función rápidamente se vuelve indiscutible en el hardware disponible.

Pero muchas de las ramas infantiles en el árbol son duplicados exactos entre sí, aunque no de una manera trivial que podría eliminarse fácilmente como la función factorial. Con la memorización podemos fusionar todas esas ramas duplicadas. De hecho, con la memorización V (32,32) solo ejecuta V () 1024 (n * m) veces, lo que es una aceleración de un factor de 10 ^ 21 (que se hace más grande a medida que n, k crece, obviamente) más o menos a cambio por una cantidad bastante pequeña de memoria. :) Encuentro este tipo de cambio fundamental en la complejidad de un algoritmo mucho más emocionante que el simple almacenamiento en caché. Puede hacer que los problemas intratables sean fáciles.

Como los números de python son naturalmente grandes, puede implementar esta fórmula en python con memorización utilizando un diccionario y claves de tupla en solo 9 líneas. Inténtalo y pruébalo sin la memoria.

Memoización es sólo una palabra elegante para el almacenamiento en caché. Si los cálculos son más caros que extraer la información del caché, entonces es una buena cosa. El problema es que las CPU son rápidas y la memoria es lenta. Así que he encontrado que el uso de la memoria es generalmente mucho más lento que simplemente rehacer el cálculo.

Por supuesto, hay otras técnicas disponibles que realmente le dan una mejora significativa. Si sé que necesito f (10) para cada iteración de un bucle, entonces lo almacenaré en una variable. Dado que no hay una búsqueda de caché, esto suele ser una victoria.

EDITAR

Adelante y votame todo lo que quieras. Eso no cambiará el hecho de que necesitas hacer evaluaciones comparativas reales y no solo comenzar a lanzar ciegamente todo en tablas hash.

Si conoce su rango de valores en tiempo de compilación, diga porque está usando n! y n es un int de 32 bits, entonces será mejor que uses una matriz estática.

Si su rango de valores es grande, digamos un doble, entonces su tabla hash puede crecer tanto que se convierta en un problema serio.

Si el mismo resultado se usa una y otra vez junto con un objeto dado, entonces puede tener sentido almacenar ese valor con el objeto.

En mi caso, descubrí que más del 90% del tiempo las entradas para una iteración dada eran las mismas que la última iteración. Eso significa que solo necesitaba mantener la última entrada y el último resultado y solo volver a calcular si la entrada cambiaba. Este fue un orden de magnitud más rápido que el uso de la memoria para ese algoritmo.

Uno de los usos para una forma de memoización es en el análisis del árbol de juegos. En el análisis de árboles de juegos no triviales (piense en ajedrez, vaya, puente), calcular el valor de una posición es una tarea no trivial y puede llevar un tiempo significativo. Una implementación ingenua simplemente usará este resultado y luego lo descartará, pero todos los jugadores fuertes lo almacenarán y usarán si la situación vuelve a surgir. Puedes imaginar que en el ajedrez hay innumerables formas de alcanzar la misma posición.

Para lograr esto, en la práctica se requiere una experimentación y afinaciones infinitas, pero es seguro decir que los programas de ajedrez por computadora no serían lo que son hoy sin esta técnica.

En AI, el uso de dicha memoria se suele denominar "tabla de transposición".

Uso la memorización todo el tiempo cuando migro datos de un sistema a otro (ETL). El concepto es que si una función siempre devolverá la misma salida para el mismo conjunto de entradas, puede tener sentido almacenar en caché el resultado, especialmente si toma un tiempo calcularlo. Al hacer ETL, a menudo se repiten las mismas acciones muchas veces en gran cantidad de datos, y el rendimiento suele ser crítico. Cuando el rendimiento no es una preocupación o es despreciable, probablemente no tenga sentido memorizar sus métodos. Como todo, usa la herramienta adecuada para el trabajo.

Memoization es una técnica para almacenar las respuestas a los subproblemas, de modo que un programa no necesita volver a resolver los mismos subproblemas más adelante.

A menudo es una técnica importante para resolver problemas mediante la programación dinámica .

Imagine enumerar todas las rutas desde la esquina superior izquierda de una cuadrícula hasta la esquina inferior derecha de una cuadrícula. Muchos de los caminos se superponen entre sí. Puede memorizar las soluciones calculadas para cada punto de la cuadrícula, construyendo desde la parte inferior derecha, de vuelta hasta la parte superior izquierda. Esto reduce el tiempo de computación de "ridículo" a "manejable".

Otro uso es: Haz una lista de los factoriales del número 0 al 100. ¡No quieres calcular 100! utilizando 100 * 99 * ... * 1 . ¡Ya calculaste 99! , ¡entonces reutilice esa respuesta y simplemente multiplique 100 veces la respuesta por 99! . Puede memorizar la respuesta en cada uno de estos pasos (de 1 a 100) para ahorrar una cantidad significativa de cómputo.

Para un punto de datos, para mi problema de resolución de grillas anterior (el problema es de un desafío de programación):

Memoized

real 0m3.128s user 0m1.120s sys 0m0.064s

No memorizado (que maté, porque estaba cansado de esperar ... así que esto está incompleto)

real 24m6.513s user 23m52.478s sys 0m6.040s

La memoria intercambia tiempo por espacio.

La memorización puede convertir el tiempo exponencial (o peor) en tiempo lineal (o mejor) cuando se aplica a problemas de naturaleza recursiva múltiple. El costo es generalmente O (n) de espacio.

El ejemplo clásico es calcular la secuencia de Fibonacci. La definición del libro de texto es la relación de recurrencia:

F (n) = F (n-1) + F (n-2)

Implementado ingenuamente, se ve así:

int fib(int n) { if (n == 0) { return 0; } else if (n == 1) { return 1; } else { return fib(n-1) + fib(n-2); } }

Puede ver que el tiempo de ejecución crece exponencialmente con n porque cada una de las sumas parciales se calcula varias veces.

Implementado con memoización, se ve así (torpe pero funcional):

int fib(int n) { static bool initialized = false; static std::vector<int> memo; if (!initialized) { memo.push_back(0); memo.push_back(1); initialized = true; } if (memo.size() > n) { return memo[n]; } else { const int val = fib(n-1) + fib(n-2); memo.push_back(val); return val; } }

Programando estas dos implementaciones en mi computadora portátil, para n = 42, la versión ingenua toma 6.5 segundos. La versión memorizada toma 0.005 segundos (todo el tiempo del sistema, es decir, está enlazado a E / S). Para n = 50, la versión memorizada todavía toma 0.005 segundos, y la versión ingenua finalmente terminó después de 5 minutos y 7 segundos (no importa que ambos hayan desbordado un entero de 32 bits).