7

これは、インターネットでランダムに見つけた動的プログラミングに関するいくつかの講義で読んだ質問です。(私は卒業しており、動的計画法の基本を既に知っています)

メモ化が必要な理由を説明するセクションでは、つまり

// psuedo code 
int F[100000] = {0};
int fibonacci(int x){
    if(x <= 1) return x;
    if(F[x]>0) return F[x];
    return F[x] = fibonacci(x-1) + fibonacci(x-2);
}

メモ化を使用しないと、多くのサブ問題が何度も再計算され、複雑さが非常に高くなります。

それから、あるページのメモには答えのない質問があります。これはまさに私が聞きたいことです。ここでは、正確な表現とそれが示す例を使用しています。

自動メモ化: 多くの関数型プログラミング言語 (Lisp など) には、メモ化のサポートが組み込まれています。

命令型言語 (Java など) ではないのはなぜですか?

メモが提供するLISPの例（効率的であると主張しています）：

(defun F (n)
    (if
        (<= n 1)
        n
        (+ (F (- n 1)) (F (- n 2)))))

それが提供するJavaの例（指数関数的であると主張しています）

static int F(int n) {
  if (n <= 1) return n;
  else return F(n-1) + F(n-2);
}

これを読む前は、いくつかのプログラミング言語にメモ化のサポートが組み込まれていることさえ知りませんでした。

注記の主張は正しいですか？はいの場合、命令型言語がそれをサポートしていないのはなぜですか?

4

3 に答える 3

3

メモ化のサポートは、ファーストクラスの機能を備えているにすぎません。

ある特定のケースで Java のバージョンをメモ化したい場合は、ハッシュテーブルを作成し、既存の値をチェックするなど、明示的に記述できます。残念ながら、関数をメモ化するためにこれを簡単に一般化することはできません。第一級の関数を持つ言語は、関数の記述とそれらのメモ化をほぼ直交する問題にします。

基本的なケースは簡単ですが、再帰呼び出しを考慮する必要があります。OCaml のような静的に型付けされた関数型言語では、メモ化された関数は、メモ化されていないバージョンを呼び出すため、自分自身を再帰的に呼び出すことはできません。selfただし、既存の関数への唯一の変更は、関数を再帰する必要がある場合はいつでも呼び出す必要がある、たとえば という名前の関数を引数として受け入れることです。次に、一般的なメモ化機能が適切な機能を提供します。この完全な例は、この回答にあります。

Lisp バージョンには、既存の関数のメモ化をさらに簡単にする 2 つの機能があります。

  1. 他の値と同じように関数を操作できます
  2. 実行時に関数を再定義できます

たとえば、Common Lisp では、次のように定義しますF。

(defun F (n)
  (if (<= n 1)
      n
      (+ (F (- n 1))
         (F (- n 2)))))

次に、関数をメモ化する必要があることがわかったので、ライブラリをロードします。

(ql:quickload :memoize)

...そしてあなたはメモしますF：

(org.tfeb.hax.memoize:memoize-function 'F)

この機能は、どの入力をキャッシュし、どのテスト関数を使用するかを指定する引数を受け入れます。次に、関数Fは新しい関数に置き換えられ、内部ハッシュ テーブルを使用するために必要なコードが導入されます。F内部への再帰呼び出しFは、元の関数ではなく、ラッピング関数を呼び出すようになりました (再コンパイルさえしませんF)。唯一の潜在的な問題は、オリジナルFがテールコール最適化の対象であった場合です。おそらくそれを宣言するnotinlineか、使用する必要がありますDEF-MEMOIZED-FUNCTION。

于 2016-09-07T08:21:34.340 に答える
1

広く使用されている Lispで自動メモ化がサポートされているかどうかは定かではありませんが、メモ化が関数型言語でより一般的である理由が 2 つあり、Lisp ファミリーの言語ではもう 1 つの理由があると思います。

まず第一に、人々は関数型言語で関数を書きます。つまり、結果が引数のみに依存し、環境に悪影響を与えない計算です。その要件を満たさないものは、メモ化の対象にはなりません。そして、まあ、命令型言語は、これらの要件が満たされていない、または満たされていない可能性がある言語にすぎません。

もちろん、(ほとんどの) Lisp のような単に関数型に適した言語であっても、注意が必要です。たとえば、次のようなものはメモ化しないでください。

(defvar *p* 1)

(defun foo (n)
  (if (<= n 0)
      *p*
    (+ (foo (1- n)) (foo (- n *p*)))))

第二に、関数型言語は一般的に不変のデータ構造について話したいということです。これは、次の 2 つのことを意味します。

  1. 大きなデータ構造を返す関数をメモ化することは実際には安全です
  2. 非常に大きなデータ構造を構築する関数は、中間構造を変更できないため、膨大な量のガベージを作成する必要があることがよくあります。

(2) は少し物議を醸しています: 受け入れられた知恵は、GC は今では問題にならないほど優れている、コピーは非常に安価である、コンパイラーは魔法を行うことができる、などです。まあ、そのような関数を書いたことがある人は、これが部分的にしか真実ではないことを知っているでしょう: GCは優れており、コピーは安価です (しかし、それらをコピーするためにポインターを追跡する大きな構造は、しばしばキャッシュに対して非常に敵対的です)。彼らが行うと主張されている魔法を行うことはほとんどありません）。したがって、機能しないコードにむやみに頼ってごまかすか、メモを取るかのどちらかです。関数をメモ化すると、すべての中間構造を一度だけ構築するだけで、すべてが安価になります (メモリ以外では、メモ化の適切な弱点はそれを処理できます)。

第三に、言語が簡単なメタ言語的抽象化をサポートしていない場合、メモ化を実装するのは非常に困難です。別の言い方をすれば、Lisp スタイルのマクロが必要です。

関数をメモ化するには、少なくとも 2 つのことを行う必要があります。

  1. メモ化のキーとなる引数を制御する必要があります。すべての関数が引数を 1 つだけ持つわけではなく、複数の引数を持つすべての関数を最初にメモ化する必要があるわけではありません。
  2. 自己末尾呼び出しの最適化を無効にするには、関数内に介入する必要があります。これにより、メモ化が完全に破壊されます。

簡単すぎてちょっと残酷ですが、Python をからかうことでこれを実証します。

デコレーターは、Python で関数をメモ化するために必要なものだと思うかもしれません。実際、デコレーターを使用してメモ化ツールを作成することもできます (私はそれらのツールをたくさん作成しました)。そして、これらはほとんど偶然に行われますが、ある種の仕事ですらあります。

まず、デコレーターは、デコレートしている関数について簡単に知ることができません。したがって、関数へのすべての引数のタプルに基づいてメモ化しようとするか、メモ化する引数をデコレータで指定する必要があるか、または同様に厄介なものになります。

第 2 に、デコレータは、デコレートしている関数を引数として取得します。関数内をいじることはできません。もちろん、Pythonは「1956年以降に発明された概念はありません」というポリシーの一部として、fの定義内の（そして介在するバインディングなしの）レキシカルfへの呼び出しが実際には自己呼び出しであると想定していないため、それは実際には問題ありません。しかし、おそらくいつの日かそれが起こり、すべてのメモ化が壊れるでしょう。

要約すると、関数を確実にメモ化するには、Lisp スタイルのマクロが必要です。おそらく、それらを持つ命令型言語は Lisp だけです。

于 2016-09-07T11:36:37.793 に答える