使用比较器排序是否比使用key- function排序更好?

Is sorting with a comparator ever better than sorting with a key-func?

本文关键字：排序 更好 function 是否 比较器 key-      更新时间：2023-09-26

比较器函数的问题

  1. 行为是未定义的，当函数不是传递的，或者如果它不是反对称的。

  2. 预期的返回值，在集合{- 1,0,1}中的int，是尴尬的

  3. 它比keyfunc方法长，当声明式风格可以很好地完成时使用命令式风格

在JavaScript

下划线函数_.sortby(myArray, keyFunc) 是不是总是优于myArray.sort(comparatorFunc) ?

如果JS中没有这两个问题就好了:

  1. 不幸的是，_.sortBy没有"反向"参数，当你想按键的反向顺序排序。

  2. _.sortBy不将数组键视为具有字典顺序语义，它只是使用本地JS <操作符将它们转换为字符串，因此没有很好的方法来做任意字典顺序。

在Python中

最近实现的mylist.sort(key=keyfunc, reverse=True/False)似乎总是比旧的mylist.sort(cmp=comparatorfunc)方法好。

使用比较器1的排序比仅使用键选择器的排序更具通用性和灵活性。然而，这并不意味着一种方法一定"更好"，它归结为的实现和使用。

首先，比较器有一个目的——在任意值之间建立排序。此操作由sort函数使用，并且这种对值排序的方法必须在某个级别上存在。

考虑一个键选择器或者仅仅是一个方便的定义这样一个比较器的方法，其中<=>定义了一些自然排序(注意<=>本身就是一个比较器!)因此，键选择器实际上是到内置比较器的输入转换。

def comparator (a, b): 
    return a.x <=> b.x              -- explicit value selection
def comparatorForKeySelector (keyFn, a, b):
    return keyFn(a) <=> keyFn(b)    -- keys selected by function

如开头所述，选择归结为实现和使用。

第一个候选，underscore.js的sortBy碰巧是一个有限的实现;由于底层比较器不了解如何对返回的数组/序列排序，因此如果没有诸如字符串修改之类的技巧，就不可能对多个值进行排序。它也无法提供逆转排序的能力。这些实现问题都可以通过适当修改的内置比较器来解决。

第二个候选键选择器，Python的键排序，可以对多个键进行简单排序，这要归功于元组之间的排序。它还允许指定排序方向，使其成为更好的实现。然而，它不允许在键之间改变的排序方向(例如，第一个键升序排序，第二个键降序排序)，这也是由于元组之间的排序。

另一个候选键选择器，c#的LINQ，它没有上述任何限制，因为它与显式排序方向链接:people.OrderBy(p => p.Height).ThenByDescending(p => p.Weight)。我认为这是"理想的"键选择器实现，尽管它依赖于一些非常漂亮的底层支持。

在查看了三种不同的实现后，注意到它们可以以不同程度的成功和灵活性解决一类常见的问题，我回到我的介绍中:比较器比键选择器更通用，我认为"更好"的解决方案是同时支持[好]，这样一个特定的问题可以以最干净的方式解决。

1我使用术语comparator来表示一个函数-可能是一个操作符-在两个值之间建立排序。在原语级别，这可能仅通过关系和相等操作符对来实现。

A la carte:

当函数不是传递的，或者它不是反对称的时候，行为是未定义的。

那么函数是坏的，应该修复。损坏的代码就是损坏的代码，不能用作反对使用比较器的论据。

期望的返回值是集合{- 1,0,1}中的一个int，这很别扭

这是一种非常自然的表达方式;许多分类接受"小于零"、"零"answers"大于零"的值。这些可以更明确地键入-例如。使用常量-但与此类函数的语义无关。

它比keyfunction方法长，当声明式风格可以很好地工作时，它使用命令式风格

比较器不是隐式的"命令式风格"。在函数式语言中，它将是一种"函数风格"。键选择器通常更简洁明了;

相关文章：