sorted 的 key 每个元素只算一次:一千个元素恰好调用一千次

举报
yd_232353574 发表于 2026/11/18 08:19:39 2026/11/18
【摘要】 在本机 CPython 3.10.11 / win32 实测:对一千个元素的列表用 key 函数排序,key 恰好被调用一千次,一次不多——排序底层先做 Schwartzian transform(施瓦茨变换),为每个元素算一次 key 后缓存,比较阶段只读不重算,所以调用次数严格等于元素个数、与比较次数无关;另外 list.sort() 是原地排序、返回 None,想拿新列表得用 sorted。

一个担心的性能问题

代码里有个排序,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,两条都是实测确认的。

我现在的习惯是:涉及标准库内部行为的猜测,先写个十行的小测量,用数字替代印象,往往比读半天讨论帖更快也更可信。

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0)

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。