Python cmp_to_key() 排序比较方法

说明

《Python 教程》持续更新中，提供建议、纠错、催更等加作者微信: gairuo123（备注：pandas教程）和关注公众号「盖若」ID: gairuo。跟作者学习，请进入 Python学习课程。欢迎关注作者出版的书籍：《深入浅出Pandas》和《Python之光》。

cmp_to_key() 是 Python 内置模块 functools 的一个高阶函数，将 (旧式的) 比较函数转换为新式的 key function ，针对 Iterable.sort() 或者 sorted(Iterable) 的稍微复杂一点的对象排序，在类似于 sorted() ， min() ， max() ， heapq.nlargest() ， heapq.nsmallest() ， itertools.groupby() 等函数的 key 参数中使用。此函数主要用作将 Python 2 程序转换至新版的转换工具，以保持对比较函数的兼容。

快速使用

比较函数意为一个可调用对象，该对象接受两个参数并比较它们，结果为小于则返回一个负数，相等则返回零，大于则返回一个正数。key function 则是一个接受一个参数，并返回另一个用以排序的值的可调用对象。通过这个函数可以把一个 cmp 函数（它支持两个参数，排序过程是一个对比过程，对比在两个元素之间进行）变成一个 key 函数，从而可以实现自定义排序规则。

《剑指 Offer》 45. 把数组排成最小的数案例中要求：输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例 1:

输入: [10,2]
输出: "102"
示例 2:

输入: [3,30,34,5,9]
输出: "3033459"

代码如下：

from functools import cmp_to_key

def sort_rule(x, y):
        a, b = x + y, y + x
        if a > b:
            return 1
        elif a < b:
            return -1
        else:
            return 0

nums = [3,30,34,5,9]
strs = [str(num) for num in nums]

sort_strs = sorted(strs, key=cmp_to_key(sort_rule))
sort_strs
# ['30', '3', '34', '5', '9']

''.join(sort_strs)
# '3033459'

参考：https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/

原理说明

Python 3 的 sorted() 函数发生了变化，它现在接受三个值，即 iterable、key 和 reverse。最后两个函数是可选的，我们主要来关注一下 key 参数部分。key 所做的是，它有助于在排序时比较 iterable 元素。在之前 Python 2 已经有了用于比较两个值并返回 1、-1 或 0 的 cmp() 函数：

cmp(x,y) 函数用于比较2个对象，如果 x < y 返回 -1, 如果 x == y 返回 0, 如果 x > y 返回 1。

Python 3 已经删除了对 cmp 参数的支持， cmp() 函数本身在 Python 2 里是一个内置函数。没有__lt__等6个富比较方法，Python 2.1 以前的排序比较方法只提供一个 cmp 比较函数参数，没有__lt__等6个富比较方法， Python 2.1 引入了富比较方法，Python 3.4 之后作废了 cmp 参数。相应地从 Python 2.4 开始，list.sort 方法和 sorted 等方法都增加了一个 ‘key’ 参数用来在进行比较之前指定每个列表元素上要调用的函数。但是这个函数不能支持两个对象之间进行比较，只支持对某个对象处理后返回一个值。

下面的文章将讨论此函数的应用和说明。

定义：

语法为 functools.cmp_to_key(callable)
cmp_to_key() 使用一个 key 来调用比较元素
它内置于 functools 模块中，因此必须首先导入 functools 才能使用该函数
与接受关键函数（如 min(), max(), sorted() 等）的有 key 参数的方法一起使用
严格接受一个为可调用的参数
此函数返回可用于比较元素的特殊键

callable（自定义函数）的解释：

接受两个参数
将每个元素与列表中的每个其他元素进行比较，直到获得排序后的列表
每个元素显然都使用列表中的其他元素调用 mycmp() 函数
函数的作用是：给出序列中任意两个元素的对比规则，大于返回1，小于返回-1，相同返回0
key 最终的结果最终帮助 sorted() 等按升序排列元素

如何理解

我们知道 sorted() 函数和列表的 sort() 方法：

[].sort
# <function list.sort(*, key=None, reverse=False)>
sorted
# <function sorted(iterable, /, *, key=None, reverse=False)>

不再支持 cmp 参数，而支持了 key 参数，它们的作用都是自定义一个排序方法。

它们的区别是：

key 参数：Python 3 支持，接受的函数（入参为每个元素）返回值（对这个元素的计算），表示此元素的权值，sorted 将按照权值大小进行排序
cmp 参数：Python 2 支持，接受的函数是元素中的所有需要对比的两个元素，这个函数定义大于（一般返回1）、小于（-1）、等于逻辑（1），最后根据这些比较逻辑排序

下边来通过案例进行讲解。

示例

比如，我们对一列字符串按它里边的数字大小进行排序：

from functools import cmp_to_key

def mycmp(a, b):
    # 提取字符中的数字
    a = int(''.join([i for i in a if i.isdigit()]))
    b = int(''.join([i for i in b if i.isdigit()]))
    
    if a > b:
        print(a, "vs", b, '=' , 1)
        return 1
    elif a < b:
        print(a, "vs", b, '=' , -1)
        return -1
    else:
        print(a, "vs", b, '=' , 0)
        return 0

