functools中的cmp_to_key函数如何工作？

Question

在Python中，list.sort方法和内置函数sorted都可以接受一个可选参数key，它是一个函数，给定列表中的一个元素返回其排序关键字。旧版本的Python使用了不同的方法，使用cmp参数，它是一个函数，给定列表中的两个元素，如果第一个小于第二个则返回负数，如果相等则返回零，如果第一个大于第二个则返回正数。在某个时候，这个参数被弃用并且没有包含在Python 3中。有一天我想按照cmp函数更容易编写的方式对元素列表进行排序。我不想使用废弃的特性，所以我阅读了文档，并发现有一个名为cmp_to_key的函数存在于functools模块中，正如其名称所示，它接收一个cmp函数并返回一个key函数... 或者至少在我阅读类似于源代码的高级函数所包含的文档中是这样的。

def cmp_to_key(mycmp):
    'Convert a cmp= function into a key= function'
    class K(object):
        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
    return K

尽管 cmp_to_key 能够按照预期工作，但我对这个函数返回的不是函数而是一个 K 类感到惊讶。为什么？它是如何工作的？我的猜测是 sorted 函数在内部检查 cmp 是否是函数或 K 类或类似的东西，但我不确定。 附言: 尽管有些奇怪，我发现 K 类非常有用。请查看以下代码：

from functools import cmp_to_key

def my_cmp(a, b):
    # some sorting comparison which is hard to express using a key function

class MyClass(cmp_to_key(my_cmp)):
    ...

这样，任何 MyClass 实例的列表都可以默认按照 my_cmp 中定义的标准进行排序。

- matiascelasco

---

这是 cmp_to_key 的源代码：https://github.com/python/cpython/blob/main/Lib/functools.py#L206 - Justin Harris

排序函数为什么需要检查某个东西是函数还是K类？它们只需调用键函数或每个元素并比较它们：key(a) < key(b)。只要key像可调用对象一样工作，那就没问题了。请参见https://en.wikipedia.org/wiki/Duck_typing。 - Justin Harris

当我尝试定义class MyClass(cmp_to_key(my_cmp)):时，出现了TypeError: cannot create 'functools.KeyWrapper' instances的错误。因此，我猜测这不是一种可靠的继承方式 - 似乎_functools（C实现版本）不支持这样做。 - wim

Answer 1

不需要，sorted函数（或list.sort）内部不需要检查其接收到的对象是函数还是类。它关心的只是在key参数中接收到的对象应该是可调用的，并且应返回一个可以与其他值进行比较的值。

类也是可调用的，当您调用类时，会返回该类的实例。

为了回答你的问题，首先我们需要理解（至少基本层次上）key参数的工作方式：

1. 对于每个元素，都会调用key可调用对象，并将其返回的对象用于排序。

2. 在收到新对象后，它与其他对象进行比较（通过使用另一个元素调用key可调用对象再次获得对象）。

现在要注意的重要事情是，接收到的新对象与其他相同对象进行比较。

现在来看你的等效代码，当你创建该类的一个实例时，可以使用你的mycmp函数将其与同一类的其他实例进行比较。而在排序时，比较这些对象（实质上）调用你的mycmp()函数以确定该值是否小于或大于其他对象。

带有打印语句的示例：

>>> def cmp_to_key(mycmp):
...     'Convert a cmp= function into a key= function'
...     class K(object):
...         def __init__(self, obj, *args):
...             print('obj created with ',obj)
...             self.obj = obj
...         def __lt__(self, other):
...             print('comparing less than ',self.obj)
...             return mycmp(self.obj, other.obj) < 0
...         def __gt__(self, other):
...             print('comparing greter than ',self.obj)
...             return mycmp(self.obj, other.obj) > 0
...         def __eq__(self, other):
...             print('comparing equal to ',self.obj)
...             return mycmp(self.obj, other.obj) == 0
...         def __le__(self, other):
...             print('comparing less than equal ',self.obj)
...             return mycmp(self.obj, other.obj) <= 0
...         def __ge__(self, other):
...             print('comparing greater than equal',self.obj)
...             return mycmp(self.obj, other.obj) >= 0
...         def __ne__(self, other):
...             print('comparing not equal ',self.obj)
...             return mycmp(self.obj, other.obj) != 0
...     return K
...
>>> def mycmp(a, b):
...     print("In Mycmp for", a, ' ', b)
...     if a < b:
...         return -1
...     elif a > b:
...         return 1
...     return 0
...
>>> print(sorted([3,4,2,5],key=cmp_to_key(mycmp)))
obj created with  3
obj created with  4
obj created with  2
obj created with  5
comparing less than  4
In Mycmp for 4   3
comparing less than  2
In Mycmp for 2   4
comparing less than  2
In Mycmp for 2   4
comparing less than  2
In Mycmp for 2   3
comparing less than  5
In Mycmp for 5   3
comparing less than  5
In Mycmp for 5   4
[2, 3, 4, 5]

