如何在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))

在我的计算机上,常量字符串测试需要大约两倍的时间,因为两个版本都在排序包含相同大小值的混洗数组.