11

私はいくつかのプログラムで遊んでいてpermutation、この小さな実験に出くわしました:

順列方法 1:

permute([], []).
permute([X|Rest], L) :-
    permute(Rest, L1),
    select(X, L, L1).

順列方法 2:

permute([], []).
permute(L, [P | P1]) :-
    select(P, L, L1),
    permute(L1, P1).

順列方法 3 (組み込みを使用):

permute(L, P) :- permutation(L, P).

末尾再帰を使用することは良い習慣であり、一般に組み込み関数を使用することは効率的であると考えられていることを理解しています。しかし、次を実行すると：

time(findall(P, permute([1,2,3,4,5,6,7,8,9], P), L)).

次の結果が得られました。これは、いくつかの実行で比較的一貫しています。

方法 1:

% 772,064 inferences, 1.112 CPU in 2.378 seconds (47% CPU, 694451 Lips)

方法 2:

% 3,322,118 inferences, 2.126 CPU in 4.660 seconds (46% CPU, 1562923 Lips)

方法 3:

% 2,959,245 inferences, 1.967 CPU in 4.217 seconds (47% CPU, 1504539 Lips)

したがって、非末尾再帰法は、リアルタイム効率が大幅に向上します。

特定の再帰型は、他のすべての条件が等しい場合、一般的にリアルタイムでより効率的ですか (それは必ずしも単純な前提ではないことはわかっています)。この実験が私に教えてくれるのは、常に末尾再帰を求めているわけではなく、最初にパフォーマンス分析を行う必要があるかもしれないということです。次に、末尾再帰が持つ他の利点とパフォーマンスの利点を比較検討してください。

4

4 に答える 4

4

本当にいい質問です。

誰かが時間/空間分析を投稿するのを待っています。私が提供できる唯一の警告は、最初の引数が空いているときに方法 1 と 2 が終了しないことですが、方法 3 は終了します。

とにかく、方法 1 はビルトインよりもはるかに効率的です。知っておくと良い。

編集: ライブラリの実装は単に引数のインスタンス化を調整し、メソッド 1 を呼び出すだけであるため、SWI-Prolog メーリング リストでメソッド 2 を別の方法として議論します (または、自分でやりたい場合はお知らせください)。

詳細編集: permutation/3 (たとえば、方法 2) は辞書順に並べられたソリューションを提供するが、方法 1 は提供しないことを指摘するのを以前に忘れていました。これは強力な優先要件になる可能性があると思いますが、方法 1 でパフォーマンスが向上することを考えると、オプションとして表現する必要があります。

?- time(call_nth(permute1([0,1,2,3,4,5,6,7,8,9],P),1000000)).
% 3,112,758 inferences, 3,160 CPU in 3,162 seconds (100% CPU, 984974 Lips)
P = [1, 4, 8, 3, 7, 6, 5, 9, 2|...] .

?- time(call_nth(permute2([0,1,2,3,4,5,6,7,8,9],P),1000000)).
% 10,154,843 inferences, 9,779 CPU in 9,806 seconds (100% CPU, 1038398 Lips)
P = [2, 7, 8, 3, 9, 1, 5, 4, 6|...] .

YAPはさらに利益を上げます！

?- time(call_nth(permute1([0,1,2,3,4,5,6,7,8,9],P),1000000)).
% 0.716 CPU in 0.719 seconds ( 99% CPU)
P = [1,4,8,3,7,6,5,9,2,0]

?- time(call_nth(permute2([0,1,2,3,4,5,6,7,8,9],P),1000000)).
% 8.357 CPU in 8.368 seconds ( 99% CPU)
P = [2,7,8,3,9,1,5,4,6,0]

edit :このテーマについてSWI-Prolog doc ページにコメントを投稿しました。

于 2013-06-10T05:21:24.613 に答える
4

この調査の引き金になったのは、アキュムレータを使用する場合と使用しない場合の末尾再帰に関する議論だったsum/2と思います。このsum/2例は非常に単純です。1 つのバージョンはスタックで演算を行い、もう 1 つはアキュムレータを使用しています。ただし、現実世界のほとんどのことと同様に、一般的な真実は「場合による」ということです。たとえば、完全なインスタンス化を使用して方法 1 と 2 の効率を比較します。

?- time(permute([1,2,3,4,5,6,7,8,9], [1,2,3,4,5,6,7,8,9])).
% 18 inferences, 0.000 CPU in 0.000 seconds (66% CPU, 857143 Lips)
true ;
% 86,546 inferences, 0.022 CPU in 0.022 seconds (100% CPU, 3974193 Lips)
false.

?- time(permute([1,2,3,4,5,6,7,8,9], [1,2,3,4,5,6,7,8,9])).
% 18 inferences, 0.000 CPU in 0.000 seconds (62% CPU, 857143 Lips)
true ;
% 47 inferences, 0.000 CPU in 0.000 seconds (79% CPU, 940000 Lips)
false.

方法 1 は、(テストのように) ソリューションを生成している場合は方法 2 よりも優れていますが、単純にチェックしている場合は方法 2 が方法 1 よりも優れています。コードを見ればその理由は簡単にわかります。最初のコードはリストの最後尾全体を並べ替える必要があるのに対し、2 番目のコードは 1 つの項目を選択するだけです。この場合、生成されたケースを指して、それがより望ましいと言うのは簡単かもしれません。その決定は、Prolog を扱うときに追跡しなければならないトレードオフの 1 つにすぎません。すべての人にとってすべてのものであり、常に優れたパフォーマンスを発揮する述語を作成することは非常に困難です。どれが「特権パス」で、どれがそうでないかを決定する必要があります。

誰かが最近、「リターン中に」リストを追加する例と、テール再帰ではない、またはテール再帰であってはならないものを取得して、統合のおかげで機能させる方法を示したことを漠然と思い出しますが、リンクがありませんハンディ。うまくいけば、前回それを取り上げた人 (でしょうか?) が現れて共有してくれることでしょう。

ところで、素晴らしい質問です。調査方法は有効です。他のインスタンス化パターンも考慮する必要があります。個人的に言えば、私は通常、パフォーマンスよりも正確性と一般性について心配するようにしています。代わりにアキュムレータを使用する方法がすぐにわかる場合はそうしますが、それ以外の場合は、より良いパフォーマンスが実際に必要になるまでそのようにはしません。末尾再帰は、パフォーマンスを改善するための 1 つの方法にすぎません。多くの場合、ひどくまたはさらに悪いものとして対処する必要がある他のことがあります。

于 2013-06-10T05:38:19.557 に答える