Python 排序完全指南:基于 KBEngine 内置 Python 3.7 源码的 sorting HOW TO 深度解读
Python 排序完全指南:基于 KBEngine 内置 Python 3.7 源码的 sorting HOW TO 深度解读
导读
本文以 kbe/src/lib/python/Doc/howto/sorting.rst 这份官方 Sorting HOW TO 文档为主线,结合 KBEngine 仓库内嵌的 CPython 3.7.3 源码(listobject.c、bltinmodule.c、operator.py、functools.py),系统讲解 Python 排序的完整知识体系:从 sorted() 与 list.sort() 的基础用法,到 key 函数、operator 模块、降序排序、稳定排序与 Timsort 原理、旧式 DSU 与 cmp 参数迁移,再到本地化排序等技巧。读完本文,你将掌握在 KBEngine 的 Python 脚本层(实体逻辑、WebConsole 管理界面等)写出正确、高效、可维护排序代码的全部必备技能。
排序基础:sorted() 与 list.sort() 的取舍
Python 的排序入口有两个:内置函数 sorted() 和列表方法 list.sort()。前者接受任意可迭代对象并返回一个新列表,后者原地修改列表且返回 None(避免调用者误以为返回了新列表)。
>>> sorted([5, 2, 3, 1, 4])
[1, 2, 3, 4, 5]
>>> a = [5, 2, 3, 1, 4]
>>> a.sort()
>>> a
[1, 2, 3, 4, 5]
两者还有一个关键差异:list.sort() 只在列表上定义,而 sorted() 接受任何可迭代对象——包括字典、集合、生成器等:
>>> sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'})
[1, 2, 3, 4, 5]
从源码看,sorted() 的实现非常轻量:在 bltinmodule.c 中,它先用 PySequence_List(seq) 把可迭代对象物化为列表,然后取出该列表的 sort 属性,把 key、reverse 等关键字参数原样转发给 list.sort()。换句话说,sorted() 本质上是“先建列表、再调 list.sort()”的语法糖。
选用建议:如果你不再需要原始列表,直接使用 list.sort() 能省下一次列表拷贝;否则用 sorted() 更安全、更符合函数式风格。在 KBEngine 的 WebConsole 管理代码中,就有直接调用 .sort() 原地排序的实例(见下文“KBEngine 中的实际应用”)。
Key Functions:让排序摆脱“裸比较”
list.sort() 和 sorted() 都接受 key 参数,它指定一个函数,该函数会在比较之前对每个元素调用一次,返回用于排序的“键值”。
大小写不敏感的字符串排序是最经典的例子:
>>> sorted("This is a test string from Andrew".split(), key=str.lower)
['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']
key 参数应当是一个“接收单个参数、返回排序键”的函数。这套机制很快,因为每个元素只调用一次 key 函数(而不是像 cmp 时代那样在每次比较时重复调用)。
用 lambda 按下标或属性排序
对元组列表,常用下标索引作为键:
>>> student_tuples = [
... ('john', 'A', 15),
... ('jane', 'B', 12),
... ('dave', 'B', 10),
... ]
>>> sorted(student_tuples, key=lambda student: student[2]) # 按年龄排序
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
对带命名属性的对象,则用属性访问:
>>> class Student:
... def __init__(self, name, grade, age):
... self.name = name
... self.grade = grade
... self.age = age
... def __repr__(self):
... return repr((self.name, self.grade, self.age))
>>> student_objects = [
... Student('john', 'A', 15),
... Student('jane', 'B', 12),
... Student('dave', 'B', 10),
... ]
>>> sorted(student_objects, key=lambda student: student.age) # 按年龄排序
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
源码印证:key 函数确实只调用一次
“每个元素只调用一次 key 函数”不是文档中的空洞承诺,而是写死在排序实现里的。在 listobject.c 的 list_sort_impl 中,当 keyfunc 非空时,先分配一个与列表等长的 keys 数组,然后通过一个循环对每个元素调用一次 key 函数并把结果缓存起来:
for (i = 0; i < saved_ob_size ; i++) {
keys[i] = PyObject_CallFunctionObjArgs(keyfunc, saved_ob_item[i], NULL);
...
}
之后整个排序过程只比较 keys 数组中的键值,原始元素不再参与比较。这就是 key 方案在时间复杂度上优于 cmp 方案的根源——比较次数依旧,但 key 函数的调用次数被压缩到 O(n)。
operator 模块:把“取键”封装成高效可复用对象
key=lambda student: student[2] 这种模式太常见了,因此标准库 operator.py 提供了三个现成的访问器工厂:itemgetter、attrgetter 和 methodcaller,它们比手写 lambda 更快(无需反复构造闭包与执行 Python 级调用),代码也更简洁:
>>> from operator import itemgetter, attrgetter
>>> sorted(student_tuples, key=itemgetter(2))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
>>> sorted(student_objects, key=attrgetter('age'))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
从 operator.py 的实现看,itemgetter 是一个带 __call__ 的类:传入单个下标时返回 obj<a href="https://link.gitcode.com/i/287b13c02cf8a377cdf9fac95eba26a1" target="_blank">item],传入多个下标时返回元组 tuple(obj[i] for i in items)。attrgetter([operator.py)则支持点分路径如 'name.first'。methodcaller(operator.py)用于调用对象的方法并支持携带参数。
多级排序:一个 key 搞定主次关键字
operator 模块的函数天然支持多字段排序。例如先按 grade、再按 age 排序:
>>> sorted(student_tuples, key=itemgetter(1, 2))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]
>>> sorted(student_objects, key=attrgetter('grade', 'age'))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]
这里 itemgetter(1, 2) 返回形如 (grade, age) 的元组,而元组天然按字典序比较:先比第一个元素,相同再比第二个,依次类推。同理,attrgetter('grade', 'age') 返回 (student.grade, student.age)。
升序与降序:reverse 参数
list.sort() 和 sorted() 都接受布尔型 reverse 参数,用于标记降序排序。比如按年龄降序排列学生数据:
>>> sorted(student_tuples, key=itemgetter(2), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
>>> sorted(student_objects, key=attrgetter('age'), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
值得注意的实现细节:在 listobject.c 中,降序排序并不是“比较时取反”,而是先把待排序的数据切片整体反转,做一次稳定的升序排序,最后再把结果反转回来。注释明确写道:
/* Reverse sort stability achieved by initially reversing the list,
applying a stable forward sort, then reversing the final result. */
这种“先反转、排序、再反转”的做法正是为了在降序时也能保持排序稳定性(见下一节)。
排序稳定性与复杂排序:Timsort 的用武之地
Python 的排序被保证是稳定的(stable):当多个记录拥有相同的 key 时,它们在排序后的相对顺序与原始顺序一致。
>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
>>> sorted(data, key=itemgetter(0))
[('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]
注意两条 blue 记录保持了原有顺序,('blue', 1) 必定排在 ('blue', 2) 之前。
用“多趟稳定排序”实现复合排序
稳定排序这一特性让你可以通过一系列排序步骤构造复杂排序:要想“按 grade 降序、再按 age 升序”,就先按次要键 age 升序排一遍,再按主键 grade 降序排一遍:
>>> s = sorted(student_objects, key=attrgetter('age')) # 先按次要键排序
>>> sorted(s, key=attrgetter('grade'), reverse=True) # 再按主键降序排序
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
因为第一趟已经把相同 grade 内部按 age 排好了,第二趟稳定排序时相同 grade 的相对顺序不会被破坏,最终结果自然就是“grade 降序 + age 升序”。
Timsort:能“吃老本”的自适应排序算法
Python 使用的排序算法是 Timsort。它之所以能把多趟排序做得高效,是因为它能够利用数据集中已经存在的任何顺序性——比如刚刚被上一趟排序排好的部分。
在 listobject.c 中可以看到 Timsort 的核心流程:
merge_compute_minrun(nremaining)计算最小 run 长度;count_run从左到右扫描,识别出数据中已经有序(升序或降序)的自然 run;- 对长度不足
minrun的 run 用binarysort(二分插入排序,listobject.c,注释称其为“排序小数组的最佳方法”)补齐; - 把每个 run 压入
pending栈,并通过merge_collapse决定何时合并相邻 run; - 合并时采用 galloping(奔袭)模式(
gallop_left/gallop_right,listobject.c),配合min_gallop动态调节阈值,避免在“一方持续占优”的合并中做无谓比较。
对于接近有序的数据,Timsort 几乎只做识别 run 和合并,接近 O(n);而对已排序过的数据做二次排序时,上一趟留下的顺序性会被直接当作 run 利用,这就是“多趟排序依然很快”的底层原因。
旧式写法(一):Decorate-Sort-Undecorate(DSU)
在 key 函数普及之前,Python 程序员常用“装饰—排序—去装饰”(Decorate-Sort-Undecorate)三步曲:
- 装饰:给原始列表的每个元素附加控制排序顺序的新值;
- 排序:对装饰后的列表排序;
- 去装饰:移除装饰,还原出按新顺序排列的原始值列表。
例如按 grade 排序:
>>> decorated = [(student.grade, i, student) for i, student in enumerate(student_objects)]
>>> decorated.sort()
>>> [student for grade, i, student in decorated] # undecorate
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
这个惯用法之所以可行,是因为元组按字典序比较:先比第一个元素,相同再比第二个,以此类推。
装饰元组中的索引 i 并非在所有情况下都必要,但加上它有两个好处:
- 排序稳定:两个元素 key 相同时,索引保证它们的相对顺序在排序后得以保留;
- 原始元素不必可比较:装饰元组的顺序最多由前两项决定,因此原始列表甚至可以包含无法直接排序的元素(如复数)。
这个惯用法还有另一个广为人知的名字:Schwartzian transform(施瓦茨变换),得名于在 Perl 程序员中推广它的 Randal L. Schwartz。在 Python 提供 key 函数之后,这一技术已经很少需要了——但它仍然是理解排序演进史和理解 Perl/旧代码的关键。
旧式写法(二):cmp 参数与 cmp_to_key 迁移
本 HOWTO 中大量构造都假定 Python 2.4 或更高版本。在此之前,既没有 sorted() 内置函数,list.sort() 也不接受关键字参数;所有 Py2.x 版本都通过 cmp 参数接受用户自定义的比较函数。
到了 Py3.0,cmp 参数被彻底移除——这是语言“简化与统一”工程的一部分,用于消除富比较(rich comparison)与 __cmp__ 魔术方法之间的冲突。
Py2.x 时代,sort 允许传入一个比较函数,它接收两个参数,返回负数表示“小于”、零表示“等于”、正数表示“大于”:
>>> def numeric_compare(x, y):
... return x - y
>>> sorted([5, 2, 4, 1, 3], cmp=numeric_compare) # doctest: +SKIP
[1, 2, 3, 4, 5]
交换比较顺序即可实现降序:
>>> def reverse_numeric(x, y):
... return y - x
>>> sorted([5, 2, 4, 1, 3], cmp=reverse_numeric) # doctest: +SKIP
[5, 4, 3, 2, 1]
从 cmp 迁移到 key:cmp_to_key 包装器
从 Python 2.x 移植到 3.x 时,经常遇到“用户提供比较函数、而新 API 需要 key 函数”的情况。下面这个包装器可以轻松完成转换(也是标准库 functools.cmp_to_key 的原始实现思路):
def cmp_to_key(mycmp):
'Convert a cmp= function into a key= function'
class K:
def __init__(self, obj, *args):
self.obj = obj
def __lt__(self, other):
return mycmp(self.obj, other.obj) < 0
def __gt__(self, other):
return mycmp(self.obj, other.obj) > 0
def __eq__(self, other):
return mycmp(self.obj, other.obj) == 0
def __le__(self, other):
return mycmp(self.obj, other.obj) <= 0
def __ge__(self, other):
return mycmp(self.obj, other.obj) >= 0
def __ne__(self, other):
return mycmp(self.obj, other.obj) != 0
return K
使用方式:把旧的比较函数包一层即可作为 key 使用:
>>> from functools import cmp_to_key
>>> sorted([5, 2, 4, 1, 3], key=cmp_to_key(reverse_numeric))
[5, 4, 3, 2, 1]
Python 3.2 起,functools.cmp_to_key 正式加入标准库。在 KBEngine 内置的 Python 3.7.3 中,它的实现位于 functools.py:内部定义了一个带 __slots__ = ['obj'] 的 K 类,把所有富比较方法转发给原始 mycmp,并显式把 __hash__ 设为 None(比较语义对象不应参与哈希);随后尝试从 C 扩展 _functools 导入加速版本,失败时回退到纯 Python 实现。
杂项技巧(Odd and Ends)
本地化感知排序
需要按地区(locale)规则排序字符串时:
- 用
locale.strxfrm作为 key 函数(先把字符串转换成适合比较的形式); - 或用
locale.strcoll作为比较函数。
import locale
# key 方案(推荐)
sorted(names, key=locale.strxfrm)
reverse=True 与双重 reversed() 等价
reverse 参数依然维持排序稳定性(key 相等的记录保持原始顺序)。有趣的是,这个效果可以不用 reverse 参数、仅靠内置 reversed() 函数模拟出来——先反转、排序、再反转:
>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
>>> standard_way = sorted(data, key=itemgetter(0), reverse=True)
>>> double_reversed = list(reversed(sorted(reversed(data), key=itemgetter(0))))
>>> assert standard_way == double_reversed
>>> standard_way
[('red', 1), ('red', 2), ('blue', 1), ('blue', 2)]
这正是 listobject.c 中降序排序实现方式的 Python 层等价物。
用 __lt__ 给类注入默认排序规则
排序例程保证在比较两个对象时只使用 __lt__。因此,给类定义一个 __lt__ 方法即可获得标准排序顺序,无需为每次排序编写 key 函数:
>>> Student.__lt__ = lambda self, other: self.age < other.age
>>> sorted(student_objects)
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
key 函数不一定要依赖被排序对象本身
key 函数可以访问外部资源。例如,学生的成绩存在字典里,用它来对一个独立的姓名列表排序:
>>> students = ['dave', 'john', 'jane']
>>> newgrades = {'john': 'F', 'jane': 'A', 'dave': 'C'}
>>> sorted(students, key=newgrades.__getitem__)
['jane', 'dave', 'john']
这里 newgrades.__getitem__ 就是“取该姓名对应的成绩”的 key 函数,排序结果按成绩 A < C < F 排列。
KBEngine 中的应用场景
这份 Sorting HOW TO 随 KBEngine 仓库的 Python 运行时一同分发,位于 kbe/src/lib/python/Doc/howto/,并被 howto/index.rst 收录为官方教程之一;functional.rst 在讲解函数式编程时也直接引用了本文档(:ref:sortinghowto``)。
内置 Python 版本确认
KBEngine 嵌入的 Python 解释器版本为 3.7.3,见 Include/patchlevel.h 中的宏定义:
#define PY_MAJOR_VERSION 3
#define PY_MINOR_VERSION 7
#define PY_MICRO_VERSION 3
#define PY_VERSION "3.7.3"
这意味着本文所述的所有现代 API(sorted、key、operator、functools.cmp_to_key)在该环境中均可直接使用;而 cmp 参数、__cmp__ 魔术方法等 Py2 时代产物则已不可用,迁移时务必按上文“cmp 参数与 cmp_to_key 迁移”一节处理。
WebConsole 中的真实排序代码
KBEngine 的 WebConsole(Web 管理控制台)在展示集群机器列表时就用到了本节知识。在 kbe/tools/server/webconsole/WebConsole/views.py 中,查询到的机器信息先按 IP 地址原地排序,再交给模板渲染:
kbeMachines = machinesmgr.queryMachines()
kbeMachines.sort(key = lambda info: info.intaddr)
这里的 key=lambda info: info.intaddr 正是对“按对象某个属性排序”这一 key 函数模式的直接实践——如果后续需要按多个维度(如机器负载、组件数量)排序,换成 itemgetter/attrgetter 或组合多趟稳定排序即可,原理全部来自本文。
速查总结
| 需求 | 推荐写法 |
|---|---|
| 升序排序、保留原列表 | sorted(iterable) |
| 升序排序、原地修改 | list.sort() |
| 忽略大小写排序 | key=str.lower |
| 按元组下标排序 | key=itemgetter(i) |
| 按对象属性排序 | key=attrgetter('attr') |
| 多字段排序(如 grade 再 age) | key=itemgetter(1, 2) 或 key=attrgetter('grade', 'age') |
| 降序排序 | reverse=True |
| 复合排序(主键降序 + 次键升序) | 先按次键升序排,再按主键 reverse=True 排(利用稳定性) |
| 旧比较函数迁移 | key=functools.cmp_to_key(mycmp) |
| 本地化排序 | key=locale.strxfrm 或 locale.strcoll |
理解 key 函数“每元素只调用一次”的性能本质(listobject.c)、Timsort 的 run 识别与 galloping 合并机制(listobject.c),以及稳定排序对多趟复合排序的支撑,是写出高性能、可维护 Python 排序代码的关键——这也是 KBEngine 服务器脚本开发中最常用的数据处理能力之一。