python3自定义排序规则

-
python3的sort不支持关键字cmp了，只支持关键字key，这个时候想要自定义复杂的排序规则就有点麻烦了。

首先key是什么呢？其实是个callable或者class。如果是callable，那么这个key做了什么事呢？

例如:


1
2
3
4
5
a = [1, 2, 3]
def F(x):
    return x + 1
 
a.sort(key=F)


本质上，python会把a的每一个元素都调用key(F)函数的得到返回值b


1
2
3
b = []
for i in a:
    b.append(F(i))


然后就是拿b去比较大小了。

这样存在一个问题，python每次只扔a的一个元素到key里，所以key对应的callable只能包含一个形参，这个让人非常无语。当实现复杂的排序规则时，往往要比较两个元素，例如：


1
a = [('bb','cc'), ('aa','bb'), ('bb','aa')]

当想要按照tuple的第一个关键字递增排序，在第一个关键字相同的情况下，按照第二关键字递减排序，这个就麻烦大了。

当然python提供了一个叫做functools.cmp_to_key的东西来帮助解决这个问题。

先上代码：


1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import functools
 
a = [('bb','cc'), ('aa','bb'), ('bb','aa')]
 
def cmp_1(x, y):
    if x == y:
        return 0
    if x < y:
        return -1
    return 1
 
def cmp_2(x, y):
    if x[0] == y[0]:
        return cmp_1(y[1], x[1])
    return cmp_1(x[0], y[0])
    
 
 
a.sort(key=functools.cmp_to_key(cmp_2))
 
print(a)
 
# output: a = [('aa', 'bb'), ('bb', 'cc'), ('bb', 'aa')]

我来分析一下：


1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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本质做了一件事，就是返回了一个类名，刚才也说了key也可以是class，当key是class的时候，python做了什么呢？


1
2
3
b = []
for i in a:
    b.append(K(a))


本质上就是将a里的元素逐个调用key(K)的构造函数，然后得到b(a list of K的对象)，然后怎么比较对象大小呢？ 显然调用__lt__方法了，所以可以看到上面__lt__的实现，本质调用了mycmp函数，因此我们只要将自定义排序规则定义在mycmp里就好了。

这里mycmp就是我代码里的cmp_2，这里有一个问题，mycmp的返回值，当小于成立时返回负数，等于返回0，大于返回正数，因此我定义了cmp_1来做这件事。

上面虽然解决了自定义排序问题，当时看着非常不自然，要定义两个cmp，难道没有像c++语言那样的定义方法吗？

当然有，我们自己传class给key就好了啊，然后定义__lt__函数，注意__lt__返回True表示小于，这个时候我们只要重写__lt__就可以了，类似c++的写法。


1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
import functools
 
a = [('bb','cc'), ('aa','bb'), ('bb','aa')]
 
class A():
    def __init__(self,x):
        self.x = x
    def __lt__(self, other):
        if self.x[0] == other.x[0]:
            return self.x[1] > other.x[1]
        return self.x[0] < other.x[0]
 
 
a.sort(key=A)
 
print(a)


总之，python3的自定义排序规则有点不自然，但是习惯就好。

Comments

Post a Comment