インターネット上には、さまざまな言語用の自動メモ化ライブラリがいくつかあります。しかし、それらが何のために使用され、どこで使用され、どのように機能するかを知らなければ、その価値を理解することは困難です。メモ化を使用するための説得力のある議論は何ですか? また、メモ化が特に優れているのはどのような問題領域ですか? 情報を知らない人のための情報は、ここで特に高く評価されます。
6093 次
12 に答える
22
私の意見では、フィボナッチと階乗の計算は実際には最良の例ではありません。メモ化は、次の場合に真価を発揮します。
- 問題の計算への膨大な範囲の潜在的な入力ですが、その範囲は依然として明らかに制限されており、既知です
- プログラムの実際の使用は、計算に可能な入力の小さなサブセットのみを使用することを事前に知っています（フィボナッチと階乗はこれに失敗します）
- 実行時にどの特定の入力が使用されるのかがわからないため、どの特定の結果をメモする必要があるのか わかりません（フィボナッチと階乗もこれに失敗します、ある程度まで）
明らかに、可能なすべての入力を知っていて、スペースが許せば、関数をルックアップに置き換えることを検討できます (これは、既知のジェネレーターを使用した埋め込み CRC32 実装の場合に行います)。
...＃2よりもさらに優れているのは、プログラムの特定の実行について、「潜在的な入力の範囲がこれらの条件を満たすサブセットに制限される...」とすぐに言うことができる場合です.
これの多くは確率的 (または直感的) である可能性があることに注意してください — 確かに、誰かがあなたの魔法の計算に 10^13 の可能なすべての入力を試すかもしれませんが、現実的にはそうではないことがわかっています。その場合、メモ化のオーバーヘッドは実際には何のメリットもありません。しかし、これが許容できると判断するか、そのような状況でメモ化をバイパスすることを許可することもできます。
ここに例を示します。情報を提供するのに複雑すぎる (または一般化されていない) ことを願っています。
私が書いたいくつかのファームウェアでは、プログラムの一部が ADC から読み取りを行います。ADC は から までの任意の数0x000で0xFFFあり、プログラムの他の部分の出力を計算します。この計算には、ユーザーが調整可能な一連の数値も使用されますが、これらはプログラムの起動時にのみ読み取られます。この計算は、初めて実行するとかなりヒットします。
事前にルックアップ テーブルを作成するのはばかげています。0x000入力ドメインは、[ , ..., 0xFFF] と (浮動小数点値の広い範囲) と (別の広い範囲...) と ...のデカルト積です。
しかし、状況が急速に変化したときにデバイスがうまく機能することを要求したり期待したりするユーザーはいません。したがって、これらの要件を反映する計算動作でトレードオフを行います。物事が安定している場合はこの計算が適切で高速であることを望み、そうでない場合は気にしません。
一般的なユーザーが期待する「ゆっくりと変化する条件」の定義を考えると、その ADC 値は特定の値に安定し、その安定した値の約 0x010 内にとどまります。どの値が条件に依存します。
したがって、計算の結果は、これらの 16 の潜在的な入力に対してメモすることができます。環境条件が予想よりも速く変化した場合、最新の ADC 読み取りから「最も遠い」ADC が破棄されます (たとえば、0x210 を 0x21F にキャッシュしてから 0x222 を読み取った場合、0x210 の結果は削除されます)。
ここでの欠点は、環境条件が大幅に変化すると、すでに遅い計算の実行が少し遅くなることです。これが異常なユースケースであることはすでに確認済みですが、後で誰かが実際に非常に不安定な条件下で操作したいと明らかにした場合は、メモ化をバイパスする方法を実装できます。
于 2010-07-14T02:28:30.863 に答える
21
ここで人気のある階乗の答えは、おもちゃの答えのようなものです。はい、メモ化はその関数の繰り返し呼び出しに役立ちますが、関係は自明です — 「print factorial(N) for 0..M」の場合、最後の値を再利用しているだけです。
ここにある他の例の多くは、単なる「キャッシング」です。これは便利ですが、メモ化という言葉が私にもたらす驚くべきアルゴリズムの意味を無視しています。
はるかに興味深いのは、再帰関数の 1 回の呼び出しのさまざまな分岐が同一のサブ問題にヒットするケースですが、実際にはいくつかのキャッシュへのインデックス作成が実際に役立つような自明でないパターンです。
たとえば、絶対値の合計が k になる整数の n 次元配列を考えてみましょう。たとえば、n=3、k=5 の場合 [1,-4,0]、[3,-1,1]、[5,0,0]、[0,5,0] がいくつかの例になります。V(n,k) を、特定の n,k に対して可能な一意の配列の数とします。その定義は次のとおりです。
V(n,0)=1; V(0,k)=0; V(n,k) = V(n-1,k) + V(n,k-1) + V(n-1,k-1);
この関数は、n=3、k=5 に対して 102 を返します。
メモ化がなければ、かなり控えめな数値であっても、すぐに計算が非常に遅くなります。処理をツリーとして視覚化すると、各ノードが V() の呼び出しで 3 つの子に展開され、186,268,135,991,213,676,920,832 V(n,0)=1 が V(32,32) の計算に残ります...この関数は、利用可能なハードウェアでは急速に計算不能になります。
しかし、階乗関数のように簡単に削除できる簡単な方法ではありませんが、ツリー内の子ブランチの多くは互いに正確に複製されています。メモ化を使用すると、重複するブランチをすべてマージできます。実際、メモ化を使用すると、V(32,32) は V() を 1024 (n*m) 回しか実行しません。これは、10^21 倍 (n,k が大きくなるにつれて明らかに大きくなります) の速度アップになります。かなり少量のメモリの場合。:) アルゴリズムの複雑さに対するこの種の根本的な変更は、単純なキャッシングよりもはるかにエキサイティングだと思います。難しい問題を簡単に解決できます。
Python の数値は当然 bignum であるため、辞書とタプル キーを使用したメモ化により、Python でこの式をわずか 9 行で実装できます。試してみて、メモ化せずに試してみてください。
于 2010-07-14T05:57:20.797 に答える
13
メモ化は、プログラムが後で同じサブ問題を再解決する必要がないように、サブ問題への回答を保存する手法です。
これは、動的計画法を使用して問題を解決する際に重要な手法であることがよくあります。
グリッドの左上隅からグリッドの右下隅までのすべてのパスを列挙することを想像してください。多くのパスが互いに重なり合っています。グリッド上の各点について計算された解をメモし、右下から左上に戻ることができます。これにより、計算時間が「ばかばかしい」ものから「扱いやすい」ものに短縮されます。
別の用途: 0 から 100 までの階乗をリストします。100 を計算する必要はありません。を使用して100 * 99 * ... * 1。はすでに計算したので、その答えを再利用して、単純に答え99!を に掛けます。これらの各ステップ (1 から 100 までの作業) で答えをメモして、計算量を大幅に節約できます。10099!
データ ポイントの場合、上記の問題を解決するグリッドの場合 (問題はプログラミングの課題によるものです):
メモ化:
real 0m3.128s
user 0m1.120s
sys 0m0.064s
メモ化されていない (待つのにうんざりしていたので、これを殺しました... これは不完全です)
real 24m6.513s
user 23m52.478s
sys 0m6.040s
于 2010-07-14T00:51:42.983 に答える
11
メモ化は、サブ問題の解決策を再利用できる問題で威力を発揮します。簡単に言えば、キャッシングの一種です。階乗関数を例に見てみましょう。
3！はそれ自体の問題ですが、n! の部分問題でもあります。ここで n > 3 など4! = 4 * 3! 階乗を計算する関数は、3 しか計算しないため、メモ化を使用するとはるかに優れたパフォーマンスを発揮できます! 一度、結果を内部のハッシュ テーブルに格納します。出会うたびに3！ここでも、値を再計算する代わりに、テーブルで値を調べます。
サブ問題の解決策を再利用できる (より頻繁に使用するほど良い) 問題は、メモ化を使用する候補です。
于 2010-07-14T00:47:53.053 に答える
7
メモ化は時間を空間と交換します。
メモ化は、本質的に多重再帰的な問題に適用されると、指数時間 (またはそれ以上) を線形時間 (またはそれ以上) に変えることができます。コストは通常 O(n) スペースです。
古典的な例は、フィボナッチ数列の計算です。教科書の定義は再帰関係です。
F(n) = F(n-1) + F(n-2)
単純に実装すると、次のようになります。
int fib(int n) {
if (n == 0) {
return 0;
}
else if (n == 1) {
return 1;
}
else {
return fib(n-1) + fib(n-2);
}
}
各部分和が複数回計算されるため、実行時間が n で指数関数的に増加することがわかります。
メモ化で実装すると、次のようになります (不器用ですが機能的です)。
int fib(int n) {
static bool initialized = false;
static std::vector<int> memo;
if (!initialized) {
memo.push_back(0);
memo.push_back(1);
initialized = true;
}
if (memo.size() > n) {
return memo[n];
}
else {
const int val = fib(n-1) + fib(n-2);
memo.push_back(val);
return val;
}
}
私のラップトップでこれら 2 つの実装のタイミングを計ると、n = 42 の場合、素朴なバージョンは 6.5 秒かかります。メモ化されたバージョンは 0.005 秒かかります (すべてのシステム時間 - つまり、I/O バウンドです)。n = 50 の場合、メモ化されたバージョンはまだ 0.005 秒かかり、ナイーブ バージョンは 5 分 7 秒後に最終的に終了しました (どちらも 32 ビット整数をオーバーフローしたことに注意してください)。
于 2010-07-14T01:23:45.943 に答える
4
メモ化の用途の 1 つは、ゲーム ツリーの分析です。重要なゲーム ツリー (チェス、囲碁、ブリッジなど) の分析では、位置の値を計算することは重要なタスクであり、かなりの時間がかかる可能性があります。素朴な実装では、単にこの結果を使用してから破棄しますが、すべての強力なプレイヤーはそれを保存して、状況が再び発生した場合に使用します。チェスでは、同じ位置に到達する方法が無数にあることが想像できます。
実際にこれを達成するには、際限のない実験と調整が必要ですが、この手法がなければ、コンピューター チェス プログラムは今日のようにはなっていなかったと言っても過言ではありません。
AI では、このようなメモ化の使用は、通常、「転置テーブル」と呼ばれます。
于 2010-07-14T03:02:16.727 に答える
4
メモ化は、アルゴリズムを根本的に高速化できます。古典的な例はフィボノッチ数列で、再帰アルゴリズムは非常に遅いですが、メモ化により自動的に反復バージョンと同じくらい高速になります。
于 2010-07-14T00:52:52.127 に答える
3
メモ化とは、基本的に、特定の入力に対する関数の戻り値をキャッシュすることです。これは、同じ入力で関数呼び出しを何度も繰り返す場合、特に関数の実行に時間がかかる場合に便利です。もちろん、データはどこかに保存する必要があるため、メモ化はより多くのメモリを使用します。これは、CPU の使用と RAM の使用の間のトレードオフです。
于 2010-07-14T00:49:45.543 に答える
2
あるシステムから別のシステム (ETL) にデータを移行するときは、常にメモ化を使用します。概念は、関数が常に同じ入力セットに対して同じ出力を返す場合、特にその結果の計算に時間がかかる場合は、結果をキャッシュすることが理にかなっているということです。ETL を実行する場合、多くの場合、大量のデータに対して同じアクションを何度も繰り返すことになり、パフォーマンスが重要になることがよくあります。パフォーマンスが問題にならないか無視できる場合、メソッドをメモすることはおそらく意味がありません。何でもそうですが、仕事に適したツールを使用してください。
于 2010-07-14T00:48:52.657 に答える
1
メモ化を使用してアルゴリズムのパフォーマンスを向上させる方法の例として、この特定のテストケースでは、以下の実行が約300倍高速になります。以前は、約200秒かかりました。2/3をメモしました。
class Slice:
__slots__ = 'prefix', 'root', 'suffix'
def __init__(self, prefix, root, suffix):
self.prefix = prefix
self.root = root
self.suffix = suffix
################################################################################
class Match:
__slots__ = 'a', 'b', 'prefix', 'suffix', 'value'
def __init__(self, a, b, prefix, suffix, value):
self.a = a
self.b = b
self.prefix = prefix
self.suffix = suffix
self.value = value
################################################################################
class Tree:
__slots__ = 'nodes', 'index', 'value'
def __init__(self, nodes, index, value):
self.nodes = nodes
self.index = index
self.value = value
################################################################################
def old_search(a, b):
# Initialize startup variables.
nodes, index = [], []
a_size, b_size = len(a), len(b)
# Begin to slice the sequences.
for size in range(min(a_size, b_size), 0, -1):
for a_addr in range(a_size - size + 1):
# Slice "a" at address and end.
a_term = a_addr + size
a_root = a[a_addr:a_term]
for b_addr in range(b_size - size + 1):
# Slice "b" at address and end.
b_term = b_addr + size
b_root = b[b_addr:b_term]
# Find out if slices are equal.
if a_root == b_root:
# Create prefix tree to search.
a_pref, b_pref = a[:a_addr], b[:b_addr]
p_tree = old_search(a_pref, b_pref)
# Create suffix tree to search.
a_suff, b_suff = a[a_term:], b[b_term:]
s_tree = old_search(a_suff, b_suff)
# Make completed slice objects.
a_slic = Slice(a_pref, a_root, a_suff)
b_slic = Slice(b_pref, b_root, b_suff)
# Finish the match calculation.
value = size + p_tree.value + s_tree.value
match = Match(a_slic, b_slic, p_tree, s_tree, value)
# Append results to tree lists.
nodes.append(match)
index.append(value)
# Return largest matches found.
if nodes:
return Tree(nodes, index, max(index))
# Give caller null tree object.
return Tree(nodes, index, 0)
################################################################################
def search(memo, a, b):
# Initialize startup variables.
nodes, index = [], []
a_size, b_size = len(a), len(b)
# Begin to slice the sequences.
for size in range(min(a_size, b_size), 0, -1):
for a_addr in range(a_size - size + 1):
# Slice "a" at address and end.
a_term = a_addr + size
a_root = a[a_addr:a_term]
for b_addr in range(b_size - size + 1):
# Slice "b" at address and end.
b_term = b_addr + size
b_root = b[b_addr:b_term]
# Find out if slices are equal.
if a_root == b_root:
# Create prefix tree to search.
key = a_pref, b_pref = a[:a_addr], b[:b_addr]
if key not in memo:
memo[key] = search(memo, a_pref, b_pref)
p_tree = memo[key]
# Create suffix tree to search.
key = a_suff, b_suff = a[a_term:], b[b_term:]
if key not in memo:
memo[key] = search(memo, a_suff, b_suff)
s_tree = memo[key]
# Make completed slice objects.
a_slic = Slice(a_pref, a_root, a_suff)
b_slic = Slice(b_pref, b_root, b_suff)
# Finish the match calculation.
value = size + p_tree.value + s_tree.value
match = Match(a_slic, b_slic, p_tree, s_tree, value)
# Append results to tree lists.
nodes.append(match)
index.append(value)
# Return largest matches found.
if nodes:
return Tree(nodes, index, max(index))
# Give caller null tree object.
return Tree(nodes, index, 0)
################################################################################
import time
a = tuple(range(50))
b = (48, 11, 5, 22, 28, 31, 14, 18, 7, 29, 49, 44, 47, 36, 25, 27,
34, 10, 38, 15, 21, 16, 35, 20, 45, 2, 37, 33, 6, 30, 0, 8, 13,
43, 32, 1, 40, 26, 24, 42, 39, 9, 12, 17, 46, 4, 23, 3, 19, 41)
start = time.clock()
old_search(a, b)
stop = time.clock()
print('old_search() =', stop - start)
start = time.clock()
search({}, a, b)
stop = time.clock()
print('search() =', stop - start)
于 2010-07-18T18:46:11.567 に答える
1
ほとんどの人がメモ化の基本をカバーしていると思いますが、メモ化を使用してかなり驚くべきことを行うことができる実用的な例をいくつか紹介します (imho):
- C# では、関数をリフレクトしてそのデリゲートを作成し、デリゲートを動的に呼び出すことができます...しかし、これは本当に遅いです! メソッドを直接呼び出すよりも約 30 倍遅くなります。メソッド呼び出しをメモ化すると、メソッドを直接呼び出すのとほぼ同じ速度で呼び出しを行うことができます。
- 遺伝的プログラミングでは、集団内の何百、何千もの標本に対して同様の入力パラメーターを使用して同じ関数を繰り返し呼び出すオーバーヘッドを削減できます。
- 式ツリーの実行: すでにメモ化されている場合は、式ツリーを再評価する必要はありません...
もちろん、メモ化を使用できる実用的な例はたくさんありますが、これらはほんの一部です。
私のブログでは、メモ化とリフレクションを別々に説明していますが、リフレクトされたメソッドでのメモ化の使用については別の記事を投稿する予定です...
于 2010-07-14T04:55:21.230 に答える
-7
メモ化は、キャッシングを意味する派手な言葉です。計算がキャッシュから情報を取得するよりもコストがかかる場合、それは良いことです。問題は、CPU が高速で、メモリが低速であることです。そのため、メモ化を使用すると、通常、計算をやり直すよりもはるかに遅いことがわかりました。
もちろん、実際に大幅な改善をもたらす他のテクニックも利用できます。ループの反復ごとに f(10) が必要であることがわかっている場合は、それを変数に格納します。キャッシュ ルックアップがないため、通常はこれで問題ありません。
編集
さあ、好きなだけ私に反対票を投じてください。それでも、やみくもにすべてをハッシュ テーブルに投げ込むだけでなく、実際のベンチマークを実行する必要があるという事実は変わりません。
コンパイル時に値の範囲がわかっている場合は、たとえば n! を使用しているためです。n が 32 ビットの int の場合は、静的配列を使用することをお勧めします。
値の範囲が大きい場合、たとえば double の場合、ハッシュ テーブルが大きくなりすぎて深刻な問題になる可能性があります。
同じ結果が特定のオブジェクトと組み合わせて何度も使用される場合、その値をオブジェクトに格納することは理にかなっている場合があります。
私の場合、特定の反復の入力が最後の反復と同じ時間の 90% 以上であることを発見しました。つまり、最後の入力と最後の結果を保持し、入力が変更された場合にのみ再計算する必要がありました。これは、そのアルゴリズムでメモ化を使用するよりも桁違いに高速でした。
于 2010-07-14T00:52:24.727 に答える