16

ISO-Prolog 提供sort/2并keysort/2依赖于术语顺序 (7.2)，通常称为“标准术语顺序”。El以不同顺序对列表进行排序的常用方法是将该列表的每个元素以某种方式映射到一个对XKey-El列表，然后对该列表进行排序，最后将键投影掉。作为一个例子，考虑如何keysort/2用sort/2（参见实现的注释）来表达。

在许多情况下，这种方法比使用依赖于用户定义的顺序（如 SWI'spredsort(C_3, List, SortedList) 或 SICStus' ）的通用实现特定排序谓词快得多samsort(O_2, List, SortedList)。

我的问题归结为：

是否存在使用predsort/3resp 进行排序的情况。samsort/3不能被一些映射、sort/2-ing和投影代替吗？1

为了清楚起见，最好坚持有限的基础术语。因为，无限的基础词项不具有一个总的词典顺序，因为它需要作为有限情况的扩展；此外，在 ISO/IEC 13211-1:1995 的 7.2.1 中，变量与两个不同变量的实现相关的情况的比较将如何结果尚不清楚：

7.2.1 变量

如果X和Y是不相同的变量，则
X term_precedes Y应依赖于实现
，除非在创建排序列表（
7.1.6.5、8.10.3.1 j）期间，排序应保持不变。

因此尚不清楚是否predsort/3仍符合创建排序列表的条件。很明显，在和期间 排序保持不变。sort/2keysort/2

1 感谢@WillNess，这个投影至少还应该包括reverse/2——或任何线性变换。这也意味着可以实现具有重复和唯一的结果（类似于实现的方式keysort/2）。

4

3 回答 3

4

首先，您可以“否定” Prolog 原子。让我们称之为atom_neg/2（这是一个愚蠢的名字，但无论如何它做了一些愚蠢的事情）：

atom_neg(A, NK) :-
    atom_codes(A, Cs),
    maplist(negate, Cs, NCs),
    append(NCs, [0], NK).

negate(X, N) :- N is -X.

我并不是说这样做是可行的，但显然，这是可能的。

全排序是弱排序，集合T上的关键函数f与f的共域上的全排序r一起定义弱排序wr(x, y) <==> r(f(x), f(y))。

（该上下文中函数的共域是函数返回的值的域。）

我可能完全错了，但是关系的存在需要密钥的存在：您可以根据另一个关系来定义关系，但最终您必须比较也可以孤立存在的东西：密钥。

这里的要点是，键不需要与我们要排序的事物在同一个域中，并且为同一域的对象定义了弱排序（关系） 。Prolog 在这里做了一些奇怪的事情：它为所有可能的术语定义了一个标准的术语顺序。Prolog 也没有正确的“类型”或“域”概念。我的直觉告诉我，对不属于同一域的事物进行排序根本不是很有用，但 Prolog 显然不同意。

您不能为两种情况定义键功能：

  1. 比较谓词保持自己的状态；
  2. 您有提供比较功能但不提供关键功能的“不透明”对象（例如，在 C 中定义）。

无论哪种方式，predsort都可能有用：没有人会喜欢atom_neg/2Will Ness 的解决方案。然而，它目前有一个严重的缺陷：它不允许稳定的排序。SWI-Prolog 已经可以以这种方式使用，只需将当前行为添加到predsort/3.

于 2015-07-25T09:48:23.993 回答
3

编辑：@Boris的答案显示了如何“否定”原子以进行比较，因此在这种情况下它使我的反对论点无效。问题中的新规定使其完全无效。

如果排序标准复杂，则必须安排多个子键。如果需要保留重复项，则递增索引应在原始术语的前缀之后，在排序子键之后，按照为sort/2排序而构建的术语。

但是，构建的子键的复杂性和数量可能会失控。在某些区域按升序或降序对点进行成像排序，首先按 X，然后按 Y，在某些区域按升序或降序排列，在其他区域按 Y 先，然后按 X。

然后，以标准术语顺序仅用线性数量的关键构造和对数线性数量的（可能是轻量的）比较替换对数线性数量（可能是计算量大）比较的优势可能会消失。

简单地说，predsort/3例如反向的原子列表，带有自定义比较谓词

comp(<,A,B):- B @< A.

等，不能通过sort/2ing 以“标准术语顺序”工作（引用 SWI 文档）来完成。有了数字，我们可以翻转标志，但不能用名字。

也许您想添加reverse到允许的操作。

在sort/4允许的情况下，我看不到任何不起作用的东西。并且由于它是稳定的，次要标准也可以通过次要通过（首先是次要标准，然后是主要标准）来适应。

于 2015-07-23T22:33:29.860 回答
2

我想我可能对你的问题有一个正确的答案。

如果您有部分排序，您仍然可以尝试使用 排序predsort/3，并且您可能会得到比仅仅说“不存在全排序”更好的结果。

这是一个示例：假设您有两支球队进行的比赛。每场比赛只给其中一支球队一分，你一直打到一支球队达到一定数量的分数。

现在，你组织了一场比赛，它有一个小组赛阶段，每组 4 支球队，这是一个循环赛。只有两支顶级球队才能从小组中脱颖而出。

每进行一场比赛，球队的得分为own_points - other_teams_points. 也就是说，如果你打到 7，最后的分数是：

A 队 - 5:7 - B 队

他们A队得分-2，B队得分2。

在小组赛阶段结束时，您按以下顺序对球队进行排序：

  1. 总得分
  2. 如果总分相同，则直接战斗获胜的队伍排名较高。

最值得注意的是，使用这种计分方案，如果 A 队击败 B 队，B 队击败 C 队，C 队击败 A 队，则无法解决三方平局。在这种情况下，“稳定”排序毫无意义。

但是，使用predsort/3，您可以尝试找到两个顶级团队，并且大多数情况下您都会得到明确的答案。解决上述三向平局通常使用抛硬币来解决。

于 2015-09-30T15:05:38.693 回答