記憶化

記憶化是一種強大的技術，可以加速簡單的遞迴演算法，而無需改變演算法的工作方式。這是通過「記住」計算的結果來完成的，因此先前計算的結果永遠不必重新計算。我們將使用命令式資料結構（例如陣列和雜湊表）來說明此原理。

以下是摘錄自「記憶化」頁面，出自於書籍OCaml Programming: Correct + Efficient + Beautiful，經許可在此重製。

費波那契數列

讓我們再次考慮計算第 n 個費波那契數的問題。天真的遞迴實作會花費指數時間，因為相同的費波那契數會一遍又一遍地重新計算

let rec fib n = if n < 2 then 1 else fib (n - 1) + fib (n - 2)

如果我們在計算費波那契數時記錄它們，就可以避免這種多餘的工作。想法是，每當我們計算 f n 時，我們會將其儲存在以 n 索引的表格中。在這種情況下，索引鍵是整數，因此我們可以使用陣列來實作此表格

let fibm n =
  let memo : int option array = Array.make (n + 1) None in
  let rec f_mem n =
    match memo.(n) with
    | Some result -> (* computed already *) result
    | None ->
        let result =
          if n < 2 then 1 else f_mem (n - 1) + f_mem (n - 2)
        in
        (* record in table *)
        memo.(n) <- Some result;
        result
  in
  f_mem n

在 fibm 內定義的函式 f_mem 包含原始的遞迴演算法，只是在執行計算之前，它會先檢查結果是否已經計算並儲存在表格中，如果是，則直接傳回結果。

我們如何分析這個函式的執行時間？如果我們不包括它碰巧進行的任何遞迴呼叫所花費的時間，則單次呼叫 f_mem 所花費的時間為 O(1)。現在，我們尋找一種方法，透過尋找正在進行的進度的度量來限制遞迴呼叫的總數。

一個好的進度度量選擇，不僅在此處，而且也適用於記憶化的許多用途，是表格中非空條目的數量（即包含 Some n 而不是 None 的條目）。每次 f_mem 進行兩個遞迴呼叫時，它也會將非空條目的數量增加一（用新值填寫表格中先前為空的條目）。由於表格只有 n 個條目，因此對 f_mem 的呼叫總數只能是 O(n)，總執行時間為 O(n)（因為我們在上面確定每次呼叫花費 O(1) 時間）。因此，記憶化加速將執行時間從指數時間減少到線性時間，這是一個巨大的改變——例如，對於 n=4，記憶化加速的幅度超過一百萬倍！

能夠應用記憶化的關鍵在於存在重複求解的常見子問題。因此，我們可以利用一些額外的儲存空間來節省重複的計算。

儘管此程式碼使用命令式結構（特別是陣列更新），但副作用在函式 fibm 之外是不可見的。因此，從客戶的角度來看，fibm 是函數式的。無需提及內部使用的命令式實作（即良性的副作用）。

使用高階函式的記憶化

既然我們已經看到記憶化一個函式的範例，讓我們使用高階函式來記憶化任何函式。首先，考慮記憶化非遞迴函式 f 的情況。在這種情況下，我們只需要建立一個雜湊表，該雜湊表儲存每次呼叫 f 時對應的值（並且為了記憶化多參數函式，我們可以使用柯里化和反柯里化轉換為單參數函式）。

let memo f =
  let h = Hashtbl.create 11 in
  fun x ->
    try Hashtbl.find h x
    with Not_found ->
      let y = f x in
      Hashtbl.add h x y;
      y

然而，對於遞迴函式，需要修改遞迴呼叫結構。這可以抽象出來，獨立於被記憶化的函式

let memo_rec f =
  let h = Hashtbl.create 16 in
  let rec g x =
    try Hashtbl.find h x
    with Not_found ->
      let y = f g x in
      Hashtbl.add h x y;
      y
  in
  g

現在，我們可以利用這種通用的記憶化技術，稍微重寫上面的原始 fib 函式

let fib_memo =
  let rec fib self n =
    if n < 2 then 1 else self (n - 1) + self (n - 2)
  in
  memo_rec fib

