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 で。

最初のバージョンでは指数関数的な爆発が起こりますが、2 番目のバージョンではそうではありません。これは、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 がコメントの 1 つで提案したものです。

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一度computeをmemo呼び出すと、 によって行われた再帰呼び出しは によってインターセプトされません。この問題を解決するには、次の 2 つのことを行う必要があります。ff xfmemo

  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である where には当てはまりません。)f

于 2013-01-24T14:22:10.367 に答える
11

あなたはほとんど数学バージョンが行うことをしますが、手動で行います：

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ではなく通常のintを使用しているため、整数のオーバーフローに注意する必要があることに注意してください。

于 2013-01-22T10:18:43.230 に答える