如何编写针对降序值的排序键函数？

Question

在最新版本的Python中，将sort()函数中的cmp函数替换为传递一个key函数，这使我在对某些对象执行复杂排序时变得更加棘手。

例如，我想按最新到最旧的顺序对一组对象进行排序，并使用一组字符串绑定器字段。因此，我希望日期按相反的顺序排列，但字符串按它们的自然顺序排列。使用比较函数，我可以将日期字段与字符串字段进行比较时翻转比较结果。但是，使用键函数，我需要找到某种方法来翻转/反转日期或字符串。

处理数字很容易（虽然丑陋） - 只需从某个值中减去它们即可，但是是否必须为日期（从另一个日期中减去并比较时间差？）和字符串（...我不知道如何以本地无关的方式反转它们的顺序）找到类似的技巧？

我知道有functools.cmp_to_key()，但它被描述为“主要用作转换工具，用于将程序转换为Python 3，其中不再支持比较函数”。这意味着我应该能够使用键方法做我想做的事情--但是怎么做？

- Kylotan

---

传递reverse=True只是改变了我需要找到一种反转的子键。例如，想象一下（出于某种奇怪的原因），我想按名字升序和姓氏降序排序。传递reverse=True只意味着现在我必须找到一种反转名字的方法，而不是姓氏。 - Kylotan

那个链接如何帮助并不清楚。 - Kylotan

可能是重复的问题: Python: List Sorting with Multiple Attributes and Mixed Order - Jesse

更好的标题应该是 如何对包含不同顺序的非数值元组进行排序？ - Martin Thoma

我可以举个例子吗？我刚准备好一个问题就看到了你的。 - Martin Thoma

Answer 1

最通用的方法是依次按每个键排序。Python的排序始终是稳定的，因此这样做是安全的：

sort(data, key=tiebreakerkey)
sort(data, key=datekey, reverse=True)

假设关键函数的相关定义已经确定，此方法将按照日期降序和绑定值升序对数据进行排序。

请注意，这种方法比生成单个组合键函数要慢，因为您最终将进行两次完整的排序。因此，如果您可以生成一个组合键，那么效果会更好，但将其拆分成单独的排序方法会提供很大的灵活性：给定每列的键函数，您可以制作任何这些函数的组合，并针对任何单独的列指定反向排序。

对于完全通用的选项：

keys = [ (datekey, True), (tiebreakerkey, False) ]
for key, rev in reversed(keys):
    sort(data, key=key, reverse=rev)

为了完整性，虽然我真的认为在可能的情况下应该避免使用：

from functools import cmp_to_key
sort(data, key=cmp_to_key(your_old_comparison_function))

我认为你应该避免这种情况的原因是，如果这样做，与使用键函数相比，您将需要 n log n 次调用比较函数（或者在两次排序时需要2n次调用）。

- Duncan

---

出于与katrielalex相同的原因，+1：虽然我不认为它算是“关键”函数，但它确实解决了问题，而且我认为它比比较函数不太优雅。 - Kylotan

尽管它比复合键函数慢，但它可能仍然比比较函数快得多。还可以编写一个cmp_to_key包装器，将任何比较函数包装成可用作键函数的形式，但这真的很混乱。 - Duncan

在functools模块中有一个cmp_to_key，因此您可以认为这比一般化到多个排序传递更清晰。但是我很惊讶cmp选项已被删除，因为它显然是执行某些排序的更清晰的方法。 - Kylotan

我很欣赏速度差异，但是Python很少实现优化，使代码变得明显丑陋。为什么不保留两个代码路径并记录“key”更快呢？ - Kylotan

