Python两种多键排序实现的效率差异原因求解

首先可以确认两种排序方案逻辑完全等价：Python内置排序为稳定排序，先按次关键字排序、再按主关键字排序的结果，和一次性返回(主关键字, 次关键字)元组作为key的排序结果完全一致。

性能差异的核心原因来自三个方面：

• Timsort的有序性优化红利：Python内置排序采用Timsort算法，专门针对存在局部有序特征的序列做了极致优化。多趟排序方案中，第一趟按次关键字排序后得到的序列已经具备局部有序性，第二趟按主关键字排序时，Timsort可以直接利用该有序特征，大幅减少排序过程中的比较、元素移动次数，排序本身的开销远低于单趟处理完全乱序的原始列表。
• 比较操作的开销差异：
  • 多趟排序的两次排序过程，比较操作均为直接对比单个字符串：第一趟对比的是次关键字x[::2]的短字符串切片，单次比较开销极低；第二趟对比主关键字字符串，也没有额外开销。
  • 单趟多键排序的比较操作需要对比二元组，哪怕绝大多数场景下仅需对比元组第一个元素（主关键字）就能得到结果，元组比较本身也比直接对比单个字符串多了类型检查、元素索引的额外开销，当数据量级达到千万级时，这部分开销会被显著放大。
• 内存与缓存命中率差异：Python排序内部会采用施瓦茨变换，预计算所有元素的key并存储为临时序列后再排序。单趟排序需要存储千万级别的二元组，相比多趟排序两次分别存储单个字符串的临时序列，内存占用高出不少，会导致CPU缓存命中率下降，进一步拖慢执行速度。

补充说明：该性能差异仅符合当前测试场景的特征（次关键字计算成本远低于主关键字、排序后序列可被Timsort有效优化）。如果两个key的计算成本都很高，或是主关键字的重复率极低，两种方案的性能差距会缩小甚至反转——毕竟多趟排序需要执行两次完整的排序流程，本身也有额外开销。

测试代码 #

import random
from time import time

largest = 1000000
length = 10000000
start = time()
lst = [str(x) for x in random.choices(range(largest), k=length)]
t0 = time() - start

start = time()
tmp = sorted(lst, key=lambda x: x[::2])
l1 = sorted(tmp, key=lambda x: ''.join(sorted(x)))
t1 = time() - start

start = time()
l2 = sorted(lst, key=lambda x: (''.join(sorted(x)), x[::2]))
t2 = time() - start

print(f'prepare={t0} multisort={t1} multikey={t2} slowdown={t2/t1}')

assert l1 == l2

内容的提问来源于stack exchange，提问作者o17t H1H' S'k