Mar*_*ery 22 python time-complexity
切片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)nlen(big_string)
Sha*_*ger 32
简短回答:str切片,一般来说,复制.这意味着为每个字符串的n后缀执行切片的函数正在运行.也就是说,如果您可以使用s来处理类似对象以获取原始字节数据的零拷贝视图,则可以避免复制.有关如何使其工作的信息,请参阅下面的如何进行零拷贝切片.O(n2)bytesmemoryview
答案很长:(C)Python str不会通过引用数据子集的视图进行切片.str切片有三种操作模式:
mystr[:]:返回对完全相同的引用str(不仅仅是共享数据,相同的实际对象,mystr is mystr[:]因为它str是不可变的,因此没有风险这样做)mystr[1:1] is mystr[2:2] is ''),长度为1的低序数字符串也是缓存单例(在CPython 3.5.0上,看起来像所有在latin-1中可表示的字符,即Unicode序列range(256),都被缓存)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.mmapS等),则可以创建一个memoryview,它是原始对象的零拷贝视图,并且可以在不复制数据切片.因此,如果您可以使用(或编码)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:]
memoryviews 的切片确实会产生新的视图对象(它们只是超轻量级,固定大小与它们查看的数据量无关),而不是任何数据,因此some_constant_time_operation可以根据需要存储副本,并且当它们不会被更改时我们稍后将其分解.如果您需要一个正确的拷贝作为Py2 str/ Py3 bytes,您可以调用.tobytes()获取原始bytesobj,或者(仅在Py3中出现),将其直接解码str为缓冲区中的副本,例如str(remaining_suffix[10:20], 'latin-1').