haskell - proyectos - Memorización automática en lenguajes de programación funcionales
proyectos con haskell (5)
Haskell no parece hacer memoria automática. ¿O entiendo algo mal?
No, Haskell no. Sin embargo, las expresiones compartidas se calculan solo una vez. En el ejemplo dado por Paul Johnson x se almacena en el montón como un thunk . Tanto y como z pueden referirse a x cuando x está dentro del alcance, y se refieren a la misma ubicación. Una vez que x tiene que evaluarse, se evaluará solo una vez y solo se mantendrá el resultado de la evaluación. Así que esto no es realmente una memorización, sino un resultado de la implementación.
¿Hay otros lenguajes que hacen memoria automática (es decir, implícita, no explícita)?
He visto al decorador @memoized aparecer en algún código fuente de Python. Por supuesto, puedes crear tu propio decorador / implementación para él. Complete con LRU y otras políticas que quiera usar.
¿Cuáles son las formas comunes de implementar la memorización?
No hay una forma real common de implementar la memorización. Para patrones parecidos a fib (solo un argumento, que es un número) la memorización tal como se usa en el ejemplo de fib Uno podría idear una solución general (el de hasmaps) y funcionará, pero también podría ser insuficiente para su problema específico .
Con la memorización tiene efectos secundarios, por lo que probablemente desee que la memoria caché viva en la mónada de estado. Sin embargo, en general, desea mantener sus algoritmos lo más puros posible, de modo que si tiene recursión, ya se está metiendo en un lío. Esto se debe a que llamarás recursivamente a la versión memorada de la función, pero debe ejecutarse en la mónada de estado, de modo que ahora tu función completa debe ejecutarse en la mónada de estado. Esto también afecta la pereza, pero podrías probar la mónada estado perezoso .
Teniendo esto en cuenta: una buena memorización automática es muy difícil de lograr. Pero puedes recorrer un largo camino fácilmente. Las funciones de memorización automática probablemente implican la transformación del programa, donde la escritura de cosas en un punto fijo podría ser de gran ayuda.
Editar: estoy más interesado en el problema que describí, es decir, cómo implementar dicho límite. Cualquier referencia a cualquier documento que aborde esto sería muy agradable.
Una vez que tenga el mecanismo básico de memorización, podría ajustar las funciones de búsqueda y almacenamiento para su tabla de memorando para implementar LRU o algún otro mecanismo para mantener el consumo de memoria pequeño. Tal vez pueda obtener la idea de LRU a partir de este ejemplo de C ++ .
Siempre pensé que Haskell haría algún tipo de memoración inteligente automática. Por ejemplo, la implementación ingenua de Fibonacci
fib 0 = 0
fib 1 = 1
fib n = fib (n-2) + fib (n-1)
Sería rápido por eso. Ahora leo this y parece que estaba equivocado, parece que Haskell no hace memoria automática. ¿O entiendo algo mal?
¿Hay otros lenguajes que hacen memoria automática (es decir, implícita, no explícita)?
¿Cuáles son las formas comunes de implementar la memorización? En todas las implementaciones de muestra que he visto, usan un hashmap pero no hay ningún límite en su tamaño. Obviamente, esto no funcionaría en la práctica porque necesitas algún tipo de límite. Y dado eso, se vuelve más complicado porque cuando alcanzas el límite, debes descartar algunos datos. Y allí se vuelve complicado: ¿el límite puede ser dinámicamente y, a menudo, las funciones utilizadas deben tener un límite más alto que las funciones menos utilizadas? ¿Y qué entrada tiras cuando alcanzas el límite? ¿Solo el último usado? En ese caso, debe tener sus datos también ordenados además. Puede usar alguna combinación de una lista vinculada y un mapa hash para lograr eso. ¿Es esa la manera común?
¿Podría vincular (o referirse) a algunas implementaciones comunes en el mundo real?
Gracias, Albert
Editar: estoy más interesado en el problema que describí, es decir, cómo implementar dicho límite. Cualquier referencia a cualquier documento que aborde esto sería muy agradable.
Editar: algunos pensamientos propios con una implementación de ejemplo (que tiene un límite) se pueden encontrar here .
Editar: No estoy tratando de resolver un problema específico en una aplicación específica. Estoy buscando soluciones generales para la memorización que puedan aplicarse globalmente a todas las funciones de un programa (funcional puro) (por lo tanto, los algoritmos que no implementan un límite de memoria no son una solución). Por supuesto que (probablemente) no hay una solución óptima / mejor. Pero esto hace que mi pregunta no sea menos interesante.
Para probar esa solución, pensé en agregarlo a Haskell como una optimización. Realmente me pregunto qué tan bien funcionaría eso.
Y me pregunto si alguien ya lo hizo.
Dije en un comentario que sus requisitos sonaban a basura. Pensé esto porque estás interesado en administrar un conjunto limitado de memoria, purgarlo de vez en cuando para que no se repita.
Ahora que lo pienso, es más como un algoritmo de reemplazo de página de memoria virtual. Puede leer esa página de Wikipedia para varios enfoques utilizados para resolver ese tipo de problema, como "no usado recientemente", "envejecimiento", "reloj", "segunda oportunidad", etc.
Sin embargo, la memorización no suele hacerse restringiendo los resultados retenidos; la mutación requerida para los algoritmos mencionados anteriormente es generalmente no haskellish. Pero no dejes que eso te desanime. Usted tiene ideas interesantes que podrían ser valiosas adiciones a la exploración de las posibilidades de memorización en Haskell realizadas hasta el momento.
A veces, un problema de memorización en particular se presta bien a la memoria limitada. Por ejemplo, la alineación de dos secuencias génicas se puede hacer con la Programación Dinámica (ver la alineación # Secuencia de la Programación Dinámica de Wikipedia) con una tabla de memorización bidimensional. Pero dado que la solución de DP para una celda determinada solo depende de los resultados de la fila anterior, puede comenzar desde abajo y descartar las filas que están a más de 1 de distancia de la fila actual. Los números de Fibonacci son los mismos: solo necesita los dos números anteriores en la secuencia para calcular el siguiente. Puede descartar algo antes si todo lo que le interesa es el n. ° número.
La mayoría de las memorizaciones son para acelerar algoritmos recursivos donde hay subproblemas compartidos. Muchos de estos problemas no tienen una forma fácil de secuenciar las evaluaciones para descartar los resultados que ya no necesita. En ese punto, simplemente está adivinando, usando heurísticas (como la frecuencia de uso) para determinar quién obtiene la cantidad de acceso al recurso limitado.
No hay exactamente una respuesta, pero esta página: this ofrece ideas sobre Memoization en Haskell y también muestra una implementación basada en listas de la secuencia de Fibonacci que puede ser de interés.
No, Haskell no hace memorización automática de funciones. Lo que hace es almacenar valores, así que si tiene
x = somethingVeryLong
y en otro lugar en el mismo alcance que tiene
y = f x
z = g x
entonces x solo se computará una vez.
Este paquete muestra cómo se pueden almacenar los valores memorados utilizando una variedad de claves y tablas de búsqueda. La memorización se utiliza normalmente en una sola invocación de una función más grande, de modo que los valores memorados no permanecen para siempre (lo cual, como usted dice, sería un problema). Si quieres una memoria que también olvide valores antiguos usando LRU o algo así, entonces creo que probablemente necesites ponerlo en una mónada estatal o algo así; no puedes hacer que Haskell se comporte así usando el enfoque convencional de memorización.
Por ejemplo, al implementar la memorización automática, puede consultar el lenguaje de programación Factor y su vocabulario Memoization . Por ejemplo, simple generador de números de Fibonacci:
: fib ( n -- n )
dup 1 > [
[ 1 - fib ]
[ 2 - fib ]
bi +
] when ;
puede ser memorable reemplazando ":" palabra con "MEMO:"
MEMO: fib ( n -- n )
dup 1 > [
[ 1 - fib ]
[ 2 - fib ]
bi +
] when ;
En ese caso, las entradas de fib y las salidas correspondientes se almacenarán de forma transparente dentro del diccionario en memoria.
La sintaxis del lenguaje de factores puede ser confusa :). Te recomiendo que veas una presentación en video de Google Tech Talks sobre Factor para entender, cómo es posible implementar la memorización de esa manera.