快速反向排序（SWI）Prolog

我正在寻找一种快速的方法来在Prolog中以相反的顺序对列表进行排序。算法上，它应该像标准排序一样快，但出于显而易见的原因，我提出的选项要慢得多。快速反向排序（SWI）Prolog

谓词rsort1/2排序然后反转。

rsort1(L1, L2) :- 
    sort(L1, Tmp), 
    reverse(Tmp, L2).

谓语rsort2/2使用predsort/3使用自定义比较。

rsort2(L1, L2) :- 
    predsort(reverse_compare, L1, L2). 

reverse_compare(Delta, E1, E2) :- 
    compare(Delta, E2, E1).

为了测试他们的表现我已经产生了巨大的随机列表如下：

?- Size = 1234567, 
    findall(N, (between(1, Size, _), N is random(Size)), Ns), 
    assert(test_list(Ns)). 
Size = 1234567, 
Ns = [183677, 351963, 737135, 246842, 22754, 1176800, 1036258|...].

这些是标准sort运行时间：

?- test_list(Ns), time(sort(Ns, NsS)). 
% 2 inferences, 7.550 CPU in 8.534 seconds (88% CPU, 0 Lips) 
Ns = [183677, 351963, 737135, 246842, 22754, 1176800, 1036258, 625628|...], 
NsS = [0, 1, 3, 5, 8, 10, 12, 14, 16|...].

...为rsort1 ：

?- test_list(Ns), time(rsort1(Ns, NsS)). 
% 779,895 inferences, 8.310 CPU in 9.011 seconds (92% CPU, 93850 Lips) 
Ns = [183677, 351963, 737135, 246842, 22754, 1176800, 1036258, 625628|...], 
NsS = [1234564, 1234563, 1234562, 1234558, 1234557, 1234556, 1234555|...].

...和rsort2：

?- test_list(Ns), time(rsort2(Ns, NsS)). 
% 92,768,484 inferences, 67.990 CPU in 97.666 seconds (70% CPU, 1364443 Lips) 
Ns = [183677, 351963, 737135, 246842, 22754, 1176800, 1036258, 625628|...], 
NsS = [1234564, 1234563, 1234562, 1234558, 1234557, 1234556, 1234555|...].

我能做得比rsort1和rsort2 speedwise更好？

来源

2010-11-15 Kaarel

考虑使用不同的输入进行基准测试。当许多排序算法的输入与正确顺序相反时，它们的输入是“已按顺序”和“最差”，它们可以做到“最好”，这可能解释了您在'rsort2'中看到的差异的很大一部分。 – aschepler 2010-11-15 18:39:55

@aschepler谢谢，我现在测试随机输入，它虽然没有改变，但... – Kaarel 2010-11-15 19:06:12

predsort/3比较慢，因为它不是内置的（它在SWI中的Prolog中编写，而sort/2和keysort/2用C写成）。使用keysort/2通常比predsort/3更快，但需要辅助（全局）堆栈空间来存放密钥。 – mat 2010-11-15 19:10:25

如果您使用的是可移植的排序例程（即使用PROLOG定义），那么您可能无法以更快（或快速，需要颠倒排序顺序）的方式执行任何操作那些在C/C++中本地执行排序例程的谓词，如sort/2或msort/2。

如果速度在这里是首要问题，那么你当然可以用外部定义编写自己的非可移植谓词来进行反向排序。例如，可以使用SWI-PL C++ interface（参见那里的示例）编写一个C++定义rsort/2，也许使用也在C++中实现的comparison predicates。

同样，您也可以使用SWI-PL C接口在C中编写rsort/2。 SWI-PROLOG资源中的src/pl-list.c包含用于sort/2，msort/2和的排序方法（即nat_sort()）的实现。要实施rsort/2，您可能只需遵循其实施并将调用的解释调整为compare()，即描述标准术语顺序。

来源

2010-11-15 21:09:50 sharky

-1

定义谓词：
1.获得列表中的最小数字。
2.删除列表中的项目。
3.合并两个列表。
4.
排序列表）获得最低
b）中删除最低在列表
C）进行排序，而不最低（递归将新列表）
与基座规则orderlist（[X] ，[X]）。

来源

2010-12-20 11:22:38

该算法相当低效。快速排序或合并排序在序言中更容易实现，而且速度更快......虽然纯序言版本不会击败内建版本。 – salva 2010-12-20 11:47:12

快速反向排序（SWI）Prolog

回答

相关问题