python字符串切片函数_python – 字符串切片的时间复杂度

简短回答：str slice,一般来说,复制,所以你正在做O(n2)工作.也就是说,如果您可以使用

memoryviews to get zero-copy views of the original bytes data使用类似字节的对象,则可以避免复制.请参阅下面的“如何进行零复制切片”以了解如何使其工作.

答案很长：(C)Python str不会通过引用数据子集的视图进行切片. str切片有三种操作模式：

>完整切片,例如mystr [：]：返回对完全相同的str的引用(不仅仅是共享数据,相同的实际对象,mystr是mystr [：],因为str是不可变的,所以这样做没有风险)

>零长度切片和(依赖于实现)缓存长度为1个切片;单个字符串是空的字符串(mystr [1：1]是mystr [2：2]是”),长度为1的低序数字符串也是缓存的单例(在CPython 3.5.0上,它看起来像所有字符都可表示在latin-1中,即范围(256)中的Unicode序数,被缓存)

>所有其他切片：切片的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中类似于字节,支持buffer protocol).使用Py2 str和Py3字节(以及许多其他数据类型,如bytearray,array.array,numpy数组,mmap.mmaps等),您可以创建一个memoryview that is a zero copy view of the original object,并且可以在不复制数据的情况下进行切片.因此,如果您可以使用(或编码)Py2 str / Py3字节,并且您的函数可以使用任意字节对象,那么您可以这样做：

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:]

内存视图的片段确实会创建新的视图对象(它们只是超轻量级,固定大小与它们查看的数据量无关),而不是任何数据,因此some_constant_time_operation可以存储副本(如果需要)并且不会更改当我们稍后切片时如果你需要一个正确的拷贝作为Py2 str / Py3字节,你可以调用.tobytes()来获取原始字节obj,或者(仅在它出现的Py3中),将它直接解码为从缓冲区复制的str,例如： str(remaining_suffix [10:20],’latin-1′).