Python-02-内置数据结构
本篇讲什么
Python 的日常代码有 80% 在跟四种结构打交道:列表(list)、元组(tuple)、字典(dict)、集合(set)。
本篇讲清它们的底层实现(动态数组、哈希表)、各自的操作与复杂度、如何用推导式与生成器表达式写得又短又快、浅拷贝与深拷贝的区别(附图示)、以及排序的稳定性与多关键字技巧。
读完后你应该能:看到一段需求就选对结构、说清每个操作的时间复杂度、并且不再踩"
[[0] 3] 3全变成同一行"这类经典陷阱。
一、是什么
四种内置容器一句话概括:
| 结构 | 一句话定义 | 有序 | 可变 | 元素可重复 | 元素要求 |
|---|---|---|---|---|---|
list 列表 | 动态数组,按位置存取 | 是 | 是 | 是 | 无 |
tuple 元组 | 不可变的序列,常用来表示"一条记录" | 是 | 否 | 是 | 无(但元素都不可哈希时才不可哈希) |
dict 字典 | 键值映射,基于哈希表 | 是(插入顺序) | 是 | 键不可重复 | 键必须可哈希 |
set 集合 | 不重复元素的容器,基于哈希表 | 否(逻辑上无序) | 是 | 否 | 元素必须可哈希 |
"可哈希(hashable)"的意思是:对象有一个在其生命周期内不变的哈希值,且能与其他对象比较相等——也就是实现了 __hash__() 与 __eq__()。数字、字符串、元组、frozenset 可哈希;list、dict、set 不可哈希。
二、为什么这样设计
| 设计 | 动机 | 代价 |
|---|---|---|
| 列表是动态数组而不是链表 | 数组的随机访问是 ,缓存友好;尾部追加均摊 | 头部插入/删除是 ;中间删除要搬移元素 |
| 元组不可变 | 可哈希(能当字典键)、可安全共享、语义上表达"不该被改的数据" | 每次"修改"都要创建新元组 |
| 字典用哈希表 | 平均 查找,是 Python 里最常见的加速手段 | 占内存较多;最坏情况(大量哈希冲突)退化为 |
| 3.7 起字典保证插入顺序 | 实现上改为"稀疏索引 + 紧凑条目"后,顺序天然稳定,索性写进语言规范 | 早期版本不能依赖此性质;有额外内存开销 |
| 集合也是哈希表 | 去重与成员判断 ,集合运算可读性极高 | 不保存顺序;元素必须可哈希 |
| 提供推导式 | 把"建容器 + 循环 + 条件"压缩成一个表达式,性能也更好(少了方法查找与 append 调用) | 嵌套过深可读性急剧下降 |
一句话选型
按位置取 → list;当记录/当键 → tuple;按键找值 → dict;去重与"在不在" → set。 拿不准时先用 list,出现"按某个字段查找"就换 dict,出现"判断是否出现过"就换 set。
三、核心内容
3.1 列表(list)
CPython 的 list 是动态数组:内部维护一块连续内存 + 已用长度 size + 已分配容量 allocated。追加元素时若容量不足,按约 1.125 倍扩容(CPython 实现细节,可能变化),因此 append 是均摊 。
常用操作与复杂度:
| 操作 | 写法 | 平均复杂度 | 说明 |
|---|---|---|---|
| 索引 | l[i]、l[-1] | 负索引从末尾数 | |
| 切片 | l[a:b] | 返回新列表 | |
| 切片赋值 | l[1:3] = [...] | 可改变长度,就地修改 | |
| 追加 | l.append(x) | 均摊 | 最常用 |
| 批量追加 | l.extend(it) | 等价于 l += it | |
| 插入 | l.insert(i, x) | 头部插入最贵 | |
| 删除(按值) | l.remove(x) | 只删第一个匹配;不存在报 ValueError | |
| 删除(按位置) | l.pop()、l.pop(i)、del l[i] | 尾部 ,中间 | |
| 查找位置 | l.index(x) | 不存在报 ValueError | |
| 计数 | l.count(x) | ||
| 成员判断 | x in l | 大列表上的 in 是性能陷阱 | |
| 排序 | l.sort(...) | 就地排序,返回 None | |
| 反转 | l.reverse() | 就地反转 | |
| 浅拷贝 | l.copy()、l[:]、list(l) | 只复制顶层 | |
| 长度 | len(l) |
3.2 元组(tuple)
元组是不可变序列,它存在的意义不只是"不能改的列表":
- 可以当字典键 / 放进集合(元素都可哈希时)。
- 表达异构记录:
("Ada", 36, "London")是"一条数据",而列表更适合"同类的多个数据"。 - 解包(unpacking):
name, age, city = row让代码自解释;*rest可收集剩余项。 - 更省内存、迭代更快:没有扩容预留空间与可变性检查。
| 对比项 | list | tuple |
|---|---|---|
| 可变性 | 可变 | 不可变 |
| 可哈希 | 否 | 元素可哈希时可哈希 |
| 内存占用 | 较大(预留容量) | 较小 |
| 语义 | 同质的序列 | 异质的记录 / 常量序列 |
| 能否作字典键 | 不能 | 能(例如坐标缓存 {(x, y): value}) |
namedtuple 让元组字段有名字,是可读性与性能的折中;需要可变记录时用 dataclasses.dataclass(见 Python-04-面向对象)。
3.3 字典(dict)
字典是哈希表。CPython 3.6 起采用的是"紧凑字典(compact dict)"布局:
indices(稀疏索引数组): [ -, 1, -, 0 ] ← 每个槽位存 entries 的下标
entries(紧凑条目数组): [(hash_a, key_a, val_a), (hash_b, key_b, val_b)]
↑ 按插入顺序追加,所以遍历顺序 = 插入顺序
- 查找:先算
hash(key)定位到 indices 的槽位,再用==比对 key,命中则取出对应 value。平均 ,最坏 。 - 装载因子:当已用槽位达到容量的 2/3 左右时扩容并重新散列(实现细节)。
- 顺序:entries 按插入顺序追加,删除某个键只在 entries 里留一个空位,不会打乱其余顺序——这就是"3.7 起插入顺序是语言保证"的来源。
键的要求与相等性规则:
| 规则 | 说明 |
|---|---|
| 键必须可哈希 | {[1]: "x"} 抛 TypeError: unhashable type: 'list' |
| 相等即同键 | a == b 必须推出 hash(a) == hash(b),否则字典行为不可预测 |
| 数值与布尔会合并 | hash(1) == hash(1.0) == hash(True),所以 {1: "int", 1.0: "float"} 只有一个键 |
| 保留首次插入的键对象 | {True: "a", 1: "b"} 结果是 {True: 'b'}:键仍是 True,值被更新 |
常用 API:
| 操作 | 写法 | 说明 | |
|---|---|---|---|
| 取值(可能缺失) | d.get(k)、d.get(k, 默认值) | 缺失不报错 | |
| 取值(缺失即建) | d.setdefault(k, 默认值) | 返回该键的值;缺失时先插入默认值 | |
| 取值(必须存在) | d[k] | 缺失抛 KeyError | |
| 批量更新 | d.update(other)、d.update(k=v) | 覆盖同名键 | |
| 删除 | del d[k]、d.pop(k)、d.pop(k, 默认值) | pop 可给默认值避免异常 | |
| 弹出最后插入项 | d.popitem() | LIFO 顺序(3.7+ 文档化) | |
| 成员判断 | k in d | 判断的是键,不是值 | |
| 键 / 值 / 条目视图 | d.keys()、d.values()、d.items() | 视图是动态的,字典变了它跟着变 | |
| 合并成新字典 | `d1 \ | d2`(3.9+,PEP 584) | 右边覆盖左边 |
| 就地合并 | `d1 \ | = d2、d.update(d2)` | 修改 d1 |
| 反向遍历 | reversed(d)(3.8+) | 按插入顺序反向 | |
| 复制 | d.copy() | 浅拷贝 |
collections 里的三个进阶字典(详见 Python-06-常用标准库):
| 类型 | 用途 | 关键方法 |
|---|---|---|
defaultdict(factory) | 缺失键自动用工厂函数创建值 | 不用再写 setdefault |
Counter(iterable) | 计数 | most_common(n)、update、+/- |
OrderedDict | 需要顺序敏感的相等性判断或 move_to_end | 两个 OrderedDict 顺序不同则不相等 |
3.4 集合(set)与 frozenset
集合也是哈希表,只存键不存值,因此去重与成员判断都是平均 。
| 操作 | 运算符 | 方法 | 复杂度 | |
|---|---|---|---|---|
| 并集 | `a \ | b` | a.union(b) | |
| 交集 | a & b | a.intersection(b) | ||
| 差集 | a - b | a.difference(b) | ||
| 对称差 | a ^ b | a.symmetric_difference(b) | ||
| 子集 / 超集 | a <= b、a >= b | issubset、issuperset | ||
| 不相交 | — | a.isdisjoint(b) | 命中即返回 | |
| 增删 | — | add、discard(不报错)、remove(报 KeyError)、pop(弹出任意一个) |
要点:
- 空集合必须写
set():{}是空字典。 - 集合不保存顺序,
list({...})的顺序不可依赖;需要"去重且保序"时用dict.fromkeys(seq)。 frozenset不可变、可哈希,因此能当字典键或放进另一个集合;set不能。- 集合元素必须可哈希,所以"列表的列表"不能直接去重,要转成元组:
set(map(tuple, rows))。
3.5 四种结构选型对比
| 需求 | 首选 | 原因 | 次选 |
|---|---|---|---|
| 按下标随机访问 | list | 索引 | tuple(不改动时) |
| 频繁在两端增删 | collections.deque | 两端 | list(尾部 、头部 ) |
| 表示一条不可变记录 | tuple / namedtuple / dataclass(frozen=True) | 可哈希、可解包、语义清晰 | dict |
| 按键快速查找 | dict | 平均 | — |
| 判断"是否存在"、去重 | set | 平均 ,集合运算直观 | dict.fromkeys(需要保序时) |
| 需要有序且按范围查询 | bisect + 有序 list | 二分 | 数据库/索引结构 |
| 需要"每个键对应多个值" | defaultdict(list) / dict[str, list] + setdefault | 语义清楚 | dict[str, set](需要去重) |
| 需要优先级队列 | heapq | 堆操作 | queue.PriorityQueue(多线程) |
3.6 推导式与生成器表达式
四种写法对照:
| 形式 | 语法 | 结果类型 | 惰性 | 备注 |
|---|---|---|---|---|
| 列表推导式 | [f(x) for x in it if cond] | list | 否,立刻求值 | PEP 202 |
| 字典推导式 | {k: v for k, v in it} | dict | 否 | PEP 274 |
| 集合推导式 | {f(x) for x in it} | set | 否 | 会去重 |
| 生成器表达式 | (f(x) for x in it) | generator | 是,按需产出 | PEP 289,只能消费一次 |
关键语义(务必记住):
- 多个
for是从左到右嵌套:[x for row in matrix for x in row]等价于两层循环,外层写在前面。 if是过滤,x if c else y是映射,两者可以同时出现。- 推导式有自己的作用域,循环变量不会泄漏到外层(Python 3 的行为;Python 2 会泄漏)。
- 生成器表达式是惰性的且一次性:
sum(gen)之后再list(gen)得到空列表。它适合流式处理大数据,因为不会一次性把所有元素放进内存。
3.7 浅拷贝与深拷贝
- 浅拷贝(shallow copy):新建外层容器,元素仍是原对象本身(共享)。
- 深拷贝(deep copy):递归复制所有嵌套对象,两份数据完全独立。
graph TD
A["原对象 a = [inner, d]"] --> A0["a[0] → 内层列表 [1, 2]"]
A --> A1["a[1] → 内层字典 {k: v}"]
B["浅拷贝 b = a.copy()"] --> A0
B --> A1
C["深拷贝 c = deepcopy(a)"] --> C0["新的内层列表 [1, 2]"]
C --> C1["新的内层字典 {k: v}"]
文字版示意:
a ─┬─► [1, 2] ← 同一个内层列表
└─► {k: v} ← 同一个内层字典
b ─┴─►(与 a 共享上面两个对象,但自己是新列表)
c ─┬─► [1, 2] ← 副本
└─► {k: v} ← 副本
| 拷贝方式 | 代码 | 深度 | 适用 |
|---|---|---|---|
| 切片 | b = a[:] | 浅 | 一维列表 |
| 构造 | list(a)、dict(d)、set(s) | 浅 | 任意可迭代对象 |
| 方法 | a.copy()、d.copy() | 浅 | 推荐写法,意图明确 |
| 复制模块 | copy.copy(a) | 浅 | 自定义类 |
| 深拷贝 | copy.deepcopy(a) | 深 | 嵌套可变结构 |
copy.deepcopy 内部用 memo 字典记录已复制对象,因此能正确处理自引用(循环引用);同时它支持通过 __deepcopy__ 自定义行为。深拷贝的代价是慢且可能"复制过多"(例如把本该共享的配置对象也复制了)。
3.8 序列通用操作
只要对象实现了序列协议(__getitem__、__len__ 等),下面这些都能用:str、list、tuple、range、bytes、array.array。
| 操作 | 示例 | 说明 |
|---|---|---|
| 成员判断 | x in seq | list/tuple 是 ,str 是子串匹配 |
| 长度 | len(seq) | |
| 聚合 | min、max、sum、any、all | 都是 ;any/all 短路 |
| 拼接 / 重复 | a + b、a * 3 | 返回新对象;a += b 对 list 是就地扩展 |
| 切片 | seq[a:b:c] | 返回同类型的新对象 |
| 计数 / 定位 | seq.count(x)、seq.index(x) | |
| 遍历并编号 | enumerate(seq, start=1) | 返回 (下标, 元素) 迭代器 |
| 并行遍历 | zip(a, b)、zip(a, b, strict=True)(3.10+) | 默认以最短为准,strict 会在长度不等时抛 ValueError |
| 反向遍历 | reversed(seq) | 返回迭代器,不复制 |
| 排序 | sorted(seq, key=..., reverse=...) | 返回新列表 |
| 解包 | a, b, rest = seq、f(seq) | PEP 448 起支持更灵活的解包 |
可迭代(iterable)≠ 序列(sequence)≠ 迭代器(iterator)
字典、集合、文件对象是可迭代但不是序列(不能索引);生成器、
zip/map/filter的返回值是迭代器(只能消费一次,且本身也是可迭代对象)。for只要求可迭代。
3.9 排序稳定性与多关键字排序
Python 的排序用 Timsort:稳定(stable),最好情况 (已基本有序),最坏 ,需要 辅助空间。
"稳定"指键相等的元素保持原有相对顺序。它带来一个非常实用的技巧:多关键字排序可以分解为多次稳定排序(先排次要键,再排主要键)。
people = [("Bob", 30), ("Ada", 25), ("Cyd", 30), ("Dan", 25)]
# 写法一:元组键(推荐,一次排序)
sorted(people, key=lambda p: (p[1], p[0])) # 先按年龄升序,再按姓名升序
# 写法二:稳定排序两趟(当某个键需要单独降序而另一个升序时最方便)
step1 = sorted(people, key=lambda p: p[0]) # 先排次要键
step2 = sorted(step1, key=lambda p: p[1]) # 再排主要键
# 需要用 operator 提速(比 lambda 略快,且意图清楚)
from operator import itemgetter, attrgetter
sorted(people, key=itemgetter(1, 0))
| 需求 | 写法 |
|---|---|
| 单键升序 | sorted(data, key=keyfunc) |
| 单键降序 | sorted(data, key=keyfunc, reverse=True) |
| 多键,全部升序 | key=lambda x: (x.a, x.b) |
| 多键,数字降序 + 文本升序 | key=lambda x: (-x.age, x.name)(数字取负) |
| 多键,混合升降且不能取负 | 多趟稳定排序,或 functools.cmp_to_key |
reverse=True会反转"相等元素"的顺序吗?不会。
reverse=True仍然稳定:键相等的元素保持原相对顺序(文档明确说明)。唯一要注意的是:reverse=True不是"排序后再反转列表",对相等元素而言两者结果不同。
四、怎么用(可运行示例)
4.1 列表:增删改查与切片赋值
nums = [3, 1, 4, 1, 5]
nums.append(9) # 尾部追加:[3, 1, 4, 1, 5, 9]
nums.extend([2, 6]) # 批量追加(等价于 += )
nums.insert(0, 99) # 头部插入 O(n):尽量避免在大列表上这样写
print(nums)
# 切片赋值可以改变长度,且是就地修改(其他引用能看到变化)
nums[0:1] = [] # 删掉第一个元素
nums[1:1] = [77] # 空切片赋值 = 插入
print(nums)
# 按值删除只删第一个匹配
nums.remove(1)
print(nums)
# 就地排序、反转(都返回 None)
print(nums.sort(reverse=True), nums) # None [77, 9, 6, 5, 4, 3, 2, 1]
print(nums.reverse(), nums) # None [1, 2, 3, 4, 5, 6, 9, 77]
# 索引与负数下标(注意 reverse 是就地反转,此时列表已经被反转了)
print(nums[0], nums[-1], nums[1:3], nums[::-1])
4.2 一个真实陷阱: * 3 与 +=
# 陷阱一:重复运算符复制的是"引用",三行是同一个列表
bad = [[]] * 3
bad[0].append(1)
print(bad) # [[1], [1], [1]]
# 正解:推导式每次都新建对象
good = [[] for _ in range(3)]
good[0].append(1)
print(good) # [[1], [], []]
# 陷阱二:+= 是就地扩展(别名可见),= a + b 是新建对象
a = [1, 2]
alias = a
a += [3]
print(a, alias, a is alias) # [1, 2, 3] [1, 2, 3] True
c = [1, 2]
alias2 = c
c = c + [3] # 新对象绑定回 c,alias2 还是老对象
print(c, alias2, c is alias2) # [1, 2, 3] [1, 2] False
4.3 元组:解包与命名元组
from collections import namedtuple
# 解包:交换、星号收集、函数返回多值
point = (3, 4)
x, y = point
x, y = y, x
print(x, y)
first, *middle, last = [1, 2, 3, 4, 5]
print(first, middle, last) # 1 [2, 3, 4] 5
def min_max(values):
# 返回元组是 Python 表达"多返回值"的惯用法
return min(values), max(values)
low, high = min_max([3, 1, 4, 1, 5])
print(low, high)
# 元组可以当字典键:用坐标做缓存
cache = {(0, 0): "origin", (1, 1): "diag"}
print(cache[(0, 0)])
# 命名元组:可读性接近类,开销接近元组
Point = namedtuple("Point", ["x", "y"])
p = Point(1, 2)
print(p, p.x, p._asdict(), p._replace(y=10))
# 注意:_replace 返回新对象,原对象不变(不可变语义)
print(p)
# 单元素元组的逗号不能省
print(type((1)), type((1,))) # <class 'int'> <class 'tuple'>
4.4 字典:查找、聚合与合并
word_count = {}
for w in "the quick the lazy the end".split():
# setdefault 一次完成"缺失则建 + 返回该键的值",避免两次查找
word_count.setdefault(w, 0)
word_count[w] += 1
print(word_count)
# 更 Pythonic 的计数方式
from collections import Counter, defaultdict
print(Counter("the quick the lazy the end".split()).most_common(2))
# 分组:defaultdict 让"缺失即建列表"不用写模板代码
by_len = defaultdict(list)
for w in ["a", "bb", "cc", "ddd"]:
by_len[len(w)].append(w)
print(dict(by_len))
# 安全取值:区分"键不存在"和"值是 None"
config = {"retries": 0, "name": None}
print(config.get("retries"), config.get("missing"), config.get("name"))
print(config.get("missing", 3)) # 给默认值
# 合并(3.9+):右边覆盖左边
defaults = {"host": "localhost", "port": 80}
overrides = {"port": 8080}
print(defaults | overrides, defaults) # 原字典不变
merged = {**defaults, **overrides} # 3.5+ 的等价写法
print(merged)
# 遍历的三种姿势
for k in merged: # 只遍历键
pass
for k, v in merged.items(): # 同时拿键值(推荐)
pass
for v in merged.values(): # 只遍历值
pass
# 视图是动态的:字典变了,已取得的视图跟着变
d = {"a": 1, "b": 2}
items = d.items()
d["c"] = 3
print(list(items)) # [('a', 1), ('b', 2), ('c', 3)]
# 3.8+ 反向遍历;popitem 按 LIFO 弹出
print(list(reversed(d)), d.popitem())
4.5 一个必须知道的行为:1、1.0、True 是同一个键
print(hash(1) == hash(1.0) == hash(True)) # True
d = {1: "int", 1.0: "float", True: "bool"}
print(d) # {1: 'bool'} —— 三个写入落到了同一个键,值被最后一次覆盖
print({True: "a", 1: "b"}) # {True: 'b'}:键保留首次插入的那个对象
print({1: "x"}[True]) # x:用 True 能查到键 1 的值
# 工程后果:不要用"0/1"和"False/True"混合作键,也不要用浮点当键
4.6 集合:去重与集合运算
tags_a = {"python", "backend", "docker"}
tags_b = {"python", "frontend"}
print(tags_a & tags_b) # 交集
print(tags_a | tags_b) # 并集
print(tags_a - tags_b) # 差集
print(tags_a ^ tags_b) # 对称差
print(tags_a.isdisjoint({"golang"}))
print({"python"} <= tags_a) # 子集
# 去重且保持原顺序(set 不保序,所以用 dict.fromkeys)
names = ["b", "a", "b", "c", "a"]
print(list(dict.fromkeys(names))) # ['b', 'a', 'c']
print(sorted(set(names))) # ['a', 'b', 'c']
# 空集合不是 {}
print(type(set()), type({}), bool(set())) # <class 'set'> <class 'dict'> False
# frozenset 可哈希:能当键,也能放进集合
perms = {frozenset({"read", "write"}), frozenset({"read"})}
print(frozenset({"read"}) in perms, hash(frozenset({"read"})) is not None)
# 大列表去重的性能差异:set 判断是 O(1),list 是 O(n)
big = list(range(20_000))
as_set = set(big)
print(19_999 in big, 19_999 in as_set)
4.7 推导式与生成器表达式
matrix = [[1, 2, 3], [4, 5, 6]]
# 嵌套推导式:外层 for 写在左边,等价于两层循环
print([[row[i] for row in matrix] for i in range(3)]) # 转置
print([x for row in matrix for x in row]) # 展平
# 过滤 + 映射
print([x for x in range(10) if x % 3 == 0]) # [0, 3, 6, 9]
print([x if x % 2 else -x for x in range(4)]) # [0, 1, -2, 3]
# 字典推导式:翻转键值、由两个序列配对
ages = {"Ada": 36, "Bob": 41}
print({age: name for name, age in ages.items()})
print({k: v for k, v in zip("abc", range(3))})
# 集合推导式
print({abs(x) for x in (-1, 1, -2)}) # {1, 2}
# 生成器表达式:惰性、省内存、只能消费一次
gen = (x * x for x in range(5))
print(sum(gen)) # 30
print(list(gen)) # [] —— 已经消费完了
# 大数据场景:用生成器表达式避免创建中间列表
total = sum(len(w) for w in ("alpha", "beta", "gamma"))
print(total)
# 推导式有自己的作用域,循环变量不会泄漏
[i for i in range(3)]
print("i" in dir()) # False
4.8 浅拷贝与深拷贝
import copy
inner = [1, 2]
orig = [inner, {"k": "v"}]
shallow = copy.copy(orig) # 或 orig.copy() / orig[:] / list(orig)
deep = copy.deepcopy(orig)
# 1) 通过原引用修改嵌套对象:浅拷贝"看得到",深拷贝看不到
inner.append(3)
print(orig, shallow, deep)
# 2) 修改浅拷贝里的嵌套字典,原对象也会变(共享同一个字典)
shallow[1]["k"] = "changed"
print(orig[1], shallow[1], deep[1])
# 3) 顶层互不影响
shallow.append("new")
print(len(orig), len(shallow), len(deep)) # 2 3 2
# 4) 深拷贝能处理循环引用
a = []
a.append(a) # a 引用自己
b = copy.deepcopy(a)
print(b[0] is b) # True:副本内部仍自引用,且不无限递归
4.9 序列通用操作:zip / enumerate / reversed
names = ["Ada", "Bob", "Cyd"]
scores = [92, 78, 85]
# zip 并行遍历;默认以最短为准 —— 长度不等会静默丢数据
print(list(zip(names, scores)))
print(list(zip(names, scores, [1, 2]))) # 只出 2 对
try:
list(zip(names, scores, [1, 2], strict=True)) # 3.10+:长度不等直接报错
except ValueError as e:
print("strict:", e)
# 用 zip 建字典、转置矩阵
print(dict(zip(names, scores)))
print(list(zip(*[[1, 2], [3, 4], [5, 6]]))) # [(1,3,5), (2,4,6)]
# enumerate 从 1 开始编号
for i, name in enumerate(names, start=1):
print(f"{i}. {name}")
# reversed 返回迭代器,不复制列表
print(list(reversed(names)), names) # 原列表不变
# 通用聚合
print(len(scores), min(scores), max(scores), sum(scores), sum(scores) / len(scores))
print(any(s < 60 for s in scores), all(s >= 60 for s in scores))
4.10 排序:稳定性与多关键字
from operator import itemgetter
people = [("Bob", 30), ("Ada", 25), ("Cyd", 30), ("Dan", 25)]
# 单键升序 / 降序
print(sorted(people, key=itemgetter(1)))
print(sorted(people, key=itemgetter(1), reverse=True))
# 稳定性:年龄相同的两人保持原有先后顺序
print(sorted(people, key=lambda p: p[1])) # Ada 在 Dan 前(原顺序)
# 多关键字:年龄升序 + 姓名升序
print(sorted(people, key=lambda p: (p[1], p[0])))
# 年龄降序 + 姓名升序(数字取负实现降序)
print(sorted(people, key=lambda p: (-p[1], p[0])))
# 两趟稳定排序:先次要键,再主要键;等价于上面但支持"文字键降序"
step1 = sorted(people, key=itemgetter(0), reverse=True) # 姓名降序
step2 = sorted(step1, key=itemgetter(1)) # 年龄升序(稳定)
print(step2)
# 排序对象属性:attrgetter 比 lambda 略快,也比手写 lambda 更清晰
from collections import namedtuple
Person = namedtuple("Person", "name age")
objs = [Person("Bob", 30), Person("Ada", 25)]
from operator import attrgetter
print(sorted(objs, key=attrgetter("age")))
# 老式比较函数(返回负数/0/正数)需要用 cmp_to_key 适配
import functools
print(sorted([3, 1, 2], key=functools.cmp_to_key(lambda a, b: b - a))) # [3, 2, 1]
五、注意事项与常见坑
**坑 1:
n与[0] n的区别**
[0] 3安全(整数不可变,改一个元素是重新绑定);3会让三行指向同一个内层列表,bad[0].append(1)后三行全是[1]。二维结构一律用推导式:[[0] * cols for _ in range(rows)]。
坑 2:
list.sort()返回None,不是排序后的列表
a = [3, 1].sort()会让a变成None(就地排序的副作用),下一行a[0]直接TypeError。需要新列表就用sorted(...);想链式调用也只能用sorted。同样的"返回 None"还有append、extend、remove、reverse、d.update。
坑 3:浅拷贝共享嵌套对象
b = a.copy()(或a[:]、list(a))只复制顶层。嵌套的列表/字典仍是同一个对象,改b[0][0]会连带改a。嵌套结构要么用copy.deepcopy,要么改成不可变数据(元组/frozenset/字符串)从根上避免共享可变状态。
坑 4:可变对象不能当字典键或集合元素
{[1]: "x"}、{{1}: "x"}都抛TypeError: unhashable type。元组只有在所有元素都可哈希时才能当键:hash((1, [2]))一样报错。改用tuple、frozenset或把列表序列化成字符串。
坑 5:
1、1.0、True会撞成同一个键因为
hash(1) == hash(1.0) == hash(True)且它们相等,字典里只会有一个键。用浮点数当键还额外有精度风险(0.1 + 0.2 != 0.3),需要精确键就用Decimal或字符串。
坑 6:
{}是空字典,不是空集合空集合要写
set()。另外frozenset()才是可哈希的不可变集合,set不能作为另一个集合的元素。
坑 7:
dict.fromkeys(seq, [])让所有键共享同一个默认值
d = dict.fromkeys("abc", [])中三个键指向同一个列表,d["a"].append(1)后三个键都有[1]。正确写法是{k: [] for k in "abc"}。
坑 8:
zip默认按最短截断,会静默丢数据
zip([1, 2, 3], "ab")只有两对。处理"两个本应等长的列表"时用zip(..., strict=True)(3.10+),让长度不一致直接暴露为ValueError。
坑 9:边遍历边修改列表
for x in lst: lst.remove(x)会跳过元素甚至得到错误结果,因为迭代器按下标前进而列表在缩短。正确做法是遍历副本(for x in lst[:])或构造新列表(lst = [x for x in lst if 条件])。
坑 10:
x in list是 ,循环里嵌套用会变成常见错误写法:
for x in a: if x in b:——两个大列表就是平方级。把b提前转成set/dict,整体降到 。复杂度推导见 算法-复杂度分析。
坑 11:生成器表达式只能消费一次
gen = (x for x in data),sum(gen)之后list(gen)是空列表,调试点常在这里卡住。需要多次遍历就物化成list;只遍历一次又想省内存才用生成器。
坑 12:排序要求键之间可比较
sorted([1, "a"])抛TypeError;sorted([3.3, float("nan"), 1.1])的结果不可靠(NaN 与任何值比较都是 False)。混类型先统一成字符串,NaN/None 先过滤掉。
实践建议
1. 用
key=而不是cmp_to_key:key函数每个元素只调用一次( 次),比较函数每次比较都调用( 次)。2. 大列表查找前先转
set;需要"有序 + 二分查找"时用bisect模块而不是手写二分。3. 数据类记录优先用
namedtuple/dataclass,比裸dict更难写错字段名。4. 需要队列用
collections.deque,不要用list.pop(0)()。
六、练习题
- 基础题:给定
nums = [5, 3, 8, 3, 9, 1],用一行代码得到"去重且保持首次出现顺序"的列表,再用一行得到"去重并升序"的列表,并说明两者差别来自哪里。
- 基础题:有一个二维列表
grid = [[0] 3] 2,解释为什么grid[0][0] = 1会让两行都变成[1, 0, 0],并写出正确的初始化方式。
- 进阶题:给定学生列表
students = [("Ada", "A", 15), ("Bob", "B", 12), ("Cyd", "B", 10)](姓名、班级、年龄),分别用 ①元组键、②两趟稳定排序 实现"班级升序、年龄降序",比较两种写法在可读性与扩展性上的取舍。
- 进阶题:写一个函数
invert_index(docs: dict[str, list[str]]) -> dict[str, list[str]],把"文档 → 关键词列表"变成"关键词 → 文档列表",要求结果里每个关键词对应的文档列表有序且不重复;再说明为什么这个函数里不该用dict.fromkeys(docs, [])。
- 思考题:为什么 Python 的字典在 3.7 之后才把"插入顺序"写进语言规范,而实现上 3.6 就已经有序?这种"实现先行、规范后追"的演进方式对使用者意味着什么?如果你要写一个必须在 3.5 上运行的库,代码要怎么改?
七、常见问题(FAQ)
Q1:什么时候用列表,什么时候用元组?
A:看语义而不是看性能。同质的、会增删的集合用 list([1, 2, 3]、查询结果集);异质的、固定不变的记录用 tuple/namedtuple((host, port)、坐标、函数多返回值)。元组额外的好处是可哈希(能当键)与更省内存,但不要为了省一点点内存把需要修改的数据塞进元组。
Q2:为什么我的字典键"看起来有两个"其实只有一个?
A:检查键之间是否 == 且哈希相同。典型来源:1 / 1.0 / True 撞键;自定义类没有按"值语义"实现 __eq__ 与 __hash__(默认用身份,两个内容相同的对象是两个键);用浮点或 Decimal 混合作键。排查手段:len(d) 与 list(d.keys()) 对照,或打印 [(k, hash(k)) for k in keys]。
Q3:浅拷贝到底拷了什么?为什么我改了副本原数据也变了?
A:只新建了最外层容器,元素仍是指向原对象的引用。所以"改副本的元素本身"(b[0] = 9)不影响原列表;但"改副本里嵌套的可变对象"(b[0].append(9))会影响原列表。需要完全独立就 copy.deepcopy,或者干脆用不可变数据(元组、frozenset、字符串)来消灭共享可变状态。
Q4:推导式和 for 循环哪个快?为什么?
A:推导式通常更快。原因有二:① 循环体在字节码层面是专门的 LIST_APPEND 指令,省掉了每轮一次 list.append 属性查找与函数调用;② 没有 Python 层的名字查找开销。但差距通常在常数倍以内,可读性优先:逻辑超过两层嵌套或带复杂 if/else 时就该退回普通 for 循环。生成器表达式在"数据量大且只需遍历一次"时不仅省内存,还常常更快(不需要构造整个列表)。
相关笔记
- Python-01-环境与基础语法 —— 变量绑定、数字与字符串基础、真值测试
- Python-03-函数与模块 —— 函数、闭包、模块;
zip/enumerate/map等内置函数的配合 - Python-06-常用标准库 ——
collections、itertools、bisect的进阶容器与工具 - Python-04-面向对象 ——
dataclass、自定义__eq__/__hash__与可变记录 - 算法-排序 —— Timsort、稳定性与比较排序的复杂度下界
- 数据结构-哈希表 —— 哈希函数、冲突解决、装载因子与 的代价
- 算法-复杂度分析 —— 、、 的推导与均摊分析
- 00-索引 —— 返回全库导航
参考来源
- 官方教程:数据结构(列表、元组、字典、集合、推导式):<https://docs.python.org/3/tutorial/datastructures.html>
- 内置类型与全部方法(
list、dict、set、str等):<https://docs.python.org/3/library/stdtypes.html> collections(namedtuple、defaultdict、Counter、OrderedDict、deque):<https://docs.python.org/3/library/collections.html>copy模块(浅拷贝/深拷贝、memo、__deepcopy__):<https://docs.python.org/3/library/copy.html>- Sorting Techniques(
key、稳定性、多趟排序、DSU、cmp_to_key):<https://docs.python.org/3/howto/sorting.html> - 内置函数(
sorted、zip、enumerate、reversed、sum、any、all):<https://docs.python.org/3/library/functions.html> operator(itemgetter、attrgetter):<https://docs.python.org/3/library/operator.html>- 数据模型(
__hash__、__eq__、可哈希的定义):<https://docs.python.org/3/reference/datamodel.html> - Python 3.7 新特性(字典顺序成为语言保证):<https://docs.python.org/3/whatsnew/3.7.html>
- PEP 202 List Comprehensions:<https://peps.python.org/pep-0202/>
- PEP 274 Dict Comprehensions:<https://peps.python.org/pep-0274/>
- PEP 289 Generator Expressions:<https://peps.python.org/pep-0289/>
- PEP 448 Additional Unpacking Generalizations(更灵活的解包):<https://peps.python.org/pep-0448/>
- PEP 584 Add Union Operators To dict(
|与|=,3.9+):<https://peps.python.org/pep-0584/> - Python Wiki: TimeComplexity(各结构操作复杂度总表):<https://wiki.python.org/moin/TimeComplexity>
- 说明:复杂度数字来自官方文档与 CPython 实现(如字典装载因子、列表扩容倍数属实现细节,可能随版本变化),以官方最新文档为准。