Résultats de la mise en cache Haskell d'une fonction

Question

J'ai une fonction qui prend un paramètre et produit un résultat. Malheureusement, cela prend assez de temps pour que la fonction produise le résultat. La fonction est appelée assez souvent avec la même entrée, c'est pourquoi il serait pratique de mettre en cache les résultats. Quelque chose comme

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

Je regardais dans Data.Array et bien que le tableau est paresseux, je dois l'initialiser avec une liste de paires (en utilisant ListArray) - ce qui est peu pratique. Si la 'clé' est par exemple le type 'Double', je ne peux pas l'initialiser du tout, et même si je peux théoriquement affecter un entier à chaque entrée possible, j'ai plusieurs dizaines de milliers d'entrées possibles et je n'en utilise qu'une poignée. J'aurais besoin d'initialiser le tableau (ou, de préférence, une table de hachage, car seule une poignée de resutls sera utilisée) en utilisant une fonction au lieu d'une liste. Mise à jour: Je lis les articles sur les mémos et, pour autant que je le comprenne, le MemoTrie pourrait fonctionner comme je le souhaite. Peut être. Quelqu'un pourrait-il essayer de produire la fonction 'cachedFunction'? Préférablement pour une fonction lente qui prend 2 arguments Double? Ou, alternativement, cela prend un argument Int dans un domaine de ~ [0..1 milliard] qui ne mangerait pas toute la mémoire?

Answer 1

Eh bien, il y a Data.HashTable. Les tables de hachage n'ont pas tendance à bien fonctionner avec des données immuables et la transparence référentielle, donc je ne pense pas que cela soit très utile.

Pour un petit nombre de valeurs, les stocker dans un arbre de recherche (tel que Data.Map) serait probablement assez rapide. Si vous pouvez supporter de faire quelques manigances de votre Double s, une solution plus robuste serait d'utiliser une structure semblable à trie, comme Data.IntMap; ceux-ci ont des temps de recherche proportionnels principalement à la longueur de la clé, et à peu près constante dans la taille de la collection. Si Int est trop limitatif, vous pouvez explorer Hackage pour trouver des bibliothèques qui sont plus flexibles dans le type de clé utilisé.

Quant à la façon de mettre en cache les résultats, je pense que ce que vous voulez est généralement appelé "memoization". Si vous voulez calculer et mémoriser des résultats à la demande, l'essentiel de la technique est de définir une structure de données indexées contenant tous les résultats possibles, de telle sorte que lorsque vous demandez un résultat spécifique, il ne force que les calculs nécessaires pour obtenir la réponse que tu veux. Les exemples courants impliquent généralement l'indexation dans une liste, mais le même principe devrait s'appliquer à toute structure de données non stricte. En règle générale, les valeurs non fonctionnelles (y compris les structures de données récursives infinies) seront souvent mises en cache par le moteur d'exécution, mais pas les résultats de la fonction. L'astuce consiste donc à placer tous vos calculs dans une définition de niveau supérieur. dépend de tous les arguments.

Édition: Exemple MemoTrie ahoy!

Ceci est une preuve de concept rapide et sale; de meilleures approches peuvent exister.

{-# 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 

Notez les extensions GHC utilisées par le package MemoTrie; J'espère que ce n'est pas un problème. Chargez-le dans GHCi et essayez d'appeler slow par rapport à memoSlow avec quelque chose comme (10^6) ou (10^7) pour le voir en action.

Généraliser ceci à des fonctions prenant plusieurs arguments ou quoi que ce soit devrait être assez simple. Pour plus de détails sur l'utilisation de MemoTrie, vous pouvez trouver this blog post by its author utile.

Answer 2

Voir memoization

Answer 3

Je ne sais pas spécifiquement le haskell, mais que diriez-vous de conserver les réponses existantes dans une structure de données hachée (que l'on pourrait appeler un dictionnaire ou une hashmap)? Vous pouvez envelopper votre fonction lente dans une autre fonction qui vérifie d'abord la carte et n'appelle la fonction lente que si elle n'a pas trouvé de réponse.

Vous pouvez le faire fantaisie en limitant la taille de la carte à une certaine taille et quand il atteint cela, en jetant l'entrée la moins récemment utilisée. Pour cela, vous devez en outre conserver une carte des mappages clé-horodatage.

Answer 4

Vous pouvez écrire la fonction lente en tant que fonction d'ordre supérieur, renvoyant une fonction elle-même. Ainsi vous pouvez faire tout le pré-traitement dans la fonction lente et la partie qui est différente dans chaque calcul dans la fonction renvoyée (j'espère rapide). Un exemple pourrait ressembler à ceci: (code SML, mais l'idée doit être clair)

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

J'ai plusieurs dizaines de milliers entrées possibles et je n'utilise que en fait une poignée. J'aurais besoin d'initialiser le tableau ... en utilisant une fonction au lieu d'une liste.

je partirais avec listArray (start, end) (map func [start..end])

• func ne sont pas vraiment appelé ci-dessus. Haskell est paresseux et crée des thunks qui seront évalués lorsque la valeur est réellement requise. Lorsque vous utilisez un tableau normal, vous devez toujours initialiser ses valeurs.
• Donc, le travail requis pour créer ces thunk est nécessaire de toute façon.
• Plusieurs dizaines de milliers sont loin d'être nombreux. Si vous aviez des trillions alors je suggérerais d'utiliser une table de hachage yada yada

Answer 6

Je vais ajouter ma propre solution, qui semble être assez lente aussi. Le premier paramètre est une fonction qui renvoie Int32 - qui est l'identifiant unique du paramètre. Si vous voulez l'identifier de manière unique par différents moyens (par exemple par 'id'), vous devez changer le deuxième paramètre dans H.new à une autre fonction de hachage. Je vais essayer de savoir comment utiliser Data.Map et tester si j'obtiens des résultats plus rapides.

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

Le système d'exécution de GHC contient explicitement un certain nombre d'outils pour prendre en charge la mémorisation.

Malheureusement, la mémorisation n'est pas vraiment une affaire de taille unique, il existe donc plusieurs approches différentes que nous devons prendre en charge afin de faire face aux différents besoins des utilisateurs.

Vous pouvez trouver le writeup 1999 d'origine utile car il comprend plusieurs mises en œuvre à titre d'exemples:

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