子ノードを記憶することで再帰を高速化する方法はありますか?
https://stackoverflow.com/questions/23962
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
たとえば、N-Th Fibonacci番号を計算するコードを見てください。
fib(int n)
{
if(n==0 || n==1)
return 1;
return fib(n-1) + fib(n-2);
}
このコードの問題は、(ほとんどのコンピュータで) 15 を超える数値に対してスタック オーバーフロー エラーが生成されることです。
fib(10) を計算していると仮定します。このプロセスでは、たとえば fib(5) が何度も計算されます。これをメモリに保存して高速に取得し、再帰の速度を上げる方法はありますか?
ほぼすべての問題に使用できる一般的なテクニックを探しています。
解決
はい、あなたの洞察は正しいです。これはと呼ばれます 動的プログラミング. 。これは通常、一般的なメモリ ランタイムのトレードオフです。
fibo の場合、すべてをキャッシュする必要さえありません。
編集]質問の著者は、フィボナッチを計算する方法ではなく、キャッシュする一般的な方法を探しているようです。この答えを得るには、ウィキペディアを検索するか、他の投稿者のコードを参照してください。これらの答えは時間と記憶において直線的です。
**これは線形時間アルゴリズム O(n)、メモリ内の定数です **
in OCaml:
let rec fibo n =
let rec aux = fun
| 0 -> (1,1)
| n -> let (cur, prec) = aux (n-1) in (cur+prec, cur)
let (cur,prec) = aux n in prec;;
in C++:
int fibo(int n) {
if (n == 0 ) return 1;
if (n == 1 ) return 1;
int p = fibo(0);
int c = fibo(1);
int buff = 0;
for (int i=1; i < n; ++i) {
buff = c;
c = p+c;
p = buff;
};
return c;
};
これは線形時間で実行されます。しかし、ログは実際には可能です!!!Roo のプログラムも線形ですが、速度がかなり遅く、メモリを消費します。
これは対数アルゴリズム O(log(n)) です。
次に、ログ時間アルゴリズム (非常に高速) については、次のメソッドを使用します。u(n)、u(n-1) がわかっている場合は、行列を適用することで u(n+1)、u(n) を計算できます。
| u(n+1) | = | 1 1 | | u(n) |
| u(n) | | 1 0 | | u(n-1) |
したがって、次のようになります。
| u(n) | = | 1 1 |^(n-1) | u(1) | = | 1 1 |^(n-1) | 1 |
| u(n-1) | | 1 0 | | u(0) | | 1 0 | | 1 |
行列の指数の計算には対数的な複雑さがあります。アイデアを再帰的に実装するだけです。
M^(0) = Id
M^(2p+1) = (M^2p) * M
M^(2p) = (M^p) * (M^p) // of course don't compute M^p twice here.
また、単純に対角化することもできます (それほど難しくありません)。金数とその固有値の共役がわかり、その結果から u(n) の正確な数式が得られます。これにはそれらの固有値のべき乗が含まれているため、複雑さは依然として対数になります。
Fibo は動的プログラミングを説明するための例としてよく取り上げられますが、ご覧のとおり、実際には適切ではありません。
@ジョン:ハッシュとは関係ないと思います。
@ジョン2:地図は少し一般的だと思いませんか？フィボナッチの場合、すべてのキーが連続しているため、ベクトルが適切です。もう一度、フィボナッチ数列を計算するはるかに高速な方法があります。そこにある私のコードサンプルを参照してください。
他のヒント
これはメモ化と呼ばれます。メモ化に関する非常に優れた記事があります。 マシュー・ポドウィソッキ 最近投稿しました。それを例示するためにフィボナッチを使用します。C# のコードも示します。それを読んで ここ.
C# を使用していて、使用できる場合 ポストシャープ, 、コードの簡単なメモ化の側面は次のとおりです。
[Serializable]
public class MemoizeAttribute : PostSharp.Laos.OnMethodBoundaryAspect, IEqualityComparer<Object[]>
{
private Dictionary<Object[], Object> _Cache;
public MemoizeAttribute()
{
_Cache = new Dictionary<object[], object>(this);
}
public override void OnEntry(PostSharp.Laos.MethodExecutionEventArgs eventArgs)
{
Object[] arguments = eventArgs.GetReadOnlyArgumentArray();
if (_Cache.ContainsKey(arguments))
{
eventArgs.ReturnValue = _Cache[arguments];
eventArgs.FlowBehavior = FlowBehavior.Return;
}
}
public override void OnExit(MethodExecutionEventArgs eventArgs)
{
if (eventArgs.Exception != null)
return;
_Cache[eventArgs.GetReadOnlyArgumentArray()] = eventArgs.ReturnValue;
}
#region IEqualityComparer<object[]> Members
public bool Equals(object[] x, object[] y)
{
if (Object.ReferenceEquals(x, y))
return true;
if (x == null || y == null)
return false;
if (x.Length != y.Length)
return false;
for (Int32 index = 0, len = x.Length; index < len; index++)
if (Comparer.Default.Compare(x[index], y[index]) != 0)
return false;
return true;
}
public int GetHashCode(object[] obj)
{
Int32 hash = 23;
foreach (Object o in obj)
{
hash *= 37;
if (o != null)
hash += o.GetHashCode();
}
return hash;
}
#endregion
}
これを使用したフィボナッチ実装のサンプルを次に示します。
[Memoize]
private Int32 Fibonacci(Int32 n)
{
if (n <= 1)
return 1;
else
return Fibonacci(n - 2) + Fibonacci(n - 1);
}
C++ での簡単で汚いメモ化:
任意の再帰メソッド type1 foo(type2 bar) { ... } 簡単にメモ化できます map<type2, type1> M.
// your original method
int fib(int n)
{
if(n==0 || n==1)
return 1;
return fib(n-1) + fib(n-2);
}
// with memoization
map<int, int> M = map<int, int>();
int fib(int n)
{
if(n==0 || n==1)
return 1;
// only compute the value for fib(n) if we haven't before
if(M.count(n) == 0)
M[n] = fib(n-1) + fib(n-2);
return M[n];
}
編集：@コンラッド・ルドルフ
Konrad 氏は、std::map がここで使用できる最速のデータ構造ではないと指摘しています。それは本当です、 vector<something> よりも速いはずです map<int, something> (ただし、関数の再帰呼び出しへの入力がこの場合のように連続した整数でない場合は、より多くのメモリが必要になる可能性がありますが)、マップは一般に使用すると便利です。
によると ウィキペディア Fib(0) は 0 である必要がありますが、問題ありません。
for サイクルを使用した単純な C# ソリューションは次のとおりです。
ulong Fib(int n)
{
ulong fib = 1; // value of fib(i)
ulong fib1 = 1; // value of fib(i-1)
ulong fib2 = 0; // value of fib(i-2)
for (int i = 0; i < n; i++)
{
fib = fib1 + fib2;
fib2 = fib1;
fib1 = fib;
}
return fib;
}
再帰を次のように変換するのは非常に一般的なトリックです 末尾再帰 そしてループします。詳細については、たとえばこれを参照してください 講義 (ppt)。
これは何語ですか?内部では何もオーバーフローしません...また、ヒープ上にルックアップ テーブルを作成したり、マップを使用したりすることもできます。
この種のことには通常、キャッシュが良い考えです。フィボナッチ数は一定であるため、計算後に結果をキャッシュできます。簡単な c/疑似コードの例
class fibstorage {
bool has-result(int n) { return fibresults.contains(n); }
int get-result(int n) { return fibresult.find(n).value; }
void add-result(int n, int v) { fibresults.add(n,v); }
map<int, int> fibresults;
}
fib(int n ) {
if(n==0 || n==1)
return 1;
if (fibstorage.has-result(n)) {
return fibstorage.get-result(n-1);
}
return ( (fibstorage.has-result(n-1) ? fibstorage.get-result(n-1) : fib(n-1) ) +
(fibstorage.has-result(n-2) ? fibstorage.get-result(n-2) : fib(n-2) )
);
}
calcfib(n) {
v = fib(n);
fibstorage.add-result(n,v);
}
再帰ごとに 3 回の検索が発生するため、これは非常に遅くなりますが、これは一般的な考え方を示しています。
これは意図的に選ばれた例なのでしょうか？（例えば。テストしたい極端なケース)
現在はO(1.6^n)なので、単に間違って貧弱なコードを書いただけではなく、この問題の一般的なケース（値のキャッシュなど）の処理に関する答えを探しているだけであることを確認したいだけです:D
この特定のケースを見ると、次のようなことが考えられます。
var cache = [];
function fib(n) {
if (n < 2) return 1;
if (cache.length > n) return cache[n];
var result = fib(n - 2) + fib(n - 1);
cache[n] = result;
return result;
}
最悪の場合、O(n) に縮退します:D
[編集：* は + と等しくありません :D ]
[さらに別の編集:Haskell バージョン (私はマゾヒストか何かなので)
fibs = 1:1:(zipWith (+) fibs (tail fibs))
fib n = fibs !! n
]
マップを使用してみてください。n がキー、それに対応するフィボナッチ数が値です。
@ポール
情報をありがとう。それは知りませんでした。から ウィキペディアへのリンク あなたはこう言いました:
すでに計算されている値を保存するこの手法は、メモ化と呼ばれます
はい、コード (+1) はすでに見ました。:)
@ESRogs:
std::map ルックアップは ○（ログ n）これがここでの処理を遅くします。ベクトルを使用した方がよいでしょう。
vector<unsigned int> fib_cache;
fib_cache.push_back(1);
fib_cache.push_back(1);
unsigned int fib(unsigned int n) {
if (fib_cache.size() <= n)
fib_cache.push_back(fib(n - 1) + fib(n - 2));
return fib_cache[n];
}
他の人があなたの質問に適切かつ正確に答えています - あなたはメモ化を探しています。
プログラミング言語 テールコールの最適化 (ほとんどの関数型言語) は、スタック オーバーフローを発生させずに、特定のケースの再帰を実行できます。フィボナッチの定義には直接当てはまりませんが、コツはあります。
あなたの質問の表現を見て、興味深いアイデアを思いつきました。スタック フレームのサブセットのみを保存し、必要に応じて再構築することで、純粋な再帰関数のスタック オーバーフローを回避します。実際に役立つのは限られた場合のみです。アルゴリズムが戻りではなくコンテキストに条件付きでのみ依存している場合、および/または速度ではなくメモリを最適化している場合。
Mathematica には，ハッシュと関数呼び出しが同じ構文を使用するという事実に基づいて，メモ化を行うための特に巧妙な方法があります:
fib[0] = 1;
fib[1] = 1;
fib[n_] := fib[n] = fib[n-1] + fib[n-2]
それでおしまい。fib[0] と fib[1] を最初からキャッシュ (メモ化) し、必要に応じて残りをキャッシュします。パターン マッチング関数呼び出しのルールでは、常に、より一般的な定義の前に、より具体的な定義が使用されます。
再帰、部分関数、カリー化、メモ化などに関する C# プログラマ向けのもう 1 つの優れたリソースは、Wes Dyer のブログです。ただし、彼はしばらく投稿していません。彼はメモ化について詳しく説明しており、ここでは確実なコード例を示しています。http://blogs.msdn.com/wesdyer/archive/2007/01/26/function-memoization.aspx
このコードの問題は、(ほとんどのコンピュータで) 15 を超える数値に対してスタック オーバーフロー エラーが生成されることです。
本当に？どのようなコンピュータを使用していますか?44と時間がかかっていますが、スタックは溢れていません。実際、スタックがオーバーフローする前に、整数が保持できるより大きな値 (符号なしで約 40 億、符号付きで約 20 億) を取得することになります (Fibbonaci(46))。
ただし、これはあなたがやりたいことにはうまくいきます（非常に高速に実行されます）
class Program
{
public static readonly Dictionary<int,int> Items = new Dictionary<int,int>();
static void Main(string[] args)
{
Console.WriteLine(Fibbonacci(46).ToString());
Console.ReadLine();
}
public static int Fibbonacci(int number)
{
if (number == 1 || number == 0)
{
return 1;
}
var minus2 = number - 2;
var minus1 = number - 1;
if (!Items.ContainsKey(minus2))
{
Items.Add(minus2, Fibbonacci(minus2));
}
if (!Items.ContainsKey(minus1))
{
Items.Add(minus1, Fibbonacci(minus1));
}
return (Items[minus2] + Items[minus1]);
}
}
Scheme のようなファーストクラス関数を備えた言語を使用している場合は、初期アルゴリズムを変更せずにメモ化を追加できます。
(define (memoize fn)
(letrec ((get (lambda (query) '(#f)))
(set (lambda (query value)
(let ((old-get get))
(set! get (lambda (q)
(if (equal? q query)
(cons #t value)
(old-get q))))))))
(lambda args
(let ((val (get args)))
(if (car val)
(cdr val)
(let ((ret (apply fn args)))
(set args ret)
ret))))))
(define fib (memoize (lambda (x)
(if (< x 2) x
(+ (fib (- x 1)) (fib (- x 2)))))))
最初のブロックはメモ化機能を提供し、2 番目のブロックはその機能を使用したフィボナッチ数列です。これでは、ランタイムが O(n) になりました (メモ化なしのアルゴリズムの場合は O(2^n) でした)。
注記：提供されるメモ化機能は、一連のクロージャーを使用して以前の呼び出しを検索します。最悪の場合、これは O(n) になる可能性があります。ただし、この場合、必要な値は常にチェーンの先頭にあり、O(1) ルックアップが保証されます。
他の投稿者も指摘しているように、 メモ化 これはメモリを速度と引き換えにする標準的な方法です。ここでは、任意の関数のメモ化を実装するための疑似コードをいくつか示します (関数に副作用がない場合)。
初期機能コード:
function (parameters)
body (with recursive calls to calculate result)
return result
これを次のように変換する必要があります
function (parameters)
key = serialized parameters to string
if (cache[key] does not exist) {
body (with recursive calls to calculate result)
cache[key] = result
}
return cache[key]
ちなみにPerlには メモ化する 指定したコード内の任意の関数に対してこれを実行するモジュール。
# Compute Fibonacci numbers
sub fib {
my $n = shift;
return $n if $n < 2;
fib($n-1) + fib($n-2);
}
この関数をメモ化するには、次のようにプログラムを開始するだけです。
use Memoize;
memoize('fib');
# Rest of the fib function just like the original version.
# Now fib is automagically much faster ;-)
@ラセブク:
これは素晴らしいです。まさに私がメモ化について読んだ後に頭の中で考えていたことです。 高次 Perl. 。追加すると便利だと思われる点が 2 つあります。
- キャッシュへのキーを生成するために使用される静的メソッドまたはメンバー メソッドを指定するオプションのパラメーター。
- ディスクまたはデータベースにバックアップされたキャッシュを使用できるようにキャッシュ オブジェクトを変更するオプションの方法。
属性でこの種のことを行う方法 (またはこの種の実装で可能かどうか) はわかりませんが、試して理解するつもりです。
（オフトピック：これをコメントとして投稿しようとしましたが、コメントの長さがこれほど短いため、これは「回答」としては適切ではないとは思いませんでした）
