Память ocaml не удалась при применении к серии Фибоначчи

Question

Я пытался использовать технику запоминания, чтобы оптимизировать расчет Фибоначчи. Мой код:

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

Разница не такая большая .. Почему ?? И еще хуже, когда я пытался вычислить Фибоначчи на 40, используя

running_time ggfib 40;;
running_time memoggfib 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

Мне кажется, ты просто запоминаешь самые отдаленные звонки. Внутренние вызовы для ggfib, а не для (memo ggfib).

Когда вы вызываете memoggfib, функция memo запоминает значение самого внешнего вызова. Однако внутренние вызовы обрабатываются ggfib (функцией, которую вы передали в memo). Если вы посмотрите на определение ggfib, вы увидите, что оно вызывает само себя. Он не звонит (записка ggfib).

Я не вижу способа превратить обычную (рекурсивную) функцию в запоминающуюся. Он не будет автоматически вызывать запомненную версию самого себя.

Если вы начнете с функции, предназначенной для запоминания, я все еще вижу проблемы с «завязыванием узла».

Answer 2

(* 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 *)