7

次のプログラムを考えてみましょう。1 つは差分リストを使用し、もう 1 つはそうではありません。

reverse1(List1,R) :- rev1(List1, R-[]).
rev1([], A-A).
rev1([H|T], C-A) :-rev1(T, C - [H|A]).

reverse2(List1,R) :- rev2(List1, R, []).
rev2([], A, A).
rev2([H|T], C, A) :- rev2(T, C, [H|A]).

どちらも同じことをするので、相違点リストを使用する利点は何ですか?

4

3 に答える 3

11

与えられた例では、reverse1は真の差分リストを使用していませんが、 の異なる表現ですreverse2。どちらも同じ変数を同じ方法で使用します。reverseファンクターを使用して-それらをアタッチし、reverse2それらを個別のパラメーターとして維持します。しかし、両者の違いはそれだけです。アルゴリズムの動作は同じです。

実際の違いリストは、インスタンス化されず (おそらく後の時点まで) のようX-Tに、その中に「穴」があるリスト構造であり、含まれています(たとえば、)。このファンクターは、「公開された」インスタンス化されていない変数を、それを含む構造体に関連付けます。TXT[a,b,c|T]-T-

人気のある簡単な例は、append差分リストを使用した実装です。の従来の再帰的な実装は次のappendようになります。

append([], Ys, Ys).
append([X|Xs], Ys, [X|Zs]) :- append(Xs, Ys, Zs).

十分に単純で、実行時間は最初のリストの長さに比例します。

append差分リストを使用すると、次のように を実装できます。

append(A-B, B-C, A-C).

差分リストを使用してリストを追加するために必要なのはこれだけです。再帰などはありません。実行時間はO(1)、リストの長さとは無関係です。実行例を次に示します。

append([1,2,3|T]-T, [4,5,6|W]-W, DL).

収量:

DL = [1,2,3,4,5,6|W]-W
T = [4,5,6|W]

最後のパラメーターの空のリストで穴を「埋める」ことで、具体的な答えにたどり着くことができます。

append([1,2,3|T]-T, [4,5,6|W]-W, L-[]).

あなたは得る：

L = [1,2,3,4,5,6]
T = [4,5,6]
W = []
于 2014-01-18T04:09:59.487 に答える
4

あなたの例にあるものは、違いのリストではありません。http://en.wikibooks.org/wiki/Prolog/Difference_Listsを比較してください。差分リストは、テールを既知の変数として保持し、直接変更できるというトリックを使用します。したがって、一定時間リストに追加できます。しかし、それはあなたがあなたの例でやっていることではありません。

あなたの例を見ると、rev1実際に-はコンマのように区切り記号として使用されています。その場合の唯一の違いは、rev2では、プロローグ インタープリターがパフォーマンスを向上させる方法でルールにインデックスを付ける機会があることだと思います。ただし、この場合に違いがあるかどうかはわかりません。審美的に言えば、2 番目の解決策も私にはずっときれいに思えます。

于 2014-01-18T05:24:00.963 に答える
3

「コンテキスト外」で使用されている差分リストは見たことがありません。主なコンテキストは DCG の実装です。

これは DCG ベースのリバースです (まあ、私は自分で書きましたが、Christian がリンクしているページにもあります)。

reverse3(L,R) :- phrase(rev3(L),R).
rev3([]) --> [].
rev3([H|T]) --> rev3(T),[H].

それをリストすると、reverse2 がほぼ同じであることがわかります。

?- listing(rev3).
stackoverflow:rev3([], A, A).
stackoverflow:rev3([D|A], B, E) :-
    rev3(A, B, C),
    C=[D|E].

これらの定義はすべて問題を共有しています: 最初の解の後のバックトラックで、「backward」モードで使用するとループします:

?- reverse1(R,[a,b,c]).
R = [c, b, a] ; (^C here)
Action (h for help) ? abort
% Execution Aborted

次に、適切で効率的なライブラリの実装を見てみましょう。

?- listing(reverse).
lists:reverse(A, B) :-
    reverse(A, [], B, B).

lists:reverse([], A, A, []).
lists:reverse([B|A], C, D, [_|E]) :-
    reverse(A, [B|C], D, E).

ここには違いのリストはありません!

次に、あなたの質問についてですが、差分リストの唯一の利点は、Prolog をよりよく理解できることだと思います...

于 2014-01-18T17:51:14.927 に答える