Ocaml Memoization fehlgeschlagen, wenn auf Fibonacci-Serie angewendet

Question

Ich habe versucht, Memoisierungstechnik zu verwenden, um die Berechnung von Fibonacci zu optimieren. Mein Code ist:

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;; 

Die Ausgabe lautet:

Time lapse:0.357187 
Time lapse:0.353663 

Der Unterschied nicht so viel ist .. Warum ?? Und noch schlimmer, als ich versuchte, Fibonacci zu berechnen, bei 40 unter Verwendung

running_time ggfib 40;; 
running_time memoggfib 40;; 

Das Programm erscheint in einer Endlosschleife laufen und zur Ausgabe zu stoppen.

Was ist hier falsch? Auf welches Problem habe ich nicht geachtet?

Ich habe den obigen Code geändert, um eine 'statische' vtable für Memoization einzuführen.

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;; 

Es funktioniert immer noch als das gleiche Prinzip. Ich sah keine wesentliche Verbesserung ....

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

Es sieht für mich aus, als ob Sie nur die äußersten Anrufe memotisieren. Die inneren Aufrufe sind an ggfib, nicht an (memo ggfib).

Wenn Sie memoggfib aufrufen, speichert die Memo-Funktion den Wert des äußersten Anrufs. Die inneren Aufrufe werden jedoch von ggfib (der Funktion, die Sie an Memo übergeben) behandelt. Wenn Sie sich die Definition von ggfib ansehen, sehen Sie, dass sie sich selbst aufruft. Es ruft nicht auf (Memo ggfib).

Ich sehe keine Möglichkeit, eine gewöhnliche (rekursive) Funktion in eine memoisierte Funktion umzuwandeln. Es wird nicht automatisch die Memo-Version von sich selbst intern aufrufen.

Wenn Sie mit einer Funktion beginnen, die als Memo gespeichert werden soll, sehe ich immer noch Probleme, die den Knoten lösen.