F#
Memorización

Memorización simple

La memorización consiste en resultados de la función de almacenamiento en caché para evitar calcular el mismo resultado varias veces. Esto es útil cuando se trabaja con funciones que realizan cálculos costosos.

Podemos usar una función factorial simple como ejemplo:

let factorial index =
    let rec innerLoop i acc =
        match i with
        | 0 | 1 -> acc
        | _ -> innerLoop (i - 1) (acc * i)

    innerLoop index 1

Llamar a esta función varias veces con el mismo parámetro resulta en el mismo cálculo una y otra vez.

La memorización nos ayudará a almacenar en caché el resultado factorial y devolverlo si se pasa nuevamente el mismo parámetro.

Aquí hay una implementación de memoria simple:

// 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 función de memoization simplemente toma una función como parámetro y devuelve una función con la misma firma. Podría ver esto en la firma del método f:('a -> 'b) -> ('a -> 'b) . De esta manera, puede utilizar la memorización de la misma manera que si estuviera llamando al método factorial.

Las llamadas a printfn son para mostrar lo que sucede cuando llamamos a la función varias veces; Se pueden eliminar de forma segura.

Usar la memorización es fácil:

// 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

Memoización en una función recursiva.

Utilizando el ejemplo anterior de cálculo del factorial de un número entero, ponga en la tabla hash todos los valores de factorial calculados dentro de la recursión, que no aparecen en la tabla.

Como en el artículo sobre memoización , declaramos una función f que acepta un fact parámetro de función y un parámetro entero. Esta función f , incluye instrucciones para calcular el factorial de n desde fact(n-1) .

Esto permite manejar la recursión mediante la función devuelta por memorec y no por el fact mismo y posiblemente detener el cálculo si el valor de fact(n-1) ya se ha calculado y se encuentra en la tabla hash.

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

Resultado:

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