字符串切片的时间复杂度

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

长答案：（C）Python str不会通过引用数据子集的视图进行切片。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，支承缓冲协议）。用的Py2 str和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')。