python - 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))

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