caching - Resultados de caché Haskell de una función

memoization

Question

Tengo una función que toma un parámetro y produce un resultado. Desafortunadamente, lleva bastante tiempo para que la función produzca el resultado. La función se llama con bastante frecuencia con la misma entrada, por eso sería conveniente si pudiera almacenar en caché los resultados. Algo como

let cachedFunction = createCache slowFunction
in (cachedFunction 3.1) + (cachedFunction 4.2) + (cachedFunction 3.1)

Estaba buscando en Data.Array y aunque el array es flojo, necesito inicializarlo con una lista de pares (usando listArray), lo que no es práctico. Si la ''clave'' es, por ejemplo, el tipo ''Doble'', no puedo inicializarlo en absoluto, e incluso si teóricamente puedo asignar un Entero a cada entrada posible, tengo varias decenas de miles de entradas posibles y solo uso un puñado. Tendría que inicializar la matriz (o, preferiblemente, una tabla hash, ya que solo se usarán un puñado de resutls) usando una función en lugar de una lista.

Actualización: estoy leyendo los artículos de memorización y, por lo que yo entiendo, el MemoTrie podría funcionar como yo quiero. Tal vez. ¿Podría alguien tratar de producir la ''función en caché''? Preferiblemente para una función lenta que toma 2 argumentos dobles? ¿O, alternativamente, eso toma un argumento Int en un dominio de ~ [0.100 millones] que no se comerá toda la memoria?

Answer 1

Tengo varias decenas de miles de entradas posibles y solo uso un puñado. Necesitaría inicializar la matriz ... usando una función en lugar de una lista.

Me gustaría ir con listArray (start, end) (map func [start..end])

• func realmente no se llama más arriba. Haskell es flojo y crea thunks que se evaluarán cuando el valor realmente se requiera.
• Al usar una matriz normal, siempre debe inicializar sus valores. Entonces el trabajo requerido para crear estos thunk es necesario de todos modos.
• Varias decenas de miles están lejos de mucho. Si tuviera billones, sugeriría usar una tabla hash yada yada

Answer 2

Bueno, está Data.HashTable . Sin embargo, las tablas hash no suelen jugar muy bien con datos inmutables y transparencia referencial, por lo que no creo que se vea demasiado útil.

Para una pequeña cantidad de valores, almacenarlos en un árbol de búsqueda (como Data.Map ) probablemente sea lo suficientemente rápido. Si puede soportar hacer algunos cambios en su Double s, una solución más robusta sería usar una estructura tipo trie, como Data.IntMap ; estos tienen tiempos de búsqueda proporcionales principalmente a la longitud de la clave, y aproximadamente constante en el tamaño de la colección. Si Int es demasiado limitante, puede buscar en Hackage para encontrar las bibliotecas que son más flexibles en el tipo de clave utilizada.

En cuanto a cómo almacenar en caché los resultados, creo que lo que quiere se suele llamar "memoria" . Si desea calcular y memorizar los resultados según demanda, la esencia de la técnica es definir una estructura de datos indexados que contenga todos los resultados posibles , de tal forma que cuando solicite un resultado específico, fuerce solo los cálculos necesarios para obtener la respuesta. usted quiere. Los ejemplos comunes generalmente implican la indexación en una lista, pero el mismo principio debería aplicarse para cualquier estructura de datos no estricta. Como regla general, los valores que no son de función (incluidas las estructuras de datos recursivas infinitas) a menudo serán almacenados en caché por el tiempo de ejecución, pero no por los resultados de la función, por lo que el truco es ajustar todos sus cálculos dentro de una definición de nivel superior que no depende de cualquier argumento

Editar: ejemplo de MemoTrie ahoy!

Esta es una prueba rápida y sucia de concepto; mejores enfoques pueden existir.

