sorted 的 key 每个元素只算一次:一千个元素恰好调用一千次
一个担心的性能问题
代码里有个排序,key 函数不便宜,要查一次映射。有人担心排序过程中会反复调用它,比较次数一多就吃不消,提议先手工把 key 算好缓存起来。到底比较时会不会重复算,测一下次数就清楚,比争论强。
一千个元素,key 调了多少次
calls = [0]
def key(x):
calls[0] += 1
return x % 10
data = list(range(1000))
r = sorted(data, key=key)
print("n =", len(data))
print("key_calls =", calls[0])
lst = [3, 1, 2]
ret = lst.sort()
print("sort return:", ret)
print("list after:", lst)
输出:
n = 1000
key_calls = 1000
sort return: None
list after: [1, 2, 3]
一千个元素,key 恰好被调用一千次,一次不多。这直接打消了开头的顾虑:比较阶段并不会重新计算 key。
底层用的是 Schwartz 变换
sorted 在做比较之前,会先为每个元素算一次 key,把结果写进一个与元素平行的数组,之后所有比较只读那个数组,压根不碰元素本身。实测拿一个定义了 __lt__ 的类排序,给了 key 之后 __lt__ 一次都没被调用。这个手法常被叫做装饰、排序、去装饰,也就是 Schwartzian transform(施瓦茨变换),但 CPython 的实现不是真的把元素和 key 配成元组,而是两条平行数组。
所以 key 的调用次数严格等于元素个数,跟比较次数无关。一千个元素排下来内部比较了六千多次,key 也只跑了一千遍。这也是为什么官方文档会说,key 函数应该尽量简单,因为它对每个元素只跑一次,但排序规模大时总量仍可观。
别自己提前缓存,除非有别的用处
既然标准库已经帮我们算一遍并缓存了,再手工建一个 key 到元素的映射,属于重复劳动,还多占内存;而且 {x % 10: x for x in range(1000)} 这种写法只有 10 项,key 一重复元素就被覆盖了。真要预计算,存成元素到 key 的列表或 (key, 元素) 列表,别用字典。只有当同一个 key 在别处也要用、或者算 key 的代价高到需要跨多次排序复用时,预先算才有意义。单次排序,交给 sorted 就行。
要留心的是 key 里的副作用。既然每个元素只调一次,如果 key 函数偷偷改了全局状态、或者依赖会变化的值,结果就和调用次数绑死了。key 应当是个纯函数,给同样的输入总返回同样的键,排序过程才 reproducible。
sort 返回 None 这件事
另一半输出也值得记住:lst.sort() 返回的是 None,不是排好序的列表。它是原地排序,直接改动原对象。新手常写出 b = a.sort() 然后对着 None 发懵,或者把 sort 的返回值接着往下传,结果全乱。
要保留原列表、拿到一个新列表,用 sorted;要原地改、不介意原顺序丢失,用 sort。两者别混。这个约定是有意为之的,返回 None 就是在提醒你它改的是自己,别指望拿到新东西。
一次实测省了半天争论
这类问题不需要翻源码也不需要争,加个计数器跑一遍,调用次数和返回值当场就摆出来了。key 每元素一次、sort 原地返回 None,两条都是实测确认的。
我现在的习惯是:涉及标准库内部行为的猜测,先写个十行的小测量,用数字替代印象,往往比读半天讨论帖更快也更可信。
- 点赞
- 收藏
- 关注作者
评论(0)