2Fluent Python(第2版)

数据结构

序列与集合

列表元组字典集合双端队列

🎯 AI 时代的学习建议:不要只读理论。理解这一章的设计动机(为什么需要这个概念?)和边界条件(什么情况下会失效?)。当 AI 生成的代码涉及这些概念时,你能判断它是否用对了场景。AI 能帮你总结内容,但无法替代你亲手阅读、思考、建立直觉的过程。

第2章:数据结构

一、导读

1.1 本章学习目标

第2章深入讲解 Python 的内置数据结构:列表、元组、字典、集合、双端队列。重点在于理解它们的内部实现和使用技巧。

本章核心学习目标:

  • 掌握列表和元组的区别:可变 vs 不可变
  • 理解字典的内部实现:哈希表的优化
  • 掌握集合的数学运算:并集、交集、差集
  • 了解 collections 模块:deque、Counter、defaultdict

1.2 为什么本章如此重要

数据结构是编程的基础。Python 的内置数据结构经过高度优化,理解它们的特性有助于写出高效代码。

1.3 核心问题引导

列表的 append 为什么是 O(1) 均摊?

字典在 Python 3.7+ 为什么保持插入顺序?

元组比列表快的原因是什么?


二、核心概念详解

2.1 列表推导与生成器表达式

python
# 列表推导: 简洁高效
symbols = [chr(i) for i in range(32, 127) if i % 2 == 0]

# 嵌套推导
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
flat = [x for row in matrix for x in row]  # [1,2,3,4,5,6,7,8,9]

# 生成器表达式: 惰性求值,节省内存
total = sum(x * x for x in range(1_000_000))  # 不创建列表

# 笛卡尔积
colors = ['red', 'blue']
sizes = ['S', 'M', 'L']
shirts = [(c, s) for c in colors for s in sizes]

2.2 元组的不可变性

python
# 元组不可变,但包含的可变对象可以修改
t = (1, [2, 3], 4)
# t[0] = 10  # TypeError
t[1].append(5)  # OK: 修改的是列表,不是元组
print(t)  # (1, [2, 3, 5], 4)

# 元组作为字典键
locations = {}
locations[(35.68, 139.69)] = 'Tokyo'
locations[(51.51, -0.13)] = 'London'

# 命名元组
from collections import namedtuple
City = namedtuple('City', 'name country population coordinates')
tokyo = City('Tokyo', 'JP', 36.933, (35.689722, 139.691667))
print(tokyo.name)  # Tokyo
print(tokyo._fields)  # ('name', 'country', 'population', 'coordinates')

2.3 字典的优化

python
# Python 3.7+: 字典保持插入顺序
d = {'one': 1, 'two': 2, 'three': 3}
print(list(d.keys()))  # ['one', 'two', 'three']

# 字典推导
d = {chr(i): i for i in range(65, 70)}
# {'A': 65, 'B': 66, 'C': 67, 'D': 68, 'E': 69}

# 常用字典方法
d = {'a': 1, 'b': 2}
d.setdefault('c', 3)  # 如果键不存在,设置默认值
d.update({'d': 4, 'e': 5})
print(d.get('f', 0))  # 0 (不存在时返回默认值)

# defaultdict
from collections import defaultdict
index = defaultdict(list)
for word in ['apple', 'banana', 'avocado', 'blueberry']:
    index[word[0]].append(word)
# {'a': ['apple', 'avocado'], 'b': ['banana', 'blueberry']}

2.4 集合

python
# 集合运算
a = {1, 2, 3, 4}
b = {3, 4, 5, 6}

print(a | b)   # 并集: {1, 2, 3, 4, 5, 6}
print(a & b)   # 交集: {3, 4}
print(a - b)   # 差集: {1, 2}
print(a ^ b)   # 对称差集: {1, 2, 5, 6}

# 子集/超集
print({1, 2} <= a)   # True (子集)
print(a >= {1, 2})   # True (超集)

# frozenset: 不可变集合,可用作字典键
fs = frozenset([1, 2, 3])
d = {fs: 'value'}

三、实战案例

3.1 案例一:高效的去重和排序

python
# 去重保持顺序
def unique_preserve_order(seq):
    seen = set()
    result = []
    for item in seq:
        if item not in seen:
            seen.add(item)
            result.append(item)
    return result

items = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
print(unique_preserve_order(items))  # [3, 1, 4, 5, 9, 2, 6]

# 按多个键排序
students = [
    ('Alice', 'A', 85),
    ('Bob', 'B', 90),
    ('Charlie', 'A', 92),
    ('David', 'B', 78),
]
# 先按班级,再按分数降序
students.sort(key=lambda s: (s[1], -s[2]))

四、本章小结

列表推导简洁高效,生成器表达式节省内存

元组不可变,适合用作字典键和集合元素

字典在 Python 3.7+ 保持插入顺序

集合支持数学运算,适合去重和关系计算


五、思考与练习

为什么列表的 insert(0, x) 是 O(n)?

如何实现一个有序字典(在 Python 3.7 之前)?


2/8数据结构
0%