python之CPython 中的字符串排序是如何优化的_编程设计

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

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 中不能那样工作？

请您参考如下方法:

由于 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))

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