sorted(['b29s', 'c2s20', 'a1-1', '88d'], key=cmp_to_key(mycmp))
'''
220 vs 29 = 1
11 vs 220 = -1
11 vs 220 = -1
11 vs 29 = -1
88 vs 29 = 1
88 vs 220 = -1

['a1-1', 'b29s', '88d', 'c2s20']
'''

不过，以上功能，也可以直接用 key 调用方法完成：

sorted(['b29s', 'c2s20', 'a1-1', '88d'], key=lambda x: int(''.join([i for i in x if i.isdigit()])))
# ['a1-1', 'b29s', '88d', 'c2s20']

使用 cmp_to_key 函数提供的键从列表中打印最大值和最小值的程序：

import functools


def mycmp(a, b):
    print("comparing ", a, " and ", b)
    if a > b:
        return 1
    elif a < b:
        return -1
    else:
        return 0


print(min([45, 78, 813], key=functools.cmp_to_key(mycmp)))
print(max([45, 78, 813], key=functools.cmp_to_key(mycmp)))
'''
comparing  78  and  45
comparing  813  and  45
45
comparing  78  and  45
comparing  813  and  78
813
'''

下边是不同的排序方法：

from functools import cmp_to_key

nums = [3, 30, 34, 5, 9]
new_nums = sorted(nums, key=cmp_to_key(lambda x, y: y - x))
new_nums2 = sorted(nums, key=cmp_to_key(lambda x, y: x - y))
print(new_nums)
print(new_nums2)
#结果:
#[34, 30, 9, 5, 3
#[3, 5, 9, 30, 34]

nums2 = map(str, nums)
new_nums2 = sorted(nums2, key=cmp_to_key(lambda x, y: int(x+y) - int(y+x)))
print(new_nums2)
#结果:
#['30', '3', '34', '5', '9']

一则从大到小和从小到大，另一则是将数字左边第一个先排序再按第二个排。

使用 cmp_to_key() 函数提供的键对列表进行排序的程序：

import functools

def mycmp(a, b):
    print("comparing ", a, " and ", b)
    if a > b:
        return 1
    elif a < b:
        return -1
    else:
        return 0

print(sorted([1, 2, 4, 2], key=functools.cmp_to_key(mycmp)))
'''
comparing  2  and  1
comparing  4  and  2
comparing  2  and  4
comparing  2  and  2
comparing  2  and  4
[1, 2, 2, 4]
'''

官方示例：

from functools import cmp_to_key

sorted(iterable, key=cmp_to_key(locale.strcoll))  # 区域设置感知排序顺序

富比较

富比较（rich comparison）是 Python 面向对象的一种实现方式。Python 的基类 object 提供一系列可以用于实现同类对象进行“比较”的方法，可以用于同类对象的不同实例进行比较。他们也是实例方法，定义如下：

object.lt(self, other) 小于
object.le(self, other) 小于等于
object.eq(self, other) 等于
object.ne(self, other) 不等于
object.gt(self, other) 大于
object.ge(self, other) 大于等于

其中 self 是指对象自身，other 是参与比较的另一对象，返回值最好为 bool 值，也可以是任意值（按布尔值的转换逻辑）。

以上这些方法，object 类实现了__eq__ 和 __ne__ 两个方法，上述这些方法默认返回值为 NotImplemented，需要自定义类实现这些方法才能正确使用这些方法，当然 __eq__ 和 __ne__ 这两个方法也可以重写。

实现细节

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__ or __gt__ 等，而代理键会将其转换为对 cmp 方法的调用。

所以列表 [1,2,3] 被排序为 [K(1), K(2), K(3)]，如果，比如说，将 K(1) 与 K(2) 进行比较，看看 K(1) 是否更小，那么 K(1) 调用 K(1).__lt__(K(2))，将其转换为 mycmp(1, 2) < 0。

这就是旧 cmp 方法的工作原理。返回 -1、0 或 1，具体取决于第一个参数是否小于、等于或大于第二个参数，代理键将这些数字转换回比较运算符的布尔值。代理键在任何时候都不需要知道任何关于绝对位置的信息，它只需要知道与之比较的另一个对象，而特殊的方法钩子提供了另一个对象。

总结

Python 3 中一些接受 key 的函数中（例如sorted，min，max，heapq.nlargest，itertools.groupby），key 仅仅支持一个参数，无法实现两个参数之间的对比。采用 cmp_to_key 函数，可以接受两个参数，对两个参数做处理，比如做和做差，转换成一个参数，就可以应用于 key 关键字了。

Python 3 为了语言的简洁性去掉了 cmp 这个参数，在 Python3 重自定义比较函数需要通过 cmp_to_key 将比较函数转化成 key 可以接受的参数。

参考

https://docs.python.org/zh-cn/3/library/functools.html#functools.cmp_to_key
https://www.geeksforgeeks.org/how-does-the-functools-cmp_to_key-function-works-in-python/
https://blog.csdn.net/LaoYuanPython/article/details/95042104
https://juejin.cn/post/6844903975955726350

Python 标准库 functools 高阶函数和可调用对象上的操作 reduce() 聚合执行 >

更新时间：2022-01-18 14:50:56 标签：python 高阶函数