F#
Memoization

Einfaches Memo

Memoization besteht aus Caching-Funktionsergebnissen, um zu vermeiden, dass dasselbe Ergebnis mehrmals berechnet wird. Dies ist nützlich, wenn Sie mit Funktionen arbeiten, die kostspielige Berechnungen durchführen.

Wir können eine einfache Faktorfunktion als Beispiel verwenden:

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

    innerLoop index 1

Ein mehrfacher Aufruf dieser Funktion mit demselben Parameter führt immer wieder zu derselben Berechnung.

Memoization hilft uns, das faktorielle Ergebnis zwischenzuspeichern und zurückzugeben, wenn der gleiche Parameter erneut übergeben wird.

Hier ist eine einfache Memo-Implementierung:

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

Die memoization Funktion übernimmt einfach eine Funktion als Parameter und gibt eine Funktion mit derselben Signatur zurück. Sie könnten dies in der Methodensignatur f:('a -> 'b) -> ('a -> 'b) . Auf diese Weise können Sie die Memoisierung auf dieselbe Weise verwenden, als würden Sie die factorial-Methode aufrufen.

Die printfn Aufrufe sollen zeigen, was passiert, wenn wir die Funktion mehrmals aufrufen. Sie können sicher entfernt werden.

Die Verwendung von Memoization ist einfach:

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

Memoisierung in einer rekursiven Funktion

In dem vorherigen Beispiel der Berechnung der Fakultät einer Ganzzahl geben Sie alle in der Rekursion berechneten Werte der Fakultät in die Hashtabelle ein, die nicht in der Tabelle erscheinen.

Wie im Artikel zum Memoisieren deklarieren wir eine Funktion f , die einen Funktionsparameter- fact und einen Ganzzahl-Parameter akzeptiert. Diese Funktion f enthält Anweisungen zur Berechnung der Fakultät von n aus fact(n-1) .

Dies ermöglicht es, Rekursion durch die von memorec zurückgegebene memorec und nicht fact selbst memorec und möglicherweise die Berechnung zu stoppen, wenn der memorec fact(n-1) bereits berechnet wurde und sich in der Hash-Tabelle befindet.

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

Ergebnis:

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