खोज…
सरल संस्मरण
कई बार एक ही परिणाम की गणना से बचने के लिए संस्मरण में कैशिंग फ़ंक्शन परिणाम होते हैं। यह उपयोगी है जब ऐसे कार्यों के साथ काम करना जो महंगा संगणना करते हैं।
हम उदाहरण के रूप में एक साधारण फैक्टरियल फ़ंक्शन का उपयोग कर सकते हैं:
let factorial index =
let rec innerLoop i acc =
match i with
| 0 | 1 -> acc
| _ -> innerLoop (i - 1) (acc * i)
innerLoop index 1
एक ही पैरामीटर के साथ इस फ़ंक्शन को कई बार कॉल करने से एक ही गणना में बार-बार परिणाम आता है।
संस्मरण हमें तथ्यात्मक परिणाम को कैश करने में मदद करेगा और यदि वही पैरामीटर फिर से पारित हो जाता है तो इसे वापस कर देगा।
यहाँ एक सरल संस्मरण कार्यान्वयन है:
// 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
एक पुनरावर्ती समारोह में संस्मरण
किसी पूर्णांक के भाज्य की गणना के पिछले उदाहरण का उपयोग करते हुए, पुनरावृत्ति के अंदर गणना किए गए भाज्य के सभी मानों को हैश तालिका में डालें, जो तालिका में दिखाई नहीं देते हैं।
जैसा कि संस्मरण के बारे में लेख में, हम एक फ़ंक्शन f घोषित करते हैं जो फ़ंक्शन पैरामीटर fact और पूर्णांक पैरामीटर को स्वीकार करता है। इस फ़ंक्शन f , fact(n-1) से n के भाज्य की गणना करने के निर्देश शामिल हैं।
यह memorec द्वारा 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