Resultados de caché de Haskell de una función

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 así como

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

que estaba investigando Data.Array y aunque la matriz es perezoso, se tiene que inicializar con una lista de pares (usando ListArray) - que es poco 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) utilizando una función en lugar de una lista.

Actualización: Estoy leyendo los artículos de memorización y, por lo que yo entiendo, la MemoTrie podría funcionar de la manera que 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

Bueno, hay 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, guardarlos en un árbol de búsqueda (como Data.Map) probablemente sea lo suficientemente rápido. Si puede aguantar 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 "memoization". 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 que quieres 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

Edit: MemoTrie example ahoy!

Esta es una prueba de concepto rápida y sucia; 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 

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

Generalizando 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 this blog post by its author útil.

Answer 2

Ver memoization

Answer 3

no sé Haskell específicamente, pero ¿qué hay de mantener respuestas existentes en alguna estructura de datos hash (que 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.

Se podría hacer que sea elegante al limitar el tamaño del mapa a un cierto tamaño y cuando llega a eso, tirar de la entrada menos utilizado recientemente. Para esto, también necesitaría mantener un mapa de las asignaciones de clave a marca de tiempo.

Answer 4

Usted puede escribir la función lenta como una función de orden superior, el retorno de una función en sí. 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 tener este aspecto: (SML código, pero la idea debe ser claro)

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

Tengo varias decenas de miles de posibles entradas y sólo utilizo realmente 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 consigo llamado anteriormente. 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 ser muchas. Si tuviera billones, le sugiero usar una tabla hash yada

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 forma ú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 que admiten explícitamente la memorización.

Desafortunadamente, memoization no es realmente una sola talla para todos asunto, por lo que hay varios enfoques diferentes que tenemos que apoyar con el fin de hacer frente a las diferentes necesidades de los usuarios.

Usted puede encontrar el original de 1999 valoración crítica útil ya que incluye varias implementaciones como ejemplos:

Stretching the Storage Manager: Weak Pointers and Stable Names in Haskell por Simon Peyton Jones, Simon Marlow, y Conal Elliott