为何Python内置sorted()处理元素连续重复两次的降序列表时速度更慢？

问题描述 #

对四个结构相似的列表执行排序操作后，发现列表d的排序耗时远高于其他三个列表，其余列表耗时基本一致：

a:  33.5 ms
b:  33.4 ms
c:  36.4 ms
d: 110.9 ms

测试脚本：

from timeit import repeat

n = 2_000_000
a = [i // 1 for i in range(n)]  # [0, 1, 2, 3, ..., 1_999_999]
b = [i // 2 for i in range(n)]  # [0, 0, 1, 1, 2, 2, ..., 999_999]
c = a[::-1]                     # [1_999_999, ..., 3, 2, 1, 0]
d = b[::-1]                     # [999_999, ..., 2, 2, 1, 1, 0, 0]

for name in 'abcd':
    lst = globals()[name]
    time = min(repeat(lambda: sorted(lst), number=1))
    print(f'{name}: {time*1e3 :5.1f} ms')

原因解析 #

Python内置的sorted()函数使用Timsort算法，它的核心优化是利用数据中已有的有序子序列（称为run）：如果数据中的run数量少、长度长，排序效率就越高；反之，大量短run会导致频繁的归并操作，大幅增加耗时。

逐个分析四个列表的结构及Timsort的处理逻辑：

• 列表a：严格升序的序列，Timsort会直接识别为一个长度为200万的完整run，排序仅需复制序列，耗时最低。
• 列表b：非降序的重复元素序列（[0,0,1,1,...]），整体属于一个完整的非降序run，同样只需复制序列，耗时与a基本一致。
• 列表c：严格降序的序列，Timsort会检测到这是一个严格递减的run，将其反转成升序序列后完成排序，仅多了一步反转操作，所以耗时略高于a和b。
• 列表d：结构为降序排列的重复元素对（[999999,999999,999998,999998,...]），Timsort无法将其识别为单个大run：
  它会被拆分成100万个长度为2的非降序小run（每个重复元素对为一个run），且每个run的末尾元素都小于前一个run的起始元素。
  Timsort需要对这100万个小run进行多次归并操作，每次归并都要进行元素比较和数据复制，这就是导致d排序耗时远超其他列表的核心原因。

内容的提问来源于stack exchange，提问作者no comment