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

钝鸟先飞,大器晚成。

—— 《增广贤文》

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

列表排序

我们经常需要对数据进行 排序 ,例如制作一个积分榜。假设用户数据由 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 参数为 Truesort 方法便按降序排序。

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源码剖析】系列文章首发于公众号【小菜学编程】,敬请关注:

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