https://stackoverflow.com/questions/72209
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
両方が同じ目的を果たすことができるアルゴリズムで、再帰の代わりにループを使用した場合、またはその逆の場合、パフォーマンスに影響はありますか?例えば：指定された文字列が回文であるかどうかを確認します。私は、単純な反復アルゴリズムが要件に適合することを誇示するための手段として再帰を使用している多くのプログラマーを見てきました。コンパイラは何を使用するかを決定する上で重要な役割を果たしますか?
解決
他のヒント
ループによってプログラムのパフォーマンスが向上する場合があります。再帰により、プログラマのパフォーマンスが向上する可能性があります。あなたの状況でどちらがより重要かを選択してください。
再帰と反復を比較することは、プラス ドライバーとマイナス ドライバーを比較するようなものです。ほとんどの場合、あなたは できた 皿頭のプラスネジを外しますが、そのネジ用に設計されたドライバーを使用すると簡単ですよね?
一部のアルゴリズムは、その設計方法により再帰に適しています (フィボナッチ数列、ツリー状構造のトラバースなど)。再帰により、アルゴリズムがより簡潔になり、理解しやすくなります (したがって、共有および再利用可能)。
また、一部の再帰的アルゴリズムは「遅延評価」を使用するため、他の反復アルゴリズムよりも効率的になります。これは、ループが実行されるたびではなく、必要なときにのみ高価な計算を実行することを意味します。
始めるにはこれで十分です。いくつかの記事と例も紹介します。
リンク1: Haskel 対 PHP (再帰対反復)
以下は、プログラマーが PHP を使用して大規模なデータ セットを処理する必要がある例です。彼は、再帰を使用して Haskel で処理するのがいかに簡単だったかを示していますが、PHP には同じ方法を簡単に実現する方法がなかったため、結果を得るために反復を使用せざるを得ませんでした。
http://blog.webspecies.co.uk/2011-05-31/lazy-evaluation-with-php.html
リンク2: 再帰をマスターする
再帰の悪い評判のほとんどは、命令型言語のコストの高さと非効率性に起因しています。この記事の著者は、再帰アルゴリズムを最適化してより高速かつ効率的にする方法について説明します。また、従来のループを再帰関数に変換する方法と、末尾再帰を使用する利点についても説明します。彼の最後の言葉は、私が思う重要なポイントのいくつかを本当に要約しています。
「再帰プログラミングにより、プログラマーは、保守可能で論理的に一貫性のある方法でコードを整理するより良い方法を提供します。」
リンク3: 再帰がループより速いことはあるのでしょうか?（答え）
ここに、あなたと似たスタックオーバーフローの質問に対する回答へのリンクがあります。著者は、再帰またはループに関連するベンチマークの多くは次のようなものであると指摘しています。 とても 言語固有。通常、命令型言語はループを使用すると高速になり、再帰を使用すると低速になり、関数型言語ではその逆になります。このリンクから理解すべき主なポイントは、言語に依存せず、状況に盲目的な感覚で質問に答えるのは非常に難しいということだと思います。
再帰呼び出しは通常、各再帰呼び出しでメモリ アドレスをスタックにプッシュする必要があるため、メモリのコストが高くなります。これにより、後でプログラムがそのポイントに戻ることができます。
それでも、ツリーを操作する場合など、再帰の方がループよりもはるかに自然で読みやすい場合も多くあります。このような場合には、再帰に固執することをお勧めします。
通常、パフォーマンス上のペナルティは別の方向にあると予想されます。再帰呼び出しにより、余分なスタック フレームが構築される可能性があります。これに対するペナルティは異なります。また、Python などの一部の言語 (正確には、一部の言語の一部の実装では...) では、ツリー データ構造の最大値を見つけるなど、再帰的に指定する可能性のあるタスクでスタック制限に簡単に遭遇する可能性があります。このような場合、ループを使い続ける必要があります。
末尾再帰などを最適化するコンパイラーがあると仮定すると、適切な再帰関数を作成すると、パフォーマンスの低下をある程度軽減できます。(また、関数が本当に末尾再帰的であることを再確認してください。これは、多くの人が間違いやすい点の 1 つです。)
「エッジ」ケース (高性能コンピューティング、非常に大きな再帰深さなど) は別として、意図を最も明確に表現し、適切に設計され、保守しやすいアプローチを採用することが望ましいです。ニーズを特定した後にのみ最適化を行ってください。
問題を次のように分割できる場合は、反復よりも再帰の方が優れています。 複数, 、小さな断片。
たとえば、再帰的フィボナッチ アルゴリズムを作成するには、fib(n) を fib(n-1) と fib(n-2) に分割し、両方の部分を計算します。反復では、単一の関数を何度も繰り返すことのみが可能です。
ただし、フィボナッチは実際には壊れた例であり、実際には反復の方が効率的だと思います。fib(n) = fib(n-1) + fib(n-2) および fib(n-1) = fib(n-2) + fib(n-3) であることに注意してください。fib(n-1) は 2 回計算されます。
より良い例は、ツリーの再帰アルゴリズムです。親ノードの分析の問題は次のように分類できます。 複数 各子ノードを分析するという小さな問題。フィボナッチの例とは異なり、小さな問題は互いに独立しています。
そうです。複数の、より小さく、独立した、類似した問題に分解できる問題には、反復よりも再帰の方が優れています。
再帰を使用すると、どの言語でもメソッドの呼び出しには多くの準備が必要となるため、パフォーマンスが低下します。呼び出し元のコードは、リターン アドレス、呼び出しパラメーター、プロセッサ レジスタなどの他のコンテキスト情報をポストし、どこかに保存される可能性があります。また、戻り時に、呼び出されたメソッドが戻り値をポストし、呼び出し元によって取得されます。また、以前に取得されたコンテキスト情報もすべてポストされます。保存されたものが復元されます。反復アプローチと再帰的アプローチのパフォーマンスの違いは、これらの操作にかかる時間にあります。
実装の観点から見ると、呼び出しコンテキストの処理にかかる時間が、メソッドの実行にかかる時間と同程度になると、その違いに気づき始めます。再帰的メソッドの実行に呼び出しコンテキスト管理部分よりも時間がかかる場合は、一般にコードが読みやすく理解しやすく、パフォーマンスの低下に気付かないため、再帰的方法を選択してください。それ以外の場合は、効率性の理由から反復処理を行ってください。
Java の末尾再帰は現在最適化されていないと思います。ディテールが随所に散りばめられている これ LtU と関連リンクに関するディスカッション。それ 5月 次期バージョン 7 の機能となる予定ですが、スタック検査と組み合わせると特定のフレームが失われるため、明らかに問題が発生します。Stack Inspection は、Java 2 以降、きめ細かいセキュリティ モデルを実装するために使用されてきました。
反復法よりもはるかに洗練されたソリューションが得られるケースが多くあります。一般的な例としてはバイナリ ツリーのトラバースが挙げられるため、保守が必ずしも難しいわけではありません。一般に、反復バージョンの方が少し高速ですが (最適化中に再帰バージョンを置き換えることもできます)、再帰バージョンの方が理解しやすく、正しく実装するのが簡単です。
再帰は状況によっては非常に便利です。たとえば、階乗を求めるコードを考えてみましょう。
int factorial ( int input )
{
int x, fact = 1;
for ( x = input; x > 1; x--)
fact *= x;
return fact;
}
再帰関数を使って考えてみましょう
int factorial ( int input )
{
if (input == 0)
{
return 1;
}
return input * factorial(input - 1);
}
これら 2 つを観察すると、再帰が理解しやすいことがわかります。しかし、注意して使用しないと、エラーが発生しやすくなります。もし逃したとしたら if (input == 0), 、その後、コードはしばらく実行され、通常はスタック オーバーフローで終了します。
多くの場合、キャッシュにより再帰が高速になり、パフォーマンスが向上します。たとえば、従来のマージ ルーチンを使用したマージ ソートの反復バージョンを次に示します。キャッシュのパフォーマンスが向上するため、再帰的実装よりも実行速度が遅くなります。
反復実装
public static void sort(Comparable[] a)
{
int N = a.length;
aux = new Comparable[N];
for (int sz = 1; sz < N; sz = sz+sz)
for (int lo = 0; lo < N-sz; lo += sz+sz)
merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}
再帰的な実装
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid+1, hi);
merge(a, aux, lo, mid, hi);
}
PS - これは、Coursera で提供されたアルゴリズムに関するコースで Kevin Wayne 教授 (プリンストン大学) が語った内容です。
再帰を使用すると、「反復」ごとに関数呼び出しのコストが発生しますが、ループの場合、通常支払うのは増加/減少だけです。したがって、ループのコードが再帰的ソリューションのコードよりもそれほど複雑でない場合は、通常、ループの方が再帰よりも優れています。
再帰と反復は、実装するビジネス ロジックによって異なりますが、ほとんどの場合、同じ意味で使用できます。ほとんどの開発者は再帰が理解しやすいため、再帰を使用します。
それは言語によって異なります。Java ではループを使用する必要があります。関数型言語は再帰を最適化します。
リストを反復処理しているだけの場合は、必ず反復処理を行ってください。
他のいくつかの回答では、(深さ優先) ツリートラバーサルについて言及しています。これは、非常に一般的なデータ構造に対して行われる非常に一般的なことであるため、非常に優れた例です。この問題に関しては、再帰は非常に直感的です。
ここで「検索」メソッドを確認してください。http://penguin.ewu.edu/cscd300/Topic/BSTintro/index.html
再帰は、考えられる反復の定義よりも単純です (したがって、より基本的です)。チューリング完全システムは、 コンビネータのペア (はい、そのようなシステムでは再帰そのものでさえ派生的な概念です)。 ラムダ calculus は、再帰関数を特徴とする同様に強力な基本システムです。しかし、反復を適切に定義したい場合は、最初にさらに多くのプリミティブが必要になります。
コードに関しては、いいえ、再帰的コードは、ほとんどのデータ構造が再帰的であるため、純粋に反復的なコードよりも理解と保守が実際にはるかに簡単です。もちろん、これを正しく行うには、少なくとも標準的なコンビネータとイテレータをきちんとした方法で取得するために、高階関数とクロージャをサポートする言語が必要です。もちろん、C++ では、熱心なユーザーでない限り、複雑な再帰的ソリューションは少し見苦しく見える可能性があります。 FC++ そして似ています。
(非末尾) 再帰では、関数が呼び出されるたびに新しいスタックなどを割り当てるため、パフォーマンスが低下すると思います (もちろん言語に依存します)。
それは「再帰の深さ」に依存します。それは、関数呼び出しのオーバーヘッドが合計実行時間にどの程度影響するかによって異なります。
たとえば、古典的な階乗を再帰的に計算することは、次の理由により非常に非効率的です。- データオーバーフローのリスク - スタックのオーバーフローのリスク - 機能通話オーバーヘッドは実行時間の80％を占めています
チェスのゲームにおける位置分析のための最小-最大アルゴリズムを開発する際、後続の N 個の手を分析するアルゴリズムは、「分析の深さ」にわたって再帰的に実装できます (私が行っているように ^_^)
再帰？どこから始めればよいでしょうか。wiki には「自己相似的な方法で項目を繰り返すプロセスです」と書かれています。
私が C をやっていた頃、C++ 再帰は「末尾再帰」のような神が送ってくれたものでした。また、多くの並べ替えアルゴリズムで再帰が使用されていることがわかります。簡単な並べ替えの例: http://alienryderflex.com/quicksort/
再帰は、特定の問題に役立つ他のアルゴリズムと同様です。おそらく、すぐには、または頻繁には使い道が見つからないかもしれませんが、利用できると嬉しい問題が発生するでしょう。
C++ では、再帰関数がテンプレート化された関数である場合、すべての型推論と関数のインスタンス化がコンパイル時に行われるため、コンパイラーはそれを最適化する可能性が高くなります。最新のコンパイラは、可能であれば関数をインライン化することもできます。したがって、次のような最適化フラグを使用すると、 -O3 または -O2 で g++, の場合、再帰は反復よりも高速になる可能性があります。反復コードでは、(十分に適切に記述されていれば) すでに多かれ少なかれ最適な状態にあるため、コンパイラーがコードを最適化する機会は少なくなります。
私の場合、再帰的および反復的な方法で、Armadillo 行列オブジェクトを使用して 2 乗による行列のべき乗を実装しようとしていました。アルゴリズムはここで見つけることができます... https://en.wikipedia.org/wiki/Exponentiation_by_squaring。私の関数はテンプレート化されており、計算しました 1,000,000 12x12 行列のべき乗 10. 。次の結果が得られました。
iterative + optimisation flag -O3 -> 2.79.. sec
recursive + optimisation flag -O3 -> 1.32.. sec
iterative + No-optimisation flag -> 2.83.. sec
recursive + No-optimisation flag -> 4.15.. sec
これらの結果は、c++11 フラグを指定した gcc-4.8 を使用して取得されました (-std=c++11) および Intel mkl を搭載した Armadillo 6.1。Intel コンパイラでも同様の結果が表示されます。
マイクは正しい。末尾再帰は ない Java コンパイラまたは JVM によって最適化されます。次のようなスタック オーバーフローが常に発生します。
int count(int i) {
return i >= 100000000 ? i : count(i+1);
}
許可されているスタック サイズによっては、再帰が深すぎるとスタック オーバーフローが発生することに注意してください。これを防ぐには、再帰を終了する基本ケースを必ず提供してください。
再帰には、再帰を使用して作成したアルゴリズムの空間複雑さが O(n) であるという欠点があります。反復アプローチの空間計算量は O(1) ですが、これは再帰よりも反復を使用する利点です。では、なぜ再帰を使用するのでしょうか?
以下を参照してください。
場合によっては、再帰を使用してアルゴリズムを作成する方が簡単ですが、反復を使用して同じアルゴリズムを作成するのは少し難しい場合があります。この場合、反復アプローチに従うことを選択した場合は、スタックを自分で処理する必要があります。
私の知る限り、Perl は末尾再帰呼び出しを最適化しませんが、それを偽装することはできます。
sub f{
my($l,$r) = @_;
if( $l >= $r ){
return $l;
} else {
# return f( $l+1, $r );
@_ = ( $l+1, $r );
goto &f;
}
}
最初に呼び出されるとき、スタック上にスペースが割り当てられます。次に、引数を変更し、スタックに何も追加せずにサブルーチンを再起動します。したがって、自分自身を呼び出さなかったふりをして、反復プロセスに変更します。
「」がないことに注意してください。my @_;" または "local @_;」と思ったら、もう機能しません。
Chrome 45.0.2454.85 m だけを使用すると、再帰がかなり高速になるようです。
コードは次のとおりです。
(function recursionVsForLoop(global) {
"use strict";
// Perf test
function perfTest() {}
perfTest.prototype.do = function(ns, fn) {
console.time(ns);
fn();
console.timeEnd(ns);
};
// Recursion method
(function recur() {
var count = 0;
global.recurFn = function recurFn(fn, cycles) {
fn();
count = count + 1;
if (count !== cycles) recurFn(fn, cycles);
};
})();
// Looped method
function loopFn(fn, cycles) {
for (var i = 0; i < cycles; i++) {
fn();
}
}
// Tests
var curTest = new perfTest(),
testsToRun = 100;
curTest.do('recursion', function() {
recurFn(function() {
console.log('a recur run.');
}, testsToRun);
});
curTest.do('loop', function() {
loopFn(function() {
console.log('a loop run.');
}, testsToRun);
});
})(window);
結果
// 標準の for ループを使用して 100 回実行します
ループ実行の場合は 100 倍。完了までの時間: 7.683ミリ秒
// 末尾再帰を使用した関数的再帰的アプローチを使用して 100 回の実行
100 回の再帰実行。完了までの時間: 4.841ミリ秒
以下のスクリーンショットでは、テストあたり 300 サイクルで実行すると、再帰がさらに大きな差で勝利します。
反復がアトミックであり、新しいスタック フレームをプッシュするよりも桁違いにコストがかかる場合 そして 新しいスレッドを作成する そして 複数のコアがあります そして ランタイム環境でそれらをすべて使用できる場合、再帰的アプローチをマルチスレッドと組み合わせると、パフォーマンスが大幅に向上する可能性があります。平均反復回数が予測できない場合は、スレッド割り当てを制御し、プロセスが大量のスレッドを作成してシステムを占有するのを防ぐスレッド プールを使用することをお勧めします。
たとえば、一部の言語には、再帰的なマルチスレッド マージ ソートの実装があります。
ただし、繰り返しますが、マルチスレッドは再帰ではなくループで使用できるため、この組み合わせがどの程度うまく機能するかは、OS とそのスレッド割り当てメカニズムを含むその他の要因に依存します。
私は、再帰に対する一種の「双対」である「帰納法」によって Haskell データ構造を設計することであなたの質問に答えます。そして、この二重性がどのように素晴らしいものを生み出すのかを説明します。
単純なツリーの型を導入します。
data Tree a = Branch (Tree a) (Tree a)
| Leaf a
deriving (Eq)
この定義は、「ツリーはブランチ (2 つのツリーを含む) またはリーフ (データ値を含む) である」と解釈できます。つまり、リーフは一種の最小限のケースです。木が葉ではない場合、それは 2 つの木を含む複合木でなければなりません。これらは唯一のケースです。
ツリーを作ってみましょう:
example :: Tree Int
example = Branch (Leaf 1)
(Branch (Leaf 2)
(Leaf 3))
ここで、ツリー内の各値に 1 を追加するとします。これは、次のように呼び出すことで実行できます。
addOne :: Tree Int -> Tree Int
addOne (Branch a b) = Branch (addOne a) (addOne b)
addOne (Leaf a) = Leaf (a + 1)
まず、これが実際には再帰的な定義であることに注意してください。データ コンストラクターの Branch と Leaf をケースとして取るので (Leaf は最小限であり、これらが可能な唯一のケースであるため)、関数は確実に終了します。
addOne を反復スタイルで記述するには何が必要でしょうか?任意の数のブランチをループするとどうなるでしょうか?
また、この種の再帰は、多くの場合、「関手」の観点から因数分解できます。以下を定義することで、ツリーをファンクターにできます。
instance Functor Tree where fmap f (Leaf a) = Leaf (f a)
fmap f (Branch a b) = Branch (fmap f a) (fmap f b)
そして以下を定義します:
addOne' = fmap (+1)
代数データ型の変成作用 (またはフォールド) など、他の再帰スキームを除外できます。変成作用を使用すると、次のように書くことができます。
addOne'' = cata go where
go (Leaf a) = Leaf (a + 1)
go (Branch a b) = Branch a b
スタック オーバーフローは、メモリ管理が組み込まれていない言語でプログラミングしている場合にのみ発生します。それ以外の場合は、関数 (または関数呼び出し、STDLb など) に何かがあることを確認してください。再帰がなければ、次のようなことは不可能です...Google や SQL、あるいは大規模なデータ構造 (クラス) やデータベースを効率的に分類する必要がある場所ならどこでも。
再帰は、ファイルを繰り返したい場合に行く方法です。それが「見つける * | ？grep *'works。特にパイプの場合は二重再帰のようなものです (ただし、他の人が使用できるように公開する場合は、多くの人が好むような大量のシステムコールを実行しないでください)。
高級言語やclang/cppでも同様にバックグラウンドで実装する場合があります。
