Python的cmp_to_key函数是如何工作的？

Question

我发现了这个函数 在这里。

我对它的实现方式感到困惑——通过使用 cmp_to_key 生成的 key 函数，如何知道给定元素的“位置”，而不检查与每个其他感兴趣的元素相比较的方式？

- math4tots

Answer 1

cmp_to_key 方法返回一个特殊的对象，它充当替代键：

class K(object):
    __slots__ = ['obj']
    def __init__(self, obj, *args):
        self.obj = obj
    def __lt__(self, other):
        return mycmp(self.obj, other.obj) < 0
    def __gt__(self, other):
        return mycmp(self.obj, other.obj) > 0
    def __eq__(self, other):
        return mycmp(self.obj, other.obj) == 0
    def __le__(self, other):
        return mycmp(self.obj, other.obj) <= 0
    def __ge__(self, other):
        return mycmp(self.obj, other.obj) >= 0
    def __ne__(self, other):
        return mycmp(self.obj, other.obj) != 0
    def __hash__(self):
        raise TypeError('hash not implemented')

在排序时，每个关键字都会与序列中的大多数其他关键字进行比较。这个元素在位置0是否小于或大于另一个对象？

每当发生这种情况时，就会调用特殊方法钩子，因此将调用__lt__或__gt__，而代理键将其转换为对cmp方法的调用。

因此，列表[1, 2, 3]按照[K（1），K（2），K（3）]进行排序，如果，例如，要将K（1）与K（2）进行比较以查看K（1）是否更低，则将调用K（1）.__ lt__（K（2）），然后翻译为mycmp（1,2）<0 。

无论如何，这就是旧的cmp方法的工作方式；根据第一个参数是否小于、等于或大于第二个参数返回-1、0或1。代理键将这些数字转换回比较运算符的布尔值。

代理键在任何时候都不需要了解关于绝对位置的信息。它只需要知道与之进行比较的另一个对象，而特殊方法钩子提供了其他对象。

- Martijn Pieters

---

“cmp_to_key”函数的存在只是为了支持使用Python 2的旧有排序代码。更简单的Python方法是使用sorted()的“key”函数。如果排序算法需要类似于“cmp()” 的方法，可以直接实现自定义的比较函数。请注意不要改变原文意思。 - Martijn Pieters

有时候很难想出一个“关键字”，但很容易想出一个比较函数……例如，我想对一组数字进行排序，使所有奇数按升序排列，并使所有偶数按降序排列。 - rlbond

@rlbond 返回一个元组，其中键为 (n % 2 == 0, (n % 2 and 1 or -1) * n)。 - Martijn Pieters

我知道你可以为那个问题制作一把钥匙。但我可以轻而易举地想出更难的东西。 - rlbond

@rlbond：然后创建定义自己排序的对象；您可以将它们用作键。这包括定义自己的丰富比较钩子，就像cmp_to_key()使用的K类一样。 - Martijn Pieters