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).

这似乎可行，但如果我用两个相同大小的列表调用它，我会得到三个重复的结果。示例（两个列表都只包含一个元素）：

?- 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]].

有没有一种干净的方法可以使这个输出只有一个解决方案？

4

4 回答 4

3

已经有 3 个 SO-answers，但我不能同意一个！他们都是不正确的。

如何消除冗余解决方案

考虑您定义中的三个事实：

合并L（[]，[]，[]）。
合并（列表，[]，列表）。
合并（[]，列表，列表）。

他们都成功了，mergeL([],[],[])这就是你裁员的根源。第二个和第三个事实是List一个非空列表。因此，让我们将其添加到定义中：

合并L（[]，[]，[]）。
合并（列表，[]，列表）：- 列表 = [_|_]。
合并（[]，列表，列表）：- 列表 = [_|_]。

这消除了冗余解决方案。无需削减以删除多余的解决方案。但是，其他 SO-answer中引入的削减可能会隐藏解决方案。对于查询mergeL(Xs,YS,Zs)，剪切版本只有一种解决方案，但应该有无限多。

如何消除剩余的选择点

尽管如此，使用削减还是有一些意义的：他们能够删除一个选择点。但是这样的切割需要像这样适当地保护：

合并L（Xs，Ys，Zs）：-
   ( Xs == [], Ys == [] -> !
   ; Zs == [] -> ！
   ; 真的
   ),
   Xs = []，Ys = []，Zs = []。
...

我不确定这是否值得付出努力......实现可能会更有效地提供这一点。有关此的更多详细信息，请参见 this和this。

尾递归

对您来说更有趣的可能是最后一条规则的更改。它应该改为：

合并L（[X|Rest]，[Y|Rest2]，[XY|Res2]）：-
   附加（X，Y，XY），
   合并L（休息，休息2，休息2）。

这避免了本地堆栈空间的临时分配。所以这绝对是一个优化。但是不会损害谓词的逻辑阅读的优化。

在我的 2009 年 32 位笔记本电脑（几乎是蒸汽驱动的）和 SWI 6.3.3-40-g064f37b 上：

原始版本：

?- N 是 2^20，长度（L，N），maplist（=（[]），L），时间（mergeL（L，L，J））。
% 2,097,206 次推理，5.232 CPU 在 5.250 秒内（100% CPU，400851 唇）

尾递归版本：

?- N 是 2^20，长度（L，N），maplist（=（[]），L），时间（mergeL（L，L，J））。
% 2,097,152 推理，0.525 CPU 在 0.526 秒内（100% CPU，3997337 唇）

Th-那是 10 倍。

现在有更长的列表：尾递归版本：

?- N 是 2^22，长度（L，N），maplist（=（[]），L），时间（mergeL（L，L，J））。
% 8,388,608 推理，4.228 CPU 在 4.237 秒内（100% CPU，1984272 唇）

与原始顺序相比：

?- N 是 2^22，长度（L，N），maplist（=（[]），L），时间（mergeL（L，L，J））。
% 1,765,930 次推理，1.029 CPU 在 1.033 秒内（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([], , )，将匹配第一个和第三个子句。同样，第二个列表为空的查询将匹配第一个和第二个子句。这就是为什么您获得选择点并因此重复解决方案的原因。

如果您在第一个子句的正文中放置一个切口，您应该没问题：

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 回答