F# 程式設計/快取

F#：快取

快取通常用於重用已計算的資料。F# 提供了許多內建技術來快取資料以供將來使用。

偏函式

F# 會自動快取任何不帶引數的函式的值。當 F# 遇到一個不帶引數的函式時，F# 只會評估該函式一次，並在每次訪問該函式時重複使用它的值。比較以下內容

let isNebraskaCity_bad city =
    let cities =
        printfn "Creating cities Set"
        ["Bellevue"; "Omaha"; "Lincoln"; "Papillion"]
        |> Set.ofList
        
    cities.Contains(city)
    
let isNebraskaCity_good =
    let cities =
        printfn "Creating cities Set"
        ["Bellevue"; "Omaha"; "Lincoln"; "Papillion"]
        |> Set.ofList
        
    fun city -> cities.Contains(city)

這兩個函式接受和返回相同的值，但它們的行為卻大不相同。以下是 fsi 中輸出的比較

isNebraskaCity_bad

isNebraskaCity_good

> let isNebraskaCity_bad city =
    let cities =
        printfn "Creating cities Set"
        ["Bellevue"; "Omaha"; "Lincoln"; "Papillion"]
        |> Set.of_list
        
    cities.Contains(city);;

val isNebraskaCity_bad : string -> bool

> isNebraskaCity_bad "Lincoln";;
Creating cities Set
val it : bool = true

> isNebraskaCity_bad "Washington";;
Creating cities Set
val it : bool = false

> isNebraskaCity_bad "Bellevue";;
Creating cities Set
val it : bool = true

> isNebraskaCity_bad "St. Paul";;
Creating cities Set
val it : bool = false

> let isNebraskaCity_good =
    let cities =
        printfn "Creating cities Set"
        ["Bellevue"; "Omaha"; "Lincoln"; "Papillion"]
        |> Set.of_list
        
    fun city -> cities.Contains(city);;
Creating cities Set

val isNebraskaCity_good : (string -> bool)

> isNebraskaCity_good "Lincoln";;
val it : bool = true

> isNebraskaCity_good "Washington";;
val it : bool = false

> isNebraskaCity_good "Bellevue";;
val it : bool = true

> isNebraskaCity_good "St. Paul";;
val it : bool = false

isNebraskaCity_bad 的實現強制 F# 在每次呼叫時重新建立內部集合。另一方面，isNebraskaCity_good 是一個初始化為函式 fun city -> cities.Contains(city) 的值，因此它只建立一次內部集合，並在所有後續呼叫中重複使用它。

注意： 在內部，isNebraskaCity_bad 編譯為一個靜態函式，該函式在每次呼叫時都會構造一個集合。isNebraskaCity_good 編譯為一個靜態只讀屬性，其值在靜態建構函式中初始化。

這種區別通常很微妙，但它可能會對應用程式的效能產生巨大影響。

記憶化

"記憶化" 是一個花哨的詞，意思是計算出的值儲存在查詢表中，而不是在每次後續呼叫時重新計算。執行時間長的純函式（即沒有副作用的函式）是記憶化的良好候選者。考慮計算斐波那契數的遞迴定義

> #time;;

--> Timing now on

> let rec fib n =
    if n = 0I then 0I
    elif n = 1I then 1I
    else fib (n - 1I) + fib(n - 2I);;
Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0

val fib : Math.bigint -> Math.bigint

> fib 35I;;
Real: 00:00:23.557, CPU: 00:00:23.515, GC gen0: 2877, gen1: 3, gen2: 0
val it : Math.bigint = 9227465I

超過 fib 35I，函式的執行時間變得難以忍受。對 fib 函式的每次遞迴呼叫都會丟棄所有對 fib(n - 1I) 和 fib(n - 2I) 的中間計算，使其執行時間複雜度約為 O(2^n)。如果我們將所有這些中間計算儲存在查詢表中會怎樣？以下是 fib 函式的記憶化版本

> #time;;

--> Timing now on

> let rec fib =
    let dict = new System.Collections.Generic.Dictionary<_,_>()
    fun n ->
        match dict.TryGetValue(n) with
        | true, v -> v
        | false, _ -> 
            let temp =
                if n = 0I then 0I
                elif n = 1I then 1I
                else fib (n - 1I) + fib(n - 2I)
            dict.Add(n, temp)
            temp;;

val fib : (Math.bigint -> Math.bigint)

> fib 35I;;
Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : Math.bigint = 9227465I

好多了！這個版本的 fib 函式幾乎可以立即執行。事實上，由於我們只計算 fib(n) 的值一次，字典查詢是一個 O(1) 操作，因此這個 fib 函式的執行時間為 O(n)。

注意所有記憶化邏輯都包含在 fib 函式中。我們可以編寫一個更通用的函式來記憶化任何函式

let memoize f =
    let dict = new System.Collections.Generic.Dictionary<_,_>()
    fun n ->
        match dict.TryGetValue(n) with
        | (true, v) -> v
        | _ ->
            let temp = f(n)
            dict.Add(n, temp)
            temp
            
let rec fib = memoize(fun n ->
    if n = 0I then 0I
    elif n = 1I then 1I
    else fib (n - 1I) + fib (n - 2I) )

注意： 非常重要的是要記住上面的實現不是執行緒安全的 - 如果字典將被多個執行緒訪問，則應在新增/檢索專案之前鎖定字典。

此外，雖然字典查詢在恆定時間內發生，但字典使用的雜湊函式可能需要任意長的時間才能執行（這在字串中尤其如此，其中雜湊字串所需的時間與其長度成正比）。因此，記憶化的函式完全有可能比非記憶化的函式效能更差。始終分析程式碼以確定是否需要最佳化，以及記憶化是否真正提高了效能。

延遲值

F# 的 lazy 資料型別是一個有趣的原語，它會延遲對值的評估，直到實際需要該值為止。一旦計算出來，延遲值就會被快取以供以後重複使用

> let x = lazy(printfn "I'm lazy"; 5 + 5);;

val x : Lazy<int> = <unevaluated>

> x.Force();; (* Should print "I'm lazy" *)
I'm lazy
val it : int = 10

> x.Force();; (* Value already computed, should not print "I'm lazy" again *)
val it : int = 10

F# 使用一些編譯器魔法來避免在宣告時評估表示式 (printfn "I'm lazy"; 5 + 5)。延遲值可能是最簡單的快取形式，但它們可以用來建立一些有趣而複雜的資料結構。例如，兩個 F# 資料結構是在延遲值之上實現的，即 F# 的延遲列表和 Seq.cache 方法。

延遲列表和快取的序列表示可能無限數量元素的任意序列。這些元素在第一次訪問時被計算並快取，但在再次列舉序列時不會被重新計算。以下是 fsi 中的演示

> let x = seq { for a in 1 .. 10 -> printfn "Got %i" a; a } |> Seq.cache;;

val x : seq<int>

> let y = Seq.take 5 x;;

val y : seq<int>

> Seq.reduce (+) y;;
Got 1
Got 2
Got 3
Got 4
Got 5
val it : int = 15

> Seq.reduce (+) y;; (* Should not recompute values *)
val it : int = 15

> Seq.reduce (+) x;; (* Values 1 through 5 already computed, should only compute 6 through 10 *)
Got 6
Got 7
Got 8
Got 9
Got 10
val it : int = 55

前一頁：度量單位

索引

下一頁：主動模式