示例如何在prolog中使用predsort(:Compare， +List， -Sorted)

Question

我想订购一个自定义列表。我要订购的单子在这张表格里……

[n(_,2,_),n(_,1,_),n(_,3,_)]  

我写了一个比较器

cheaper(n(_,C1,_),n(_,C2,_)) :-
        C1>C2.  

如何在预排序中使用它?我用冒泡排序写了一个排序算法，但是我有非常大的列表，所以它很慢。

有可能吗

predsort(cheaper, [n(_,2,_),n(_,1,_),n(_,3,_)] , X).

谢谢你

Answer 1

试试这个:

cheaper(>, n(_,C1,_),n(_,C2,_)) :-
        C1>C2.
cheaper(<, n(_,C1,_),n(_,C2,_)) :-
        C1<C2.
cheaper(=, n(_,C1,_),n(_,C2,_)) :-
        C1=C2.

请注意predsort的工作原理与sort类似，没有双精度运算!如果您想保持双精度，请尝试

cheaper(>, n(_,C1,_),n(_,C2,_)) :-
        C1>C2.
cheaper(<, n(_,C1,_),n(_,C2,_)) :-
        C1=<C2.

Answer 2

Joel已经展示了基本情况(+1)，但是为了获得更好的性能，请避免重复测试:

cheaper(R, n(_,C1,_),n(_,C2,_)) :-
        C1>C2 -> R = > ; R = < .

编辑

现在，SWI-Prolog有另一个内置的sort/4，在简单的情况下，它避免了与用户定义谓词调用相关的惩罚:

?- sort(2,@=<,[n(_,2,_),n(_,1,_),n(_,3,_)],S).
S = [n(_2578, 1, _2582), n(_2564, 2, _2568), n(_2592, 3, _2596)].

Answer 3

尽量避免使用predsort/3。这是一个特定于swi的谓词，效率不是特别高，因为所有的~ O(n log n)比较都是通过调用定义来执行的。而是尝试使用keysort/2，它是一个标准谓词，不会产生任何这样的调用开销:

因此，首先将列表Ns映射到配对列表KNs，然后排序，然后提取值。

n_pricep(N, C-N) :-
   N = n(_,C,_).
pair_value(_-V,V).
   ...,
   maplist(n_pricep, Ns, KNs),
   keysort(KNs, KNsS),
   maplist(pair_value, KNsS, NsS).