フィボナッチシリーズに適用されたときにocaml memoizationが失敗しました

Question

私はフィボナッチのcaculationを最適化するためのメモアイテクニックを使用しようとしました。私のコードは次のとおりです。

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でフィボナッチを計算しようとしたとき、さらに悪い無限ループに実行し、出力を停止するように見えます。

ここで何が間違っていますか？私が気にしなかった問題は何ですか？

上記のコードを変更して、メモ化のための静的な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を呼び出すと、memo関数は最も外側の呼び出しの値を記憶します。しかし、内側の呼び出しは、ggfib（メモに渡した関数）によって処理されます。 ggfibの定義を見ると、それが自分自身を呼び出すことがわかります。それは呼び出さない（メモggfib）。

普通の（再帰的な）関数をメモしたものにする方法はありません。それは自動的に内部のmemoizedバージョンを呼び出すことはありません。

メモを取っておきたい機能から始めても、私はまだ「結び目をつける」という問題があります。