7

可以改进“原始”斐波那契递归过程

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 将在表达式中看到重复的函数调用并记忆（重用）它们。

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

怎么提高

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

以相同的方式？

4

2 回答 2

16

rgrinberg 提供的解决方案可以泛化，以便我们可以记忆任何函数。我将使用关联列表而不是哈希表。但这并不重要，您可以轻松地将我的所有示例转换为使用哈希表。

首先，这里有一个函数memo，它接受另一个函数并返回它的记忆版本。这是 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了 compute f x，任何由 进行的递归调用f都不会被memo. 为了解决这个问题，我们需要做两件事：

  1. 在这种递归的定义中，f我们需要将递归调用替换为对“稍后提供”的函数的调用（这将是 的记忆化版本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

为了演示它是如何工作的，让我们记住朴素的斐波那契函数。我们需要编写它以便它接受一个额外的参数，我将其称为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

于 2013-01-24T14:22:10.367 回答
11

您几乎可以执行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

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

于 2013-01-22T10:18:43.230 回答