在OCaml中进行记忆化? [英] Memoization in OCaml?

问题描述

可以改善原始"斐波那契递归程序

It is possible to improve "raw" Fibonacci recursive procedure

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中.

in Wolfram Mathematica.

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

First version will suffer from exponential explosion while second one will not since Mathematica will see repeating function calls in expression and memoize (reuse) them.

是否可以在OCaml中执行相同的操作?

Is it possible to do the same in OCaml?

如何改进

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

以同样的方式?

推荐答案

您几乎可以手动执行mathematica版本的操作:

You pretty much do what the mathematica version does but manually:

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

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

Here I choose a hashtable to store already computed results instead of recomputing them. Note that you should still beware of integer overflow since we are using a normal and not a big int.

这篇关于在OCaml中进行记忆化?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！