ocaml memoization failed when applied to Fibonacci series

Question

I tried to use memoization technique to optimize the caculation of Fibonacci. My code is:

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

The output is:

Time lapse:0.357187
Time lapse:0.353663

The difference is not that much.. Why?? And even worse, when I tried to calculate Fibonacci at 40 using

running_time ggfib 40;;
running_time memoggfib 40;;

The program appears to run into a infinite loop and stop outputting.

What is wrong here? What problem I did not take care of?

I changed 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 as the basically same. I didn't see a significant improvement....

Time lapse:0.581918
Time lapse:0.577813

Answer 1

It looks to me like you're just memoizing the outermost calls. The inner calls are to ggfib, not to (memo ggfib).

When you call memoggfib, the memo function will remember the value of the outermost call. However, the inner calls are handled by ggfib (the function that you passed to memo). If you look at the definition of ggfib, you see that it calls itself. It doesn't call (memo ggfib).

I don't see a way to turn an ordinary (recursive) function into a memoized one. It won't automatically call the memoized version of itself internally.

If you start with a function that's intended to be memoized, I still see problems "tying the knot".