字符串sli的时间复杂度

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

简而言之：切片，通常是拷贝。这意味着为字符串的每个n后缀做切片的函数正在做O(n2)工作。也就是说，如果可以使用^{}s to get zero-copy views of the original bytes data处理类似bytes的对象，就可以避免复制。有关如何使其工作，请参见下面的“如何执行零拷贝切片”。

长答案：（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上，看起来所有可以用拉丁文-1表示的字符，即range(256)中的Unicode序数都被缓存）
3. 所有其他切片：切片的str在创建时复制，之后与原始的str无关

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

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

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

如何进行零拷贝切片

在Python中，有很多方法可以执行基于视图的切片，在Python 2中，它将在str上工作（因为str与在python2中一样是字节，支持buffer protocol）。使用Py2str和Py3bytes（以及许多其他数据类型，如bytearray、array.array、numpy数组、mmap.mmap等），您可以创建一个^{} 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的切片确实生成了新的视图对象（它们只是超轻量级的，大小与它们所查看的数据量无关），只是没有任何数据，因此some_constant_time_operation可以在需要时存储副本，并且在以后对其进行切片时不会更改。如果您需要一个正确的副本Py2 str/Py3 bytes，您可以调用.tobytes()来获得原始的bytesobj，或者（在Py3中只出现），直接将其解码到从缓冲区复制的str，例如str(remaining_suffix[10:20], 'latin-1')。

Answer 2

这完全取决于你的切片有多大。我把以下两个基准组合在一起。第一个切片整个字符串，第二个只切片一点点。用this tool曲线拟合给出

# 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)