純粹為了好玩：派對最佳化

假設我們想為一間組織圖為二元樹的公司舉辦派對。每位員工都有一個相關的「歡樂值」，而我們希望受邀員工的總歡樂值最大化。然而，如果員工的上司被邀請，該員工就不會感到歡樂，因此我們絕不邀請在組織圖中相連的兩位員工。（這個問題較不歡樂的名稱是樹的最大權重獨立集。）對於有 n 位員工的組織圖，存在 2ⁿ 種可能的邀請名單，因此比較每個有效邀請名單的歡樂值的樸素演算法需要指數時間。

我們可以利用記憶化將此轉換為線性時間的演算法。首先，我們定義一個變體類型來表示員工。每個節點的整數是歡樂值。

type tree = Empty | Node of int * tree * tree

現在，我們如何以遞迴的方式解決這個問題？一個重要的觀察是，在任何樹中，不包含根節點的最佳邀請名單將會是左子樹和右子樹的最佳邀請名單的聯集。而包含根節點的最佳邀請名單將會是不包含各自根節點的左子節點和右子節點的最佳邀請名單的聯集。因此，擁有針對必須邀請根節點的情況以及排除根節點的情況來最佳化邀請名單的函式似乎很有用。我們將這兩個函式稱為 `party_in` 和 `party_out`。然後，`party` 的結果只是這兩個函式的最大值。

module Unmemoized = struct
  type tree =
    | Empty
    | Node of int * tree * tree

  (* Returns optimum fun for t. *)
  let rec party t = max (party_in t) (party_out t)

  (* Returns optimum fun for t assuming the root node of t
   * is included. *)
  and party_in t =
    match t with
    | Empty -> 0
    | Node (v, left, right) -> v + party_out left + party_out right

  (* Returns optimum fun for t assuming the root node of t
   * is excluded. *)
  and party_out t =
    match t with
    | Empty -> 0
    | Node (v, left, right) -> party left + party right
end

這段程式碼具有指數執行時間。但是請注意，`party` 函式只有 n 種可能的不同呼叫。如果我們將程式碼變更為記憶化這些呼叫的結果，效能將會與 n 成線性關係。以下是一個會記憶化 `party` 結果並同時計算實際邀請名單的版本。請注意，這段程式碼會直接在樹中記憶化結果。

module Memoized = struct
  (* This version memoizes the optimal fun value for each tree node. It
     also remembers the best invite list. Each tree node has the name of
     the employee as a string. *)
  type tree =
    | Empty
    | Node of
        int * string * tree * tree * (int * string list) option ref

  let rec party t : int * string list =
    match t with
    | Empty -> (0, [])
    | Node (_, name, left, right, memo) -> (
        match !memo with
        | Some result -> result
        | None ->
            let infun, innames = party_in t in
            let outfun, outnames = party_out t in
            let result =
              if infun > outfun then (infun, innames)
              else (outfun, outnames)
            in
            memo := Some result;
            result)

  and party_in t =
    match t with
    | Empty -> (0, [])
    | Node (v, name, l, r, _) ->
        let lfun, lnames = party_out l and rfun, rnames = party_out r in
        (v + lfun + rfun, name :: lnames @ rnames)

  and party_out t =
    match t with
    | Empty -> (0, [])
    | Node (_, _, l, r, _) ->
        let lfun, lnames = party l and rfun, rnames = party r in
        (lfun + rfun, lnames @ rnames)
end

為什麼記憶化對於解決這個問題如此有效？如同費波那契演算法，我們有重疊子問題的特性，其中樸素的遞迴實作多次使用相同的參數呼叫 `party` 函式。記憶化會儲存所有這些呼叫。此外，派對最佳化問題具有最佳子結構的特性，這表示問題的最佳解是從子問題的最佳解計算而來。並非所有最佳化問題都具有此特性。有效使用記憶化來解決最佳化問題的關鍵在於找出如何撰寫一個實作演算法並具有兩個特性的遞迴函式。有時，這需要仔細思考。