python - 字符串切片的时间复杂度

切片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(n)，其中n是len(big_string)吗？

最佳答案

简短的答案:str切片，通常是副本。这意味着对每个字符串的n后缀进行切片的函数正在执行O(n)工作。也就是说，如果可以使用 bytes s to get zero-copy views of the original bytes data处理类似于memoryview的对象，则可以避免复制。请参阅下面的如何进行零拷贝切片，以了解如何使其工作。

长答案:(C)Python str不会通过引用数据子集的 View 进行切片。 str切片有三种操作模式:

完整切片，例如mystr[:]:返回对完全相同的str的引用(不仅仅是共享数据，相同的实际对象，mystr is mystr[:]，因为str是不可变的，因此没有风险)

零长度切片和(取决于实现)缓存的长度1切片；空字符串是单例(mystr[1:1] is mystr[2:2] is '')，长度为1的低序数字符串也被缓存为单例(在CPython 3.5.0上，看起来所有在latin-1中可表示的字符，即range(256)中的Unicode序号都被缓存了)

所有其他切片:切片的str在创建时复制，此后与原始str无关

＃3之所以成为通用规则，是因为要避免大str的一小部分被保留在内存中的问题。如果您有一个1GB的文件，请按以下方式将其读入并切成薄片(是的，当您寻找时这很浪费，这只是为了说明):

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

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

如何进行零拷贝切片

有是方式，可以在Python中执行基于 View 的切片，而在Python 2中，它将在str上运行(因为str在Python 2中类似于字节，支持buffer protocol)。使用Py2 str和Py3 bytes(以及其他许多数据类型，例如bytearray，array.array，numpy数组，mmap.mmap s等)，您可以创建 memoryview that is a zero copy view of the original object，并且可以切片而不复制数据。因此，如果您可以对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的切片确实创建了新的 View 对象(它们只是超轻量的，固定大小与它们查看的数据量无关)，只是没有任何数据，因此some_constant_time_operation可以在需要时存储副本，并且不会稍后我们将其切片时发生了变化。如果您需要适当的副本作为Py2 str/Py3 bytes，则可以调用.tobytes()以获取原始bytes obj，或者(仅在Py3中出现)将其解码为从缓冲区复制的str，例如str(remaining_suffix[10:20], 'latin-1')。

关于python - 字符串切片的时间复杂度，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/35180377/