- Anand S Kumar

---

当cmp_to_key(-1)被返回到key值时会发生什么？为什么2被与4进行两次比较，而5没有与2进行比较？我听不懂，请让我知道。请注意，我的任务是翻译，因此我将不包括任何解释或其他信息。 - Alok

@Alok 我还没有完全理解为什么2会被比较两次，但我可以解释为什么5不会与2进行比较。如果你想象一下列表中的每个值在移动时，每个项目的位置是从左到右确定的 - 当你为5找到一个位置时，它的左侧已经有了2、3、4。我们知道这些已经按正确的顺序排列了。所以你将5与这些值的中间值3进行比较。5不小于3，因此我们已经知道它不小于3左侧的任何东西，所以我们不需要检查2。 - SDJMcHattie

这真的非常糟糕，而且内存效率很低... - Ievgen

请在此阅读 https://docs.python.org/3/howto/sorting.html#the-old-way-using-the-cmp-parameter - pankaj

Answer 2

我刚刚意识到，尽管K类不是函数，但它是可调用的，因为它是一个类！而且类是可调用的，当被调用时，会创建一个新实例，通过调用相应的__init__进行初始化，然后返回该实例。

这样它就表现得像一个键函数，因为K在调用时接收对象，并将该对象包装在一个K实例中，该实例能够与其他K实例进行比较。

如果我错了，请纠正我。我感觉我正在进入我不熟悉的元类领域。

- matiascelasco

---

仅供参考，Python使用“元类”来指代比这个领域更加元和陌生的东西。但是无论如何，你说得对。在Python中，类和函数大多可以互换 - 任何需要调用函数并且不会刻意拒绝类的东西也可以给一个类（这可能令人惊讶，因为在许多其他语言中，类是特殊的，构造只是视觉上与函数调用相同 - 但在Python中，如果它看起来像函数调用，任何可调用的东西都可以放在那里）。 - mtraceur

Answer 3

我并没有查看源代码，但我相信关键函数的结果也可以是任何东西，因此也可以是可比较的对象。而 cmp_to_key 只是掩盖了这些 K 对象的创建，这些对象在 sort 进行工作时进行比较。

如果我尝试按照部门和房间号反转的顺序创建排序，就像这样：

departments_and_rooms = [('a', 1), ('a', 3),('b', 2)]
departments_and_rooms.sort(key=lambda vs: vs[0])
departments_and_rooms.sort(key=lambda vs: vs[1], reverse=True)
departments_and_rooms # is now [('a', 3), ('b', 2), ('a', 1)]

我不希望得到这样的结果，我认为sort()方法只在每次调用时是稳定的，文档 在我看来是误导性的：

sort()方法保证是稳定的。如果一个排序算法保证相等元素间的相对顺序不变，那么它就是稳定的——这对于多次排序很有帮助（例如，先按部门排序，再按薪资等级排序）。

旧的风格方法之所以有效，是因为每个调用K类的结果都返回一个K实例，并与mycmp的结果进行比较：

def mycmp(a, b):                             
    return cmp((a[0], -a[1]), (b[0], -b[1]))

departments_and_rooms = [('a', 1), ('a', 3),('b', 2)]
departments_and_rooms.sort(key=cmp_to_key(mycmp))
departments_and_rooms # is now [('a', 3), ('a', 1), ('b', 2)]

这是一个重要的区别，不能直接进行多次排序。键函数的值/结果必须按顺序可排序，而不是要排序的元素。因此需要使用cmp_to_key掩码：创建需要排序的可比较对象。

希望这可以帮到您。感谢您对cmp_to_key代码的洞察力，也对我有很大帮助 :)

- seishin

---

我在运行你的第一段核心代码后没有得到相同的结果。我得到了[('a', 3), ('b', 2), ('a', 1)]。 - matiascelasco

你是对的，这是我复制粘贴的错误。 关于元类，这个 K 类使用只是普通对象实例化。 - seishin

无法理解整个稳定排序与主题的关系。你能否请更好地解释一下？ - matiascelasco