Ocaml memoization failed to apply to Fibonacci series
I tried to use memoization method to optimize Fibonacci caculation. My code:
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;;
Output:
Time lapse:0.357187
Time lapse:0.353663
There is not much difference. Why? And even worse when I tried to calculate Fibonacci at 40 using
running_time ggfib 40;;
running_time memoggfib 40;;
The program runs in an endless loop and stops the output.
What's wrong here? What problem did I not care about?
I modified the code above to introduce a "static" vtable for memoization.
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;;
It still acts like basically the same one. I haven't seen much improvement ....
Time lapse:0.581918
Time lapse:0.577813
source to share
(* 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 *)
source to share
It seems to me that you just resemble the most external calls. Internal calls are ggfib, not (memo ggfib).
When you call memoggfib, the memo function remembers the value of the outermost call. However, internal calls are handled by ggfib (the function you passed to the memo). If you look at the definition of ggfib, you can see that it calls itself. It doesn't call (memo ggfib).
I don't see any way to turn a regular (recursive) function into memoized. It will not automatically call up internal memory within itself.
If you start with a reminder function, I can still see "node binding" problems.
source to share