Kodokon kodokon.com

进阶结构:元组、集合与 collections

为每种需求挑选合适的结构:不可变的元组、用于 O(1) 成员检测的集合,以及应对常见模式的 Counter 和 defaultdict。

9 分钟 · 3 题

在 Kodokon 中打开本课

选对数据结构,可以一举解决可读性和性能两个问题。元组是一个不可变的序列:非常适合表示固定长度的异构记录(坐标、一对键值)。不可变意味着可哈希(前提是它的内容也可哈希):因此元组可以充当字典的键或集合的元素,而列表则不行。解包让代码富有表现力 - 而一个 "返回多个值" 的函数,实际上返回的是一个元组。

PYTHON
point = (48.85, 2.35)
lat, lon = point

def min_max(values):
    return min(values), max(values)

low, high = min_max([3, 1, 4, 1, 5])
print(low, high)

distances = {("paris", "lyon"): 465}
print(distances[("paris", "lyon")])
解包、多值返回,以及把元组用作字典的键

集合保证元素唯一,并提供平均 O(1) 的成员检测,而列表则是 O(n)。在一个要执行成千上万次 x in collection 检查的循环里,差距会立刻显现出来。集合运算符(& 交集、- 差集、| 并集)相比嵌套循环是一次真正的升级:比较两份标识符列表 - 谁消失了、谁是新来的 - 两行代码就够了。

PYTHON
active = {"ada", "linus", "guido"}
banned = {"linus", "mallory"}

print(active & banned)
print(active - banned)
print(active | banned)

emails = ["a@x.io", "b@x.io", "a@x.io"]
unique = set(emails)
print(len(unique))
集合运算与去重

collections 模块覆盖了两个日常需求。Counter 统计可迭代对象中各元素出现的次数,并提供 most_common(n) - 再也不用手写计数字典了。defaultdict(factory) 会在需要时即时构造缺失的值:defaultdict(list) 是按键分组元素的标准工具,无需在循环的每一轮里都检测键是否存在。

PYTHON
from collections import Counter, defaultdict

words = ["go", "py", "go", "rs", "go"]
counts = Counter(words)
print(counts.most_common(2))

groups = defaultdict(list)
pairs = [("fr", "Ada"), ("us", "Lin"), ("fr", "Zoe")]
for country, name in pairs:
    groups[country].append(name)
print(dict(groups))
用 Counter 计数,用 defaultdict 分组

知识检测

确认你已牢记本课的重点内容。

  1. 为什么元组可以充当字典的键,而列表不行?
    • 因为它创建起来更快
    • 因为它不可变,因而可哈希
    • 因为它只能包含数字
    • 因为字典会把列表转换成元组
  2. 你要在 100,000 个元素上执行成千上万次 x in collection 的检测。应该选择哪种结构?
    • 列表,顺序扫描
    • 集合,成员检测平均为 O(1)
    • 元组,比列表更紧凑
  3. 在 groups = defaultdict(list) 的情况下,读取一个不存在的键会发生什么?
    • 抛出 KeyError
    • 返回一个空列表,并把这个键插入字典
    • 返回 None,且不修改字典