字符串切片的时间复杂度

Question

切片 Python 字符串的时间复杂度是多少？鉴于 Python 字符串是不可变的，我可以想象将它们切片为 O(1) 或 O(n) 取决于切片的实现方式。

我需要编写一个函数来遍历（可能很大）字符串的所有后缀。我可以通过将后缀表示为整个字符串的元组加上开始读取字符的索引来避免对字符串进行切片，但这很丑陋。相反，如果我像这样天真地编写我的函数：

 def do_something_on_all_suffixes(big_string):
    for i in range(len(big_string)):
        suffix = big_string[i:]
        some_constant_time_operation(suffix)

… will its time complexity be O(n) or O(n2) , where n is len(big_string) ?

原文由 Mark Amery 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

简短回答： str 切片，一般来说，复制。这意味着为每个字符串的 n 后缀做切片的函数正在做 O(n2) 工作。也就是说，如果您可以使用 bytes 对象使用 memoryview 来获得原始字节数据的零拷贝视图，则 可以避免复制。请参阅下面的如何进行 零拷贝切片 以了解其工作原理。

长答案：©Python str 不要通过引用数据子集的视图来切片。 str 切片恰好有三种操作模式：

1. Complete slice, eg mystr[:] : Returns a reference to the exact same str (not just shared data, the same actual object, mystr is mystr[:] since str 是不可变的，所以这样做没有风险）
2. 零长度切片和（取决于实现）缓存长度为 1 的切片；空字符串是一个单例 ( mystr[1:1] is mystr[2:2] is '' )，长度为 1 的低序数字符串也是缓存的单例（在 CPython 3.5.0 上，它看起来像所有字符都可以在 latin-1 中表示，即 Unicode 序数在 range(256) 中，被缓存）
3. 所有其他切片：切片 str 在创建时复制，此后与原始切片无关 str

#3 是一般规则的原因是为了避免大 str 的一小部分视图保存在内存中的问题。如果你有一个 1GB 的文件，读入它并像这样切片（是的，当你可以搜索时它很浪费，这是为了说明）：

 with open(myfile) as f:
    data = f.read()[-1024:]

那么您将有 1 GB 的数据保存在内存中以支持显示最后 1 KB 的视图，这是一种严重的浪费。由于切片通常很小，因此在切片上复制几乎总是比创建视图更快。这也意味着 str 可以更简单；它需要知道它的大小，但它也不需要跟踪数据的偏移量。

如何进行零拷贝切片

有 多种方法可以在 Python 中执行基于视图的切片，在 Python 2 中，它将在 str 上工作（因为 str 在 Python 2 中类似于字节，支持 缓冲协议）。 With Py2 str and Py3 bytes (as well as many other data types like bytearray , array.array , numpy 数组， mmap.mmap s等），你可以创建一个 memoryview 原始对象的零拷贝视图，并且可以在不复制数据的情况下进行切片。因此，如果您可以使用（或编码）Py2 str /Py3 bytes ，并且您的函数可以使用任意 bytes 对象，那么您可以做:

 def do_something_on_all_suffixes(big_string):
    # In Py3, may need to encode as latin-1 or the like
    remaining_suffix = memoryview(big_string)
    # Rather than explicit loop, just replace view with one shorter view
    # on each loop
    while remaining_suffix:  # Stop when we've sliced to empty view
        some_constant_time_operation(remaining_suffix)
        remaining_suffix = remaining_suffix[1:]

memoryview 的切片确实创建了新的视图对象（它们只是超轻量级的，具有与它们查看的数据量无关的固定大小），只是没有任何数据，所以 some_constant_time_operation 如果需要，可以存储一个副本，当我们稍后将其切片时，它不会被更改。 Should you need a proper copy as Py2 str /Py3 bytes , you can call .tobytes() to get the raw bytes obj, or (在 Py3 中仅出现），将其直接解码为 str 从缓冲区复制，例如 str(remaining_suffix[10:20], 'latin-1') 。

原文由 ShadowRanger 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

这完全取决于你的切片有多大。我将以下两个基准放在一起。第一个切片整个字符串，第二个切片只是一点点。使用 此工具 进行曲线拟合可得出

# s[1:-1]
y = 0.09 x^2 + 10.66 x - 3.25

# s[1:1000]
y = -0.15 x + 17.13706461

对于最大 4MB 的字符串切片，第一个看起来非常线性。我想这确实衡量了构建第二个字符串所花费的时间。第二个是相当稳定的，虽然它太快了，但可能不太稳定。

 import time

def go(n):
    start = time.time()
    s = "abcd" * n
    for j in xrange(50000):

        #benchmark one
        a = s[1:-1]

        #benchmark two
        a = s[1:1000]

    end = time.time()
    return (end - start) * 1000

for n in range(1000, 100000, 5000):
    print n/1000.0, go(n)

原文由 jozxyqk 发布，翻译遵循 CC BY-SA 3.0 许可协议