字符串切片的时间复杂度

简短的答案：

str

通常是切片。这意味着对每个字符串

n

后缀进行切片的函数正在起作用。也就是说，如果可以使用s处理类似对象，则可以避免复制，以获取原始字节数据的零复制视图。有关
如何 使其工作的信息，请参见下面的如何进行 零拷贝切片
。

O(n2)``bytes

memoryview

---

长答案：（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)

   都被缓存了，即，是Unipre序数）。
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.mmap

S等），则可以创建一个

memoryview

，它是原始对象的零拷贝视图，并且可以在不复制数据切片。因此，如果您可以对Py2

str

/ Py3使用（或编码）

bytes

，并且您的函数可以与任意类似

bytes

的对象一起使用，则可以执行以下操作：

def do_something_on_all_suffixes(big_string):    # In Py3, may need to enpre 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

s切片确实创建了新的视图对象（它们只是超轻量的，固定大小与它们查看的数据量无关），只是没有任何数据，因此

some_constant_time_operation

可以存储副本，并且在需要时不会更改我们稍后将其切成薄片。如果您需要适当的副本作为Py2

str

/ Py3

bytes

，则可以调用

.tobytes()

获取原始

bytes

obj，或者（仅在Py3中显示），将其直接解码为

str

从缓冲区复制的a
，例如

str(remaining_suffix[10:20], 'latin-1')

。