Python 排序完全指南:基于 KBEngine 内置 Python 3.7 源码的 sorting HOW TO 深度解读

原创2026-10-15 19:32:582,287 阅读
文章标签:游戏开发后端

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)三步曲:

  1. 装饰:给原始列表的每个元素附加控制排序顺序的新值;
  2. 排序:对装饰后的列表排序;
  3. 去装饰:移除装饰,还原出按新顺序排列的原始值列表。

例如按 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 服务器脚本开发中最常用的数据处理能力之一。

登录后查看全文
kbengine