字符串切片的时间复杂度

Question

字符串切片的时间复杂度

44

切片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)

如果 n 是 len(big_string)，那么它的时间复杂度是 O(n) 还是 O(n²)？

- Mark Amery

1

你是否真的关心复杂性，或者只在意它是否“足够快”？如果是后者，最好的做法是尝试编写更简单的代码，如果速度足够快，那么复杂性就不重要了。 - Scott Hunter

@MarkAmery，你会考虑构建一个后缀数组吗？还是这个不相关？对于长度为n的字符串，它保证了复杂度为O(n)。 - Yannis P.

1

相关：sorted(xrange(n), key=lambda i: buffer(data, i)) 用于创建后缀数组 - jfs

相关：Python在字符串上进行切片引用吗？ - ShadowRanger

3个回答

4

这取决于你的切片大小。我组合了以下两个基准测试。第一个将整个字符串切片，第二个只切了一小部分。使用这个工具进行曲线拟合得出：

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

- jozxyqk

2

嗯，术语“0.086 x^2 + 10.66 x - 3.25”对我来说不是很线性 :) 但是对于相对较小的n，看起来是线性的... - Yannis P.

@YannisP。我假设（并希望！）0.086 x^2只是曲线拟合器对随机变化过于敏感，而不是切片真的是一个O(n^2)操作。如果切片是O(n^2)，那就太糟糕了！ - Mark Amery

很好。如果Python和其他编程语言复制字符串切片的起始和结束内存位置，而不是整个字符串，这对我来说也是有意义的，因此可以获得O(1)的切片效果。 - Yannis P.

1

@YannisP。是的...但我猜那会使垃圾收集字符串的代码比仅实现带复制的切片更加复杂，并且可能在收集时引入性能问题。这是一个复杂的问题，我一眼看不出是否可能在不损害垃圾收集效率或失去对巨大字符串进行垃圾收集的能力的情况下获得O(1)切片，即使还有对它们的微小切片的存活引用。 - Mark Amery

1

传递索引并不那么糟糕，如果你只是将它们打包在一个对象中。

from dataclasses import dataclass

@dataclass
class StrSlice:
    str: str
    start: int
    end: int

def middle(slice):
    return slice.str[(slice.start + slice.end) // 2]

def reverse(slice):
    return slice.str[slice.start : slice.end][::-1]

def length(slice):
    return slice.end - slice.start

def chars(slice):
    yield from (slice.str[i] for i in range(slice.start, slice.end)

def equals(slice1, slice2):
    if length(slice1) != length(slice2):
        return False
    return all(c1 == c2 for c1, c2 in zip(chars(slice1), chars(slice2))

- Luke Miles

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ShadowRanger · Accepted Answer

简短回答：通常情况下，str 切片会复制数据。这意味着对于每个字符串的 n 个后缀进行切片的函数会执行 O(n²) 次操作。不过，如果你能使用类似于 bytes 的对象，并使用 memoryview 来获取原始字节数据的零拷贝视图，就可以避免复制。请查看下面的如何进行零拷贝切片以了解如何实现。

详细回答：(C)Python 中的 str 不会通过引用数据子集的视图进行切片。就 str 切片而言，有三种操作模式：

完整切片，例如 mystr[:] ：返回到确切相同的 str 的引用（不仅是共享数据，而是同一对象，mystr is mystr [:]，因为 str 是不可变的，所以这样做没有风险）
零长度切片和（依赖于实现）缓存长度为1的切片；空字符串是单例的（mystr[1:1] is mystr[2:2] is ''），长度为1的低序字符串也是缓存单例的（在CPython3.5.0上，所有可以表示的字符集latin-1即Unicode取值在 range(256) 范围内的字符都被缓存了）
其他所有切片：创建时会复制被切割的 str，并且此后与原始 str 无关

为什么 #3 是一般规则？主要是为了避免通过小部分数据的视图来保留大型 str 的问题。如果你有一个1GB的文件，读入并像这样进行切片（是的，当你可以寻址时，这是浪费的，这只是为了说明）:

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

如果你使用视图来展示最终1 KB的数据，那么你需要在内存中保存1 GB的数据，这是非常浪费的。由于切片通常较小，复制一个切片通常比创建视图更快。这也意味着 str 可以更简单；它需要知道自己的大小，但不需要跟踪数据的偏移量。

如何进行零拷贝切片

有一些方法可以在 Python 中执行基于视图的切片，在 Python 2 中可以对 str 进行操作（因为在 Python 2 中，str 是类似字节的数据类型，支持缓冲区协议）。在 Py2 str 和 Py3 bytes（以及许多其他数据类型，如 bytearray、array.array、numpy 数组、mmap.mmap 等），你可以创建一个memoryview，这是原始对象的零拷贝视图，可以进行切片而不复制数据。因此，如果您可以使用（或编码）到 Py2 str/Py3 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()以获取原始的bytes对象，或者（仅在Py3中可行）直接将其解码为一个str，该字符串从缓冲区复制，例如：str(remaining_suffix[10:20], 'latin-1')。