Поиск…
Простое напоминание
Воспоминание состоит из результатов функции кеширования, чтобы избежать вычисления одного и того же результата несколько раз. Это полезно при работе с функциями, выполняющими дорогостоящие вычисления.
В качестве примера мы можем использовать простую факториальную функцию:
let factorial index =
let rec innerLoop i acc =
match i with
| 0 | 1 -> acc
| _ -> innerLoop (i - 1) (acc * i)
innerLoop index 1
Вызов этой функции несколько раз с тем же параметром приводит к тому же вычислению снова и снова.
Воспоминание поможет нам кэшировать факторный результат и вернуть его, если один и тот же параметр будет передан снова.
Вот простая реализация 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
просто принимает функцию как параметр и возвращает функцию с той же сигнатурой. Это можно увидеть в сигнатуре метода f:('a -> 'b) -> ('a -> 'b)
. Таким образом, вы можете использовать memoization так же, как если бы вы вызывали факториальный метод.
printfn
должны показывать, что происходит, когда мы вызываем функцию несколько раз; они могут быть удалены безопасно.
Использование memoization очень просто:
// 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
Воспоминание в рекурсивной функции
Используя предыдущий пример вычисления факториала целого числа, поместите в хеш-таблицу все значения факториала, вычисленные внутри рекурсии, которые не отображаются в таблице.
Как и в статье о memoization , мы объявляем функцию f
которая принимает fact
параметра функции и целочисленный параметр. Эта функция f
включает в себя инструкции для вычисления факториала n
из fact(n-1)
.
Это позволяет обрабатывать рекурсию функцией, возвращаемой memorec
а не самим fact
, и, возможно, останавливать вычисление, если значение fact(n-1)
уже рассчитано и находится в хеш-таблице.
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
Результат:
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