ocaml memoization失敗時應用於斐波那契數列

Question

我試圖使用memoization技術來優化斐波那契的計算。我的代碼是：

let memo f = 
    let vtable = ref [] in 
    let rec match_function x vt= 
    match vt with 
     |(x',y)::_ when x=x' -> y 
     |_::l -> 
     match_function x l 
     |[] -> 
     let y = (f x) in 
     vtable := (x,y):: !vtable; 
     y 
    in 
    (fun x -> (match_function x !vtable));; 

let rec ggfib = function 
    0|1 as i -> i 
    |x -> ggfib(x-1) + ggfib(x-2);; 

let memoggfib = memo ggfib;; 

let running_time f x = 
    let start_time = Sys.time() in 
    let y = f x in 
    let finish_time = Sys.time() in 
    Printf.printf "Time lapse:%f\n" (finish_time -. start_time); 
    y;; 


running_time ggfib 30;; 
running_time memoggfib 30;; 

輸出是：

Time lapse:0.357187 
Time lapse:0.353663 

不同的是沒有那麼多。爲什麼？而更糟的是，當我嘗試使用

running_time ggfib 40;; 
running_time memoggfib 40;; 

程序在40計算斐波那契似乎碰上了死循環，並停止輸出。

這裏有什麼問題？我沒有照顧什麼問題？

我改變了上面的代碼，爲memoization引入了一個'靜態'vtable。

let rec ggfib = function 
    0|1 as i -> i 
    |x -> ggfib(x-1) + ggfib(x-2);; 

let running_time x0 = 
    let vtable = ref [] in 
    let start_time = Sys.time() in 
    let x = ref 1 in 
    let rec match_function ff x vt= 
    match vt with 
     |(x',y)::_ when x=x' -> y 
     |_::l -> 
     match_function ff x l 
     |[] -> 
     let y = (ff x) in 
     vtable := (x,y):: !vtable; 
     y 
    in 
    let y=ref 1 in 
    while !x<x0 do 
    y:= match_function ggfib !x !vtable; 
    x:=!x+1; 
    done; 
    let finish_time = Sys.time() in 
    Printf.printf "Time lapse:%f\n" (finish_time -. start_time); 
    y;; 


let running_time2 x0= 
    let start_time = Sys.time() in 
    let x = ref 1 in 
    while !x<x0 do 
    ggfib !x; 
    x:=!x+1; 
    done; 
    let finish_time = Sys.time() in 
    Printf.printf "Time lapse:%f\n" (finish_time -. start_time);; 

running_time 40;; 
running_time2 30;; 

它仍然作爲基本相同。我沒有看到明顯的改善......

Time lapse:0.581918 
Time lapse:0.577813 

Answer 1

(* a "derecursified" version of fibonacci: recursive calls are 
    replaced by calls to a function passed as parameter *) 
let rec fib_derec f = function 
| 0|1 as i -> i 
| n -> f (n - 1) + f (n - 2) 

(* to get the fibonacci back we need to compute a fixpoint: 
    fib_derec should get passed 'fib' as parameter, 
    which we will define in term of fib_derec 
*) 
let rec fib n = fib_derec fib n 

let test = Array.init 10 fib 
(* [|0; 1; 1; 2; 3; 5; 8; 13; 21; 34|] *) 

(* we can make this construction generic *) 
let rec fix derec input = derec (fix derec) input 

let fib = fix fib_derec 

let test = Array.init 10 fib 
(* [|0; 1; 1; 2; 3; 5; 8; 13; 21; 34|] *) 


(* Trick: we can use this tying-the-knot operator to insert 
    memoization "between the recursive calls" of the recursive function *) 

let rec memo_fix table derec = 
    fun input -> 
    try Hashtbl.find table input with Not_found -> 
     let result = derec (memo_fix table derec) input in 
     Hashtbl.add table input result; 
     result 

let fib_table = Hashtbl.create 100 
let fib = memo_fix fib_table fib_derec 

let test = Array.init 10 fib 
(* [|0; 1; 1; 2; 3; 5; 8; 13; 21; 34|] *) 

let test2 = fib 1000 
(* -591372213: overflow, but quick result *) 

Answer 2

它在我看來像你只是記憶最外層的呼叫。內部調用是ggfib，而不是（備忘錄ggfib）。

當你調用memoggfib時，備忘錄函數會記住最外層調用的值。但是，內部調用由ggfib（您傳遞給備忘錄的函數）處理。如果你看看ggfib的定義，你會看到它自己調用。它不會調用（備忘錄ggfib）。

我沒有看到一種方法來將一個普通的（遞歸）函數變成一個memoized的。它不會自動在內部自動調用自己的記憶版本。

如果您從一個旨在被記憶的函數開始，我仍然會遇到「綁結」的問題。