F#
memoisation

Enkel memoization

Memoization består av cachefunktionsresultat för att undvika att beräkna samma resultat flera gånger. Detta är användbart när du arbetar med funktioner som gör kostsamma beräkningar.

Vi kan använda en enkel fabriksfunktion som exempel:

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

    innerLoop index 1

Att ringa denna funktion flera gånger med samma parameter resulterar i samma beräkning om och om igen.

Memoization hjälper oss att cache factorialresultatet och returnera det om samma parameter skickas igen.

Här är en enkel implementering av memoization:

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

memoization tar helt enkelt en funktion som en parameter och returnerar en funktion med samma signatur. Du kan se detta i metodsignaturen f:('a -> 'b) -> ('a -> 'b) . På det här sättet kan du använda memisering på samma sätt som om du kallade den faktormetoden.

printfn samtalen ska visa vad som händer när vi anropar funktionen flera gånger; de kan tas bort på ett säkert sätt.

Att använda memoization är enkelt:

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

Memoering i en rekursiv funktion

Använd det föregående exemplet för att beräkna faktoriet för ett heltal, lägg i hashtabellen alla värden på faktoria som beräknas inuti rekursionen, som inte visas i tabellen.

Liksom i artikeln om memoisation , deklarerar vi en funktion f som accepterar en funktionsparameter fact och en heltal parameter. Denna funktion f , innehåller instruktioner för att beräkna faktorn för n från fact(n-1) .

Detta gör det möjligt att hantera rekursion genom den funktion som returneras av memorec och inte av fact och eventuellt stoppa beräkningen om fact(n-1) redan har beräknats och finns i hashtabellen.

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

Resultat:

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