{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeOperators #-}
import Data.MemoTrie
import Data.Binary
import Data.ByteString.Lazy hiding (map)

mangle :: Double -> [Int]
mangle = map fromIntegral . unpack . encode

unmangle :: [Int] -> Double
unmangle = decode . pack . map fromIntegral

instance HasTrie Double where
    data Double :->: a = DoubleTrie ([Int] :->: a)
    trie f = DoubleTrie $ trie $ f . unmangle
    untrie (DoubleTrie t) = untrie t . mangle

slow x 
    | x < 1 = 1
    | otherwise = slow (x / 2) + slow (x / 3)

memoSlow :: Double -> Integer
memoSlow = memo slow

Observe las extensiones GHC utilizadas por el paquete MemoTrie; con suerte eso no es un problema. Póngalo en GHCi e intente llamar slow vs. memoSlow con algo como (10 ^ 6) o (10 ^ 7) para verlo en acción.

Generalizar esto para funciones que toman múltiples argumentos o lo que sea, debería ser bastante sencillo. Para obtener más detalles sobre el uso de MemoTrie, puede encontrar útil esta publicación del blog por su autor .

Answer 3

No conozco específicamente a Haskell, pero ¿qué hay de mantener las respuestas existentes en alguna estructura de datos hash (podría llamarse un diccionario o hashmap)? Puede ajustar su función lenta en otra función que primero verifique el mapa y solo llame a la función lenta si no ha encontrado una respuesta.

Podrías hacerlo elegante limitando el tamaño del mapa a un cierto tamaño y, cuando llega a eso, descartando la entrada utilizada menos recientemente. Para esto, también necesitaría mantener un mapa de las asignaciones de clave a marca de tiempo.

Answer 4

Puede escribir la función lenta como una función de orden superior, devolviendo una función en sí misma. Por lo tanto, puede hacer todo el preprocesamiento dentro de la función lenta y la parte que es diferente en cada cálculo en la función devuelta (ojalá sea rápido). Un ejemplo podría verse así: (código SML, pero la idea debería ser clara)

fun computeComplicatedThing (x:float) (y:float) = (* ... some very complicated computation *)
fun computeComplicatedThingFast = computeComplicatedThing 3.14 (* provide x, do computation that needs only x *)
val result1 = computeComplicatedThingFast 2.71 (* provide y, do computation that needs x and y *)
val result2 = computeComplicatedThingFast 2.81
val result3 = computeComplicatedThingFast 2.91

Answer 5

Ver memorización

Answer 6

Agregaré mi propia solución, que también parece ser bastante lenta. El primer parámetro es una función que devuelve Int32, que es el identificador único del parámetro. Si desea identificarlo de manera única por diferentes medios (por ejemplo, mediante ''id''), debe cambiar el segundo parámetro en H.new a una función hash diferente. Trataré de descubrir cómo usar Data.Map y probar si obtengo resultados más rápidos.

import qualified Data.HashTable as H
import Data.Int
import System.IO.Unsafe

cache :: (a -> Int32) -> (a -> b) -> (a -> b)
cache ident f = unsafePerformIO $ createfunc
    where 
        createfunc = do
            storage <- H.new (==) id
            return (doit storage)

        doit storage = unsafePerformIO . comp
            where 
                comp x = do
                    look <- H.lookup storage (ident x)

                    case look of
                        Just res -> return res
                        Nothing -> do
                            result <- return (f x)
                            H.insert storage (ident x) result
                            return result

Answer 7

Hay una serie de herramientas en el sistema de tiempo de ejecución de GHC para admitir explícitamente la memorización.

Desafortunadamente, la memorización no es realmente una cuestión de talla única para todos, por lo que hay varios enfoques diferentes que debemos apoyar para poder hacer frente a las diferentes necesidades de los usuarios.

Puede encontrar la redacción original de 1999 útil, ya que incluye varias implementaciones como ejemplos:

Extender el Administrador de almacenamiento: Punteros débiles y nombres estables en Haskell por Simon Peyton Jones, Simon Marlow y Conal Elliott