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刪除所有變量和副本

回答

相關問題