2

私のコードは、次の方法で、リストの2つのリストをアイテムごとにマージします。

mergeL([[a,b],[c,d]], [[1,2],[3,4]], Result). Result = [[a,b,1,2],[c,d,3,4]]

そして、これは私が使用するコードです：

mergeL([],[],[]).
mergeL(List, [], List).
mergeL([], List, List).
mergeL([X|Rest],[Y|Rest2], [XY|Res2]) :-
   mergeL(Rest, Rest2, Res2),
   append(X,Y,XY).

これは機能しているようですが、同じサイズの2つのリストで呼び出すと、3つの結果が繰り返されます。例（両方のリストに含まれる要素は1つだけです）：

?- mergeL([[a,b]],[[1,2,3]],Q).
Q = [[a, b, 1, 2, 3]] ;
Q = [[a, b, 1, 2, 3]] ;
Q = [[a, b, 1, 2, 3]].

この出力を1つのソリューションのみにするクリーンな方法はありますか？

4

4 に答える 4

3

すでに3つのSO回答がありますが、1つに同意することはできません。それらはすべて正しくありません。

冗長なソリューションを排除する方法

あなたの定義の3つの事実を考慮してください：

mergeL（[]、[]、[]）。
mergeL（List、[]、List）。
mergeL（[]、List、List）。

それらはすべて成功し、mergeL([],[],[])それがあなたの冗長性の源です。2番目と3番目の事実はList、空でないリストであるためにここにあります。それでは、これを定義に追加しましょう。

mergeL（[]、[]、[]）。
mergeL（List、[]、List）：-List = [_|_]。
mergeL（[]、List、List）：-List = [_|_]。

これにより、冗長なソリューションが排除されます。冗長なソリューションを削除するためにカットする必要はありません。ただし、他のSO-answerで導入されたカットは、解決策を隠す可能性があります。クエリのmergeL(Xs,YS,Zs)場合、カットバージョンの解決策は1つだけですが、無限に多くなるはずです。

残りの選択ポイントを排除する方法

それでも、カットを使用することにはいくつかのポイントがあります。カットを使用すると、1つの選択ポイントを削除できます。しかし、そのようなカットは次のように適切に保護する必要があります。

mergeL（Xs、Ys、Zs）：-
   （Xs == []、Ys == []->！
   ; Zs == []->！
   ; true
   ）、
   Xs = []、Ys = []、Zs=[]。
..。

これが努力する価値があるかどうかはわかりません...実装はこれをより効率的に提供するかもしれません。これに関する詳細については、これとこれを参照 してください。

尾の再帰性

あなたにとってはるかに興味深いのは、おそらく最後のルールの変更です。それはむしろ読むべきです：

mergeL（[X | Rest]、[Y | Rest2]、[XY | Res2]）：-
   append（X、Y、XY）、
   mergeL（Rest、Rest2、Res2）。

これにより、ローカルスタックスペースの一時的な割り当てが回避されます。したがって、これは間違いなく最適化です。ただし、述語の論理的な読み取りに悪影響を及ぼさない最適化。

私の2009年の32ビットラップトップ（ほとんど蒸気駆動）とSWI 6.3.3-40-g064f37b：

元のバージョン：

？-Nは2 ^ 20、length（L、N）、maplist（=（[]）、L）、time（mergeL（L、L、J））です。
％2,097,206推論、5.250秒で5.232 CPU（100％CPU、400851リップ）

末尾再帰バージョン：

？-Nは2 ^ 20、length（L、N）、maplist（=（[]）、L）、time（mergeL（L、L、J））です。
％2,097,152推論、0.526秒で0.525 CPU（100％CPU、3997337リップ）

Th-それは10の因数です。

そして今、より長いリストで：末尾再帰バージョン：

？-Nは2 ^ 22、length（L、N）、maplist（=（[]）、L）、time（mergeL（L、L、J））です。
％8,388,608推論、4.237秒で4.228 CPU（100％CPU、1984272リップ）

元の注文との比較：

？-Nは2 ^ 22、length（L、N）、maplist（=（[]）、L）、time（mergeL（L、L、J））です。
％1,765,930推論、1.033秒で1.029 CPU（100％CPU、1716119リップ）
エラー：ローカルスタックが不足しています

したがって、ローカルスタックを埋めるために実行されたのは1.7Miのみでした。これは主にスペースの問題です。私よりも多くのメモリがある場合は、単に増やしてN is 2^22ください！

于 2012-11-15T10:31:51.057 に答える
1

カットを追加できます：

mergeL([],[],[]) :- !.
mergeL(List, [], List):- !.
mergeL([], List, List):- !.
mergeL([X|Rest],[Y|Rest2], [XY|Res2]) :-
   mergeL(Rest, Rest2, Res2),
   append(X,Y,XY).
于 2012-11-15T08:42:57.947 に答える
1

最初のリストが空のクエリ、つまり？-merge（[] 、、）は、最初と3番目の句に一致します。同様に、2番目のリストが空のクエリは、1番目と2番目の句に一致します。そのため、選択肢が得られ、ソリューションが重複します。

最初の句の本文にカットを配置すると、問題がないはずです。

merge([],[],[]) :- !.
于 2012-11-15T08:43:20.690 に答える
1

私は最後の選択をコミットします：

mergeL([X|Rest],[Y|Rest2], [XY|Res2]) :-
    mergeL(Rest, Rest2, Res2), !, append(X,Y,XY).

@twintererの回答も機能します！

于 2012-11-15T08:43:48.647 に答える