F#
메모

간단한 메모

Memoization은 동일한 결과를 여러 번 계산하지 않도록 함수 결과를 캐싱하는 것으로 구성됩니다. 이것은 값 비싼 계산을 수행하는 함수로 작업 할 때 유용합니다.

간단한 계승 함수를 예제로 사용할 수 있습니다.

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) 와 같은 방법으로 서명을 볼 수 있습니다. 이렇게하면 계승 방법을 사용하는 것과 같은 방법으로 메모를 사용할 수 있습니다.

printfn 호출은 함수를 여러 번 호출 할 때 어떤 일이 일어나는지 보여주는 것입니다. 안전하게 제거 할 수 있습니다.

메모를 사용하는 것은 쉽습니다.

// 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 에 대한 기사에서와 같이, 함수 매개 변수 fact 와 정수 매개 변수를 받아들이는 함수 f 를 선언합니다. 이 함수 f 는 fact(n-1) 에서 n 의 계승을 계산하기위한 지침을 포함합니다.

이것은 fact 자체가 아니라 memorec 의해 반환 된 함수에 의한 재귀를 처리 할 수 ​​있으며 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