OCaml中的记忆？

Question

有可能改进"原始"Fibonacci递归程序

Fib[n_] := If[n < 2, n, Fib[n - 1] + Fib[n - 2]]

同

Fib[n_] := Fib[n] = If[n < 2, n, Fib[n - 1] + Fib[n - 2]]

在Wolfram Mathematica.

第一个版本将遭受指数爆炸,而第二个版本将不会,因为Mathematica将在表达式中看到重复的函数调用并记住(重用)它们.

是否有可能在OCaml中做同样的事情？

如何提高

let rec fib n = if n<2 then n else fib (n-1) + fib (n-2);;

以相同的方式？

Answer 1

rgrinberg提供的解决方案可以推广,以便我们可以记住任何函数.我将使用关联列表而不是哈希表.但它并不重要,您可以轻松地将我的所有示例转换为使用哈希表.

首先,这是一个函数memo,它接受另一个函数并返回它的memoized版本.这是nlucaroni在其中一条评论中提出的建议:

let memo f =
  let m = ref [] in
    fun x ->
      try
        List.assoc x !m
      with
      Not_found ->
        let y = f x in
          m := (x, y) :: !m ;
          y

该函数memo f保留了m到目前为止计算的结果列表.当被要求计算时f x,首先检查m是否f x已经计算过.如果是,则返回结果,否则实际计算f x,将结果存储在中m,然后返回结果.

在递归的memo情况下,上面存在问题f.一旦memo调用f计算f x,任何递归调用f都不会被拦截memo.要解决这个问题,我们需要做两件事:

1. 在这种递归的定义中,f我们需要用对"稍后提供"的函数的调用来代替递归调用(这将是memoized版本f).

2. 在memo f我们需要提供f与承诺"的功能,当你想递归调用,你应该叫".

这导致以下解决方案:

let memo_rec f =
  let m = ref [] in
  let rec g x =
    try
      List.assoc x !m
    with
    Not_found ->
      let y = f g x in
        m := (x, y) :: !m ;
        y
  in
    g

为了演示这是如何工作的,让我们记住天真的Fibonacci函数.我们需要编写它以便它接受一个额外的参数,我将调用它self.这个参数是函数应该使用的,而不是递归调用自身:

let fib self = function
    0 -> 1
  | 1 -> 1
  | n -> self (n - 1) + self (n - 2)

现在要记住fib,我们计算

let fib_memoized = memo_rec fib

欢迎您试一试,看看fib_memoized 50即时返回.(通常的天真递归定义memo f在哪里不是这样f.)

Answer 2

你几乎完成了mathematica版本的功能,但手动:

let rec fib = 
  let cache = Hashtbl.create 10 in
  begin fun n ->
    try Hashtbl.find cache n
    with Not_found -> begin
      if n < 2 then n
      else 
        let f = fib (n-1) + fib (n-2) in
        Hashtbl.add cache n f; f
    end
  end

在这里,我选择一个哈希表来存储已计算的结果,而不是重新计算它们.请注意,您应该仍然注意整数溢出,因为我们使用的是普通而不是大的int.