F#
memoization

Eenvoudige memoisatie

Memoisatie bestaat uit cachefunctie resultaten om te voorkomen dat hetzelfde resultaat meerdere keren wordt berekend. Dit is handig wanneer u werkt met functies die dure berekeningen uitvoeren.

We kunnen een eenvoudige faculteit als voorbeeld gebruiken:

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

    innerLoop index 1

Door deze functie meerdere keren met dezelfde parameter aan te roepen, wordt steeds opnieuw dezelfde berekening uitgevoerd.

Memoisatie helpt ons het facultaire resultaat te cachen en terug te sturen als dezelfde parameter opnieuw wordt doorgegeven.

Hier is een eenvoudige implementatie van memo's:

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

De memoization neemt gewoon een functie als parameter en retourneert een functie met dezelfde handtekening. Je zou dit kunnen zien in de methode handtekening f:('a -> 'b) -> ('a -> 'b) . Op deze manier kunt u memo's gebruiken op dezelfde manier als wanneer u de facultaire methode aanroept.

De printfn aanroepen laten zien wat er gebeurt als we de functie meerdere keren aanroepen; ze kunnen veilig worden verwijderd.

Memoisatie gebruiken is eenvoudig:

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

Memoisatie in een recursieve functie

Gebruik het vorige voorbeeld van het berekenen van de faculteit van een geheel getal, zet in de hashtabel alle waarden van de faculteit berekend in de recursie, die niet in de tabel voorkomen.

Zoals in het artikel over memoization verklaren we een functie f die een functie parameter accepteert fact en een integer parameter. Deze functie f bevat instructies voor het berekenen van de faculteit van n uit fact(n-1) .

Dit maakt het mogelijk om recursie af te handelen door de functie die door memorec en niet door fact zelf en mogelijk de berekening te stoppen als de fact(n-1) waarde al is berekend en zich in de hashtabel bevindt.

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

Resultaat:

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