CPython 中的字符串排序是如何优化的？

Question

我有这个故意不高效的代码：

def suffix_array_alternative_naive(s):
    return [rank for suffix, rank in sorted((s[i:], i) for i in range(len(s)))]

from random import randint

constant_string = lambda length: 'a' * length
random_string = lambda length: ''.join(chr(randint(0, 255)) for _ in range(length))

length = 10000
s1 = constant_string(length)
s2 = random_string(length)

from time import time

for s in [s1, s2]:
    d = time()
    for _ in range(10):
        suffix_array_alternative_naive(s)
    print(time()-d)

使用 pypy3： 2.0367980003356934 1.9366297721862793
和python3： 0.48073387145996094 0.5416769981384277 如果我尝试使用 length = 100000 和一个循环：
pypy3: 48.4867467880249 35.002175092697144
Python3 4.402702808380127 4.469300031661987

通常情况下，常量字符串应该比较长，因为您必须完整地阅读它们，而随机字符串应该很容易避免后缀前缀之间的冲突。因此，pypy3的结果是合乎逻辑的。

为什么它在 CPython 中不能那样工作？

Answer 1

由于 Python 中字符串的内部格式，您的“常量”字符串比随机字符串小。

>>> sys.getsizeof('\x7f')
50
>>> sys.getsizeof('\x80')
74

CPython 使用优化来存储 ASCII 字符串比非 ASCII 字符串更紧凑。要避免这种差异，请使用 randint(0, 127)，这将生成纯 ASCII 常量字符串。或者使用非 ASCII 字符代替 'a'.

最重要的是，常量字符串已经排序。 CPython 的排序算法是 Timsort，它以针对某些情况进行优化而闻名，例如已排序或反向排序的输入。

import random
import timeit

def constant_string(length):
    return 'a' * length
def random_string(length):
    return ''.join(chr(random.randint(0, 127)) for _ in range(length))

length = 10000
s1 = constant_string(length)
s2 = random_string(length)

for s in [s1, s2]:
    def test():
        arr = [s[i:] for i in range(len(s))]
        random.shuffle(arr)
        arr.sort()
    print(timeit.timeit(test, number=100))

在我的计算机上，常量字符串测试大约需要两倍的时间，因为这两个版本都对包含相同大小值的随机数组进行排序。

CPython 中的字符串排序是如何优化的？

How is the string sort optimised in CPython?

python

cpython