1

最近いくつかのコードを最適化する際に、メモ化の「タイプ」と思われるものを実行することになりましたが、それをそう呼ぶべきかどうかはわかりません。以下の疑似コードは実際のアルゴリズムではありません (アプリケーションで階乗をほとんど必要とせず、そのコードを投稿することは違反であるため)、私の質問を説明するには十分なはずです。これはオリジナルでした：

def factorial (n):
    if n == 1 return 1
    return n * factorial (n-1)

十分に単純ですが、次のように、より大きな数に対して多数の計算を回避できるように、固定小数点を追加しました。

def factorial (n):
    if n == 1 return 1
    if n == 10 return 3628800
    if n == 20 return 2432902008176640000
    if n == 30 return 265252859812191058636308480000000
    if n == 40 return 815915283247897734345611269596115894272000000000
    # And so on.

    return n * factorial (n-1)

もちろん、これは が効率の悪い ではなく12!として計算されたことを意味します。12 * 11 * 362880012 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

しかし、これをメモ化と呼ぶべきかどうかは疑問です。これは、過去の計算結果を記憶して使用することと定義されているようです。これは、ハードコーディングされた計算 (覚えていない) とその情報を使用することに関するものです。

このプロセスに適切な名前はありますか? それとも、メモ化は、実行時に行われる計算だけでなく、コンパイル時に行われる計算にも、コードを書き始める前に頭の中で行われる計算にも及ぶと主張できますか?

4

4 に答える 4

4

メモ化ではなく、事前計算と呼んでいます。特定の入力に対する最終的な答えを計算するプロセスで行った計算を実際に覚えているわけではなく、特定の入力に対する固定数の答えを事前に計算しています。私が理解しているメモ化は、後で再利用するために結果を計算するときに、一連の結果を「キャッシュ」することに似ています。後で再計算する必要がないように、計算された各値を保存する場合、それはメモ化になります。あなたのソリューションは、プログラムから「計算された」結果を保存せず、事前に計算された固定点のみを保存するという点で異なります。メモ化を使用すると、事前に計算されたものとは異なる入力で関数を再実行しても、結果を再計算する必要はありません。

于 2011-03-22T03:09:31.520 に答える
1

結果をハードコーディングしているかどうかに関係なく、再度計算することを期待している結果をすでに計算しているため、これはメモ化です。これは、ランタイムまたはコンパイル時の形で提供される可能性がありますが、いずれにしても、メモ化です。

于 2011-03-22T03:04:34.980 に答える
1

メモ化は実行時に行われます。コンパイル時に最適化しています。ですから、そうではありません。

たとえば...ウィキペディアを参照してください

または ...

  1. メモ化メモ化という用語は、以前の計算の結果を自動的に 記憶する関数を作成するプロセスを指すために、Donald Michie（1968）によって造られました 。このアイデアは、関数型言語の台頭とともに近年人気が高まっています。Field and Harrison（1988）は、その章全体をそれに捧げています。基本的な考え方は、以前に計算された入力/結果のペアのテーブルを保持することです。

カリフォルニア大学ピーターノーヴィグ 校（太字は私のものです）

リンク

于 2011-03-22T03:06:09.120 に答える