sort/2，keysort/2与samsort/3，predsort/3的区别是什么？

Question

sort/2，keysort/2与samsort/3，predsort/3的区别是什么？

sortingprologiso-prolog

16

ISO-Prolog提供了sort/2和keysort/2，它们依赖于项序(7.2)，通常称为“标准项序”。

使用不同序列的常见方法是将该列表的每个元素El映射到一些对XKey-El的列表上，然后对该列表进行排序，最后投影键。例如，考虑如何用sort/2(请参阅实现说明)表示keysort/2。

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

我的问题可以简化为：

是否存在使用predsort/3或samsort/3无法替换的排序情况，需要使用映射、sort/2和投影?¹

为了清晰起见，最好遵循有限地、地面术语。因为无限地面术语没有总的字典序，因此需要将其扩展为有限地面术语; 此外，鉴于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/2和keysort/2期间，排序顺序保持不变。

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

- false

如果我们将“X term_precedes Y”定义为非传递关系，则“predsort”将根据初始输入顺序给出不同的结果。 - Eugene Sh.

@EugeneSh。keysort 在具有_等效_元素的列表排列上也会产生不同的结果，例如 keysort([a-b,a-c], Sorted) 和 keysort([a-c,a-b], Sorted)，尽管等价性是可传递的。 - user1812457

@EugeneSh.：换句话说，任何没有实现完全排序的关系，无论是不可传递还是其他任何情况，都不能与predsort/3一起使用！因此，您将获得准随机结果。相比之下，另一种方法也会给出类似的随机结果。 - false

3个回答

3

编辑：答案由@Boris给出，展示了如何"否定"原子以进行比较，因此在那种情况下它使我的反驳无效。而问题中的新规定则完全使其无效。

在复杂的排序标准下，多个子键将需要被排列。如果希望保留重复项，则应在原始术语之前加上递增索引，以跟随排序子键，构建用于sort/2排序的术语。

然而，构造的子键的复杂性和数量可能会失控。想象一下通过先按X排序，然后按Y排序，在某些地区按升序或降序排序，并且通过先按Y排序，然后再按X排序，在其他地区排序点。

那么，替换对术语进行标准顺序的对数级别（可能是计算量很大的）比较的对数级别的键构造和线性数量（可能是轻量级的）比较的优势可能会消失。

简单来说，使用自定义比较谓词对原子列表进行反转排序，可以使用predsort/3函数。

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

等等，无法使用sort/2对等号"标准顺序"（引用SWI文档）进行排序，这类排序方式无法处理复杂的内容。对于数字，我们可以改变符号，但对于名称则不行。

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

如果允许使用sort/4，我看不出任何不能排序的内容了。由于它是稳定的，次要条件也可以通过第二轮排序来满足（首先按次要标准排序，然后再按主要标准排序）。

- Will Ness

@j4nbur53，你的comp当然更好。 "切片和切块"可能使用了几个标准，比如按X排序，但如果相等，则按Y排序？我想我在最后一句中解决了它？（然后当然需要sort/4...） - Will Ness

sort/4似乎可以概括sort、msort和keysort。我认为predsort仍然可以做更多。Slice and dice的意思是，例如一个值子范围按B @< A排序，另一个值子范围按同一属性的A @< B排序，你不能用简单的sort和reverse组合来实现这一点。 - user502187

@j4nbur53，你可以使用多个子键。假设我们按升序排序[1..10]之间的随机数，但如果两个数字都在[3..8]之间，则交换顺序，对吧？那么对于x在[1..3]中的值为x-0，对于x在[3..8]中的值为5-x，对于[8..10]中的值为x-0。然后我们按第二个子键降序排列，然后按第一个子键升序排列。--另请参见Eugene Sh.的此评论。 - Will Ness

1

s(X)。你的例子表明我的问题没有以最好的方式提出。我想你会同意，没有人会说：我们需要predsort/3来解决这个例子。 - false

1

@j4nbur53和其他人：当然可以为原子或任意字符串定义“否定”。请参见我的答案。 - user1812457

显示剩余14条评论

2

我认为我可能有一个合适的答案来回答你的问题。如果你有一个部分排序，你仍然可以尝试使用predsort/3进行排序，并且你可能会得到比只是说“不存在完全排序”更好的结果。

这里有一个例子：假设你有一个由两个团队玩的游戏。每次游戏只给一个团队加分，直到一个团队达到一定数量的分数为止。

现在，你组织了一个锦标赛，在分组为4个团队的小组赛中进行循环轮换。只有前两支队伍才能脱颖而出。

对于每场比赛，团队得分为自己的得分减去其他团队的得分。换句话说，如果你打到7分，最终比分是：

团队A - 5:7 - 团队B

那么团队A得到-2分，团队B得到2分。

在小组赛结束时，你按以下方式对队伍进行排序：

1. 总得分 2. 如果总得分相同，则以胜利直接排名高的球队为先。

值得注意的是，使用这种计分方案，“你无法解决三方平局”的问题，例如：团队A击败团队B，团队B击败团队C，团队C击败团队A。在这种情况下，“稳定”的排序没有意义。

然而，使用predsort/3，你可以尝试找到前两支队伍，并且在大多数情况下会得到一个确定的答案。解决以上三方平局问题通常使用抛硬币的方式来解决。

- user1812457

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user1812457 · Accepted Answer

首先，您可以“否定”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.

我不是在声称这样做是实用的，但显然是可能的。

总排序是一种弱排序，关键函数 f 在集合 T 上以及定义在 f 的值域上的总排序 r，定义了 一个弱排序 wr(x, y) <==> r(f(x), f(y))。

(在该上下文中，函数的值域是函数返回的值的定义域。)

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

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

您无法为两种情况定义关键函数：

比较谓词保留其自己的状态；
您有“不透明”的对象（例如在C中定义），提供比较函数但不提供关键函数。

无论如何，predsort 都是有用的：没有人会喜欢 atom_neg/2 超过 Will Ness 的解决方案。但目前它有一个严重的缺陷：它不允许稳定排序。 SWI-Prolog 已经可以以这种方式使用, 只需要将当前行为添加到 predsort/3 的规范和文档中即可。