最佳实践：灵活运用内建容器，提高开发效率

本节以若干场景抛砖引玉，介绍如何选择内建容器对象，高效解决问题。

列表排序

我们经常需要对数据进行排序，例如制作一个积分榜。假设用户数据由 list 对象保存，数据项字段如下：

name ，名字；
sex ，性别；
area ，区域；
score，积分；

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


users = [{
    'name': 'jim',
    'sex': MALE,
    'city': 'guangzhou',
    'score': 28000,
}, {
    'name': 'lily',
    'sex': FEMALE,
    'city': 'shenzhen',
    'score': 25000,
}, ...]

为得到积分榜，我们需要对列表数据进行排序。这在 Python 中只是小菜一碟，list 对象 sort 方法即可胜任：

1

users.sort(key=lambda user: user['score'])

由于数据项类型 dict 不是 可比较 的，我们需要提供 key 函数，为每个数据项生成可比较的排序 key 。排序 key 可以是单字段，也可以复合字段，还可以是数据项的某种运算结果。

这样一来，sort 函数便按照 score 字段对数据进行排序，积分榜也就诞生了！

可比较对象

此外，我们可以用一个自定义类来抽象用户信息，并实现 eq 系列比较方法。借助 total_ordering 装饰器，我们只需要实现 eq 和 lt 两个比较方法，其他诸如 gt 等均由 total_ordering 自动生成：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


from functools import total_ordering

@total_ordering
class User:
    
    def __init__(self, name, sex, area, score):
        self.name = name
        self.sex = sex
        self.area = area
        self.score = score
        
    def __eq__(self, other):
        return self.score == other.score
    
    def __lt__(self, other):
        return self.score < other.score

这样一来，按积分排序 User 列表时，便不再需要提供 key 函数了：

1
2
3
4
5
6
7


users = [
    User(name=a1, age=a2, area=a3, score=a4),
    # ...
    User(name=z1, age=z2, area=z3, score=z4),
]

users.sort()

比较函数只能实现一种排序标准，我们的 User 类默认只能按积分，即 score 字段排序。如果想按 name 字段进行排序，则可以提供 key 辅助函数：

1

users.sort(key=lambda user: user.name)

由此可见，虽然 key 辅助函数应用起来要麻烦些，但 灵活性 更胜一筹。

排行榜

如果我们想将排名前 100 位的用户制作成积分榜，可以先按积分 降序排序 ，再取出前 100 个：

1
2


users.sort(reverse=True)
top100 = users[:100]

注意到，指定 reverse 参数为 True ，sort 方法便按降序排序。

sort 方法排序的时间复杂度为 $O(NlogN)$，如果基数 $N$很大，计算开销肯定也不小。由于积分榜只关心前 100 位用户，似乎没有必要对整个列表进行排序。这个场景非常典型，可以用最小堆来解决：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


from heapq import heappush, heappop

# 用一个最小堆来保存积分最多的100位用户
# 这样，积分最小的用户刚好在堆顶
top100 = []

# 遍历所有用户
for user in users:
    # 堆未满100，不断压入
    if len(top100) < 100:
        heappush(top100, user)
        continue
        
    # 如果当前用户积分比堆中积分最少的用户多，则替换
    if user > top100[0]:
        heappop(top100)
        heappush(top100, user)
        
 # 遍历完毕后，现在堆中保存的用户就是积分最多的100位了

引入最小堆后，制作排行榜的时间复杂度降为 $O(Nlog100)$。由于 $O(log100)$是个常数，因此时间复杂度等价于$O(N)$。更一般地，假设为$N$位用户制作长度为$K$的排行榜，两个方案的的时间复杂度分别是：

全量排序：$O(NlogN)$；
最小堆：$O(NlogK)$；

由于一般情况下，$K$远小于$N$，因此采用最小堆性能更理想。

还想知道更多内建容器的巧妙用法吗？点击 阅读原文 ，获取更多详细内容！

【Python源码剖析】系列文章首发于公众号【小菜学编程】，敬请关注：