该网址(http://wiki.python.org/moin/HowTo/Sorting/#Sort_Stability_and_Complex_Sorts)特别推荐这种方法用于复杂排序，并指出*Python中使用的Timsort算法能够高效地进行多重排序，因为它可以利用数据集中已有的任何排序顺序*. - ecatmur

Answer 2

做这件事情的缓慢而优雅的方法是创建一个具有相反顺序的值包装器：

from functools import total_ordering
@total_ordering
class ReversedOrder:
    def __init__(self, value):
        self.value = value
    def __eq__(self, other):
        return other.value == self.value
    def __lt__(self, other):
        return other.value < self.value

如果你没有 functools.total_ordering，那么你需要实现全部6个比较操作，例如：

import operator
class ReversedOrder:
    def __init__(self, value):
        self.value = value
for x in ['__lt__', '__le__', '__eq__', '__ne__', '__ge__', '__gt__']:
    op = getattr(operator, x)
    setattr(ReversedOrder, x, lambda self, other, op=op: op(other.value, self.value))

- ecatmur

---

如果 ReversedOrder 的唯一用处是用作排序键，那么您只需要实现 __lt__，可以安全地忽略其他所有内容。 - Duncan

@Duncan 这个在哪里有文档记录？我在参考资料中找不到。 - ecatmur

请查看Python 3的发行说明http://docs.python.org/release/3.0.1/whatsnew/3.0.html#ordering-comparisons。但我不知道它是否在主要文档中。 - Duncan

我会接受这个答案，因为其他帖子确实解决了问题，但这个答案最接近问题的答案。 - Kylotan

@Duncan：在list.sort的文档中有一个明确的保证：“此方法使用仅限于 < 比较项来就地对列表进行排序。” 排序 HOW TO 明确指出：“排序例程保证在比较两个对象时使用 __lt __()。因此，通过定义 __lt__() 方法，可以轻松地向类添加标准排序顺序:”（在此上下文中，“sort routines”指的是 list.sort 和 sorted）。 - ShadowRanger

Answer 3

我认为这份文档不完整。我理解“primarily”的意思是仍然有使用cmp_to_key的理由，而这就是其中之一。 cmp被删除是因为它是一个“有吸引力的危险物品”：人们会倾向于使用它，即使key才是更好的选择。

但是，你的情况显然更适合作为一个cmp函数，所以使用cmp_to_key来实现它。

- Ned Batchelder

---

+1 我同意这个答案，如果在那些更优雅的情况下使用 cmp 函数是更好的方式，那么使用 functools 已经提供的解决方案没有问题。 - wim

我想知道为什么这个函数没有针对这两种用例进行重载，即使等效映射结构是可能的。 - jxramos

Answer 4

对每个关键字分别进行两次排序，一次正序，一次倒序。

(Python的sort是稳定的；也就是说，除非必须更改原始列表的顺序，否则它不会更改原始列表的顺序。)

_{如果您关心相等元素的排序方式，则排序的顺序很重要。}

- Katriel

---

不错的想法。然而，与自定义比较函数相比，我认为这有点繁琐，并且在我的代码库中效果不佳（我根据输入选择排序键，然后一次调用sort()），但这肯定是解决问题的一种方法。 - Kylotan

Answer 5

一种方法是使用pandas库和参数ascending，通过设置你想要升序排列的列以及你想要降序排列的列来进行排序，例如：ascending=[True,False,False]

你不仅可以对两个级别（例如datetime和str）进行排序，还可以对所需的任意数量级别进行排序。

例如，如果你有以下数据：

d = [[1, 2, datetime(2017,1,2)], 
     [2, 2, datetime(2017,1,4)],
     [2, 3, datetime(2017,1,3)],
     [2, 3, datetime(2017,1,4)], 
     [2, 3, datetime(2017,1,5)], 
     [2, 4, datetime(2017,1,1)], 
     [3, 1, datetime(2017,1,2)]]

您可以设置您的 df。

df = pd.DataFrame(d)

并使用 sort_values

sorted_df = df.sort_values(by=[0,1,2], ascending=[True,False,False])
sorted_list = sorted_df.agg(list, 1).tolist()


[[1, 2, Timestamp('2017-01-02 00:00:00')],
 [2, 4, Timestamp('2017-01-01 00:00:00')],
 [2, 3, Timestamp('2017-01-05 00:00:00')],
 [2, 3, Timestamp('2017-01-04 00:00:00')],
 [2, 3, Timestamp('2017-01-03 00:00:00')],
 [2, 2, Timestamp('2017-01-04 00:00:00')],
 [3, 1, Timestamp('2017-01-02 00:00:00')]]

请注意，第一列按升序排列，而第二列和第三列按降序排列，这当然是由于设置了ascending=[True,False,False]的缘故。

- rafaelc

Answer 6

对于字符串，您可以使用一些公认的最大值（例如2^16或2^32），并使用chr()、unicode()、ord()等函数进行计算，就像处理整数一样。

在我的一个项目中，我知道我处理的是utf8编码的字符串，它们的序数低于0xffff，因此我写了以下代码：

def string_inverse(s):
    inversed_string = ''
    max_char_val = 0xffff
    for c in s:
        inversed_string += unicode(max_char_val-ord(c))
    return inversed_string        

result.sort(key=lambda x:(x[1], string_inverse(x[0])), reverse=True)

x的类型是：（字符串，整数），所以我得到的是，为了滥用SQL：

select * from result order by x[1] desc, x[0] asc;

- Kun Wu

Answer 7

试试这个：

>>> import functools
>>> reverse_key = functools.cmp_to_key(lambda a, b: (a < b) - (a > b))
>>> reverse_key(3) < reverse_key(4)
False
>>> reverse_key(3) > reverse_key(4)
True
>>> reverse_key('a') < reverse_key('b')
False

- Yankai Zhang