Prolog删除所有变量和副本

我需要一个查询，这将从我的列表中删除我所有变量和重复。Prolog删除所有变量和副本

实施例：

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

来源

2013-05-02 Świstak35

好，你有最佳的复杂性。只能使用哈希映射才能实现更快的速度。无论如何你的名单多久了？ – 2013-05-02 18:12:16

您应该在您的示例中重命名结果变量 - 现在您的'X'既是'L'中的变量又是谓词的输出参数;我不认为这就是你的意图。 – l4mpi 2013-05-02 18:16:32

@ l4mpi谢谢，更正。 – 2013-05-02 18:23:46

如果您使用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的排序将首先离开无限变量（不知道这种行为是其他序言中的标准），因此，一旦找到第一个非变量，就可以停止移除变量。

读了一下SWI's documentation，它指出：

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-02 18:57:32 gusbro

约8％的改善，谢谢！ – 2013-05-02 20:20:30

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-02 18:06:47

Prolog删除所有变量和副本

回答

相关问题