2

我需要一个查询，它将从列表中删除所有变量和重复项。

例子：

?- L = [1,2,3,X,Y,3,2], my_awesome_predicate(L, Res).

那么，Res 应该是：[1,2,3]。

我不在乎顺序（可能是 [2,3,1]、[3,2,1] 或其他）。

不幸的是，我有一项任务我必须关心效率，所以我的主要问题是 - 它可以更快地完成吗？目前，我有以下代码：

remove_variables([], []).
remove_variables([H|List], Res):- var(H), !, remove_variables(List, Res).
remove_variables([H|List], [H|Res]):- remove_variables(List, Res).

my_awesome_predicate([], []).
my_awesome_predicate(List, Res):-
  sort(List, Sorted),
  remove_variables(Sorted, Res).
4

3 回答 3

3

如果您使用的是SWI，那么您可以使用以下代码进一步改进：

my_awesome_predicate(List, Res):-
  sort(List, MRes),
  remove_variables(MRes, Res).

remove_variables([Var|Tail], NTail):-
  var(Var),
  !,
  remove_variables(Tail, NTail).
remove_variables(Res, Res).

因为似乎 SWI 的排序会首先留下无界变量（不知道这种行为是否是其他 prolog 中的标准），所以一旦找到第一个非变量，就可以停止删除变量。

阅读一点SWI 的文档，它指出：

4.7.1 Standard Order of Terms

Comparison and  unification of arbitrary  terms.   Terms are ordered  in
the so called ``standard order''.  This order is defined as follows:

 1. Variables < Numbers < Atoms < Strings < Compound Terms

所以当你找到第一个非变量时停止删除元素似乎是安全的......

于 2013-05-02T18:57:32.547 回答
1 
awesome([],[]).
awesome([H|T],R):- var(H), !, awesome(T,R).
awesome([H|T],R):- awesome(T,[H],R).

awesome([],R,R).
awesome([H|T],A,R):- memberchk(H,A) -> awesome(T,A,R) ; awesome(T,[H|A],R).

像这样的东西？理论上它是二次的，但是你的列表很短而且这段代码很简单，所以编译器可能会更好地优化。

如果您附加结果列表，最好将其更改为使用差异列表，将输出直接放入正在构建的结果列表中：

awesome([],Z,Z).
awesome([H|T],R,Z):- var(H), !, awesome(T,R,Z).
awesome([H|T],R,Z):- R=[H|Y], awesome(T,[H],Y,Z).

awesome([],_,Z,Z).
awesome([H|T],A,R,Z):- memberchk(H,A) -> awesome(T,A,R,Z) 
                                      ;  R=[H|Y], awesome(T,[H|A],Y,Z).

memberchk/2当然会剔除变量和重复项。

于 2013-05-02T18:06:47.900 回答
0

这是一个老问题，但作为参考，还有另一个不错的简短解决方案，使用setof.

my_awesome_predicate(L, Res) :-
    setof(X, (member(X, L), ground(X)), Res).

Res包含没有变量的解，其项按首次出现排序。

?- my_awesome_predicate([1,2,3,X,Y,3,2], Res).
Res = [1, 2, 3].
于 2019-06-07T11:53:40.657 回答