如何为降序值编写Python排序键函数

Question

在最近的Python版本中,将键函数传递给sort()前一个cmp函数的举动使得我对某些对象执行复杂的排序变得更加棘手.

例如,我想用一组字符串tie-breaker字段对从最新到最旧的一组对象进行排序.所以我希望日期顺序相反,但字符串按其自然顺序排列.使用比较函数,我可以反转日期字段与字符串字段的比较.但是通过关键功能,我需要找到一些方法来反转/反转日期或字符串.

使用数字很简单(虽然难看) - 只是从某些东西中减去它们 - 但我是否必须找到类似的日期(从另一个日期减去它们并比较timedeltas？)和字符串(...我不知道我如何以与语言环境无关的方式改变他们的顺序).

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

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调用比较函数与n调用key函数(或者2n当你进行两次排序时调用).

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))

Answer 3

我认为文档不完整.我将"主要"这个词解释为仍然有理由使用cmp_to_key,这就是其中之一. cmp被删除是因为这是一个"有吸引力的滋扰:"人们会倾向于它,即使这key是一个更好的选择.

但是你的情况作为一个cmp函数显然更好,所以用cmp_to_key它来实现它.

Answer 4

排序两次，每个键一次，一次反转。

（Pythonsort是稳定的；也就是说，除非必须，否则它不会更改原始列表的顺序。）

_{它确实你在做各种各样哪种顺序的事，如果你关心如何相等的元素进行排序。}