Recherche…
Mémo simple
La mémorisation consiste à mettre en cache les résultats des fonctions pour éviter de calculer le même résultat plusieurs fois. Ceci est utile lorsque vous travaillez avec des fonctions qui effectuent des calculs coûteux.
Nous pouvons utiliser une fonction factorielle simple comme exemple:
let factorial index =
let rec innerLoop i acc =
match i with
| 0 | 1 -> acc
| _ -> innerLoop (i - 1) (acc * i)
innerLoop index 1
L'appel de cette fonction plusieurs fois avec le même paramètre entraîne le même calcul encore et encore.
La mémorisation nous aidera à mettre en cache le résultat factoriel et à le renvoyer si le même paramètre est transmis à nouveau.
Voici une implémentation simple de mémo:
// memoization takes a function as a parameter
// This function will be called every time a value is not in the cache
let memoization f =
// The dictionary is used to store values for every parameter that has been seen
let cache = Dictionary<_,_>()
fun c ->
let exist, value = cache.TryGetValue (c)
match exist with
| true ->
// Return the cached result directly, no method call
printfn "%O -> In cache" c
value
| _ ->
// Function call is required first followed by caching the result for next call with the same parameters
printfn "%O -> Not in cache, calling function..." c
let value = f c
cache.Add (c, value)
value
La fonction de memoization prend simplement une fonction comme paramètre et renvoie une fonction avec la même signature. Vous pouvez le voir dans la signature de la méthode f:('a -> 'b) -> ('a -> 'b) . De cette façon, vous pouvez utiliser la mémorisation de la même manière que si vous appeliez la méthode factorielle.
Les appels à printfn doivent montrer ce qui se passe lorsque nous appelons la fonction plusieurs fois; ils peuvent être enlevés en toute sécurité.
Utiliser la mémorisation est facile:
// Pass the function we want to cache as a parameter via partial application
let factorialMem = memoization factorial
// Then call the memoized function
printfn "%i" (factorialMem 10)
printfn "%i" (factorialMem 10)
printfn "%i" (factorialMem 10)
printfn "%i" (factorialMem 4)
printfn "%i" (factorialMem 4)
// Prints
// 10 -> Not in cache, calling function...
// 3628800
// 10 -> In cache
// 3628800
// 10 -> In cache
// 3628800
// 4 -> Not in cache, calling function...
// 24
// 4 -> In cache
// 24
Mémo dans une fonction récursive
En utilisant l'exemple précédent de calcul de la factorielle d'un entier, mettez dans la table de hachage toutes les valeurs de factorielles calculées à l'intérieur de la récursivité, qui n'apparaissent pas dans la table.
Comme dans l'article sur la mémorisation , nous déclarons une fonction f qui accepte un paramètre de fonction fact et un paramètre entier. Cette fonction f comprend des instructions pour calculer la factorielle de n fact(n-1) .
Cela permet de gérer la récursivité par la fonction retournée par memorec et non par la fact elle-même et éventuellement arrêter le calcul si le fact(n-1) valeur a été déjà calculé et est situé dans la table de hachage.
let memorec f =
let cache = Dictionary<_,_>()
let rec frec n =
let value = ref 0
let exist = cache.TryGetValue(n, value)
match exist with
| true ->
printfn "%O -> In cache" n
| false ->
printfn "%O -> Not in cache, calling function..." n
value := f frec n
cache.Add(n, !value)
!value
in frec
let f = fun fact n -> if n<2 then 1 else n*fact(n-1)
[<EntryPoint>]
let main argv =
let g = memorec(f)
printfn "%A" (g 10)
printfn "%A" "---------------------"
printfn "%A" (g 5)
Console.ReadLine()
0
Résultat:
10 -> Not in cache, calling function...
9 -> Not in cache, calling function...
8 -> Not in cache, calling function...
7 -> Not in cache, calling function...
6 -> Not in cache, calling function...
5 -> Not in cache, calling function...
4 -> Not in cache, calling function...
3 -> Not in cache, calling function...
2 -> Not in cache, calling function...
1 -> Not in cache, calling function...
3628800
"---------------------"
5 -> In cache
120