字符串切片的时间复杂度

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)

… …将其时间复杂度是O(n)或，其中是？O(n2)``n``len(big_string)

Answer 1

简短的答案：str通常是切片。这意味着对每个字符串n后缀进行切片的函数正在起作用。也就是说，如果可以使用s处理类似对象，则可以避免复制，以获取原始字节数据的零复制视图。有关
如何 使其工作的信息，请参见下面的如何进行 零拷贝切片
。O(n2)``bytesmemoryview

长答案：（C）Pythonstr不会通过引用数据子集的视图进行切片。str切片共有三种操作模式：

1. 完整切片，例如mystr[:]：返回完全相同的引用str（不只是共享数据，相同的实际对象，mystr is mystr[:]因为它str是不可变的，因此没有风险）
2. 零长度切片和（取决于实现）缓存的长度1切片；空字符串是单例（mystr[1:1] is mystr[2:2] is ''），长度为1的低序数字符串也将被缓存为单例（在CPython 3.5.0上，看起来所有可在latin-1中表示的字符range(256)都被缓存了，即，是Unicode序数）。
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中类似于字节，因此支持缓冲协议）。用的Py2str和PY3
bytes（以及许多其他数据类型，例如bytearray，array.array，numpy阵列，mmap.mmapS等），则可以创建一个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:]

的memoryviews切片确实创建了新的视图对象（它们只是超轻量的，固定大小与它们查看的数据量无关），只是没有任何数据，因此some_constant_time_operation可以存储副本，并且在需要时不会更改我们稍后将其切成薄片。如果您需要适当的副本作为Py2
str/ Py3
bytes，则可以调用.tobytes()获取原始bytesobj，或者（仅在Py3中显示），将其直接解码为str从缓冲区复制的a
，例如str(remaining_suffix[10:20], 'latin-1')。