代码之家 › 专栏 › 技术社区 › Kaarel

快速反向排序(SWI)Prolog

prolog sorting

Kaarel · 技术社区 · 14 年前

我正在寻找一种在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号 快速?

2 回复 | 直到 11 年前

sharky 14 年前

如果你正在执行一个可移植的排序例程(即使用Prolog定义),那么你可能无法实现比在C/C++中执行排序例程的那些谓词更快(或者快速,需要反转排序顺序),例如 sort/2 或 msort/2 .

如果速度在这里是最重要的,那么您当然可以用外部定义编写自己的不可移植谓词来进行反向排序。例如 SWI-PL C++ interface 可以使用(参见示例)编写C++定义 rsort/2 ,可能使用 comparison predicates 也在C++中实现。

同样,你也可以写 排序/2 使用SWI-PL C接口。 src/pl-list.c 在SWI-PROLOG源代码中包含排序方法的实现(即 nat_sort() )用于 排序/2 , M端口/2 和 keysort/2 . 实施 排序/2 ,您可能只需要遵循它们的实现并调整/反转对 compare() 它描述了术语的标准顺序。

-1

chris amanse 14 年前

定义谓词:
一。得到列表中最低的数字。
2。删除列表中的项目。
三。合并两个列表。
四。列表排序依据
a) 最低的
b) 删除列表中最低的
c) 在没有最低值的情况下对新列表排序(递归)
使用基本规则orderlist([X],[X])。