Python字符串连接成语.需要澄清.

Question

来自http://jaynes.colorado.edu/PythonIdioms.html

"将字符串构建为列表并在结尾处使用'.join.join是在分隔符上调用的字符串方法,而不是列表.从空字符串调用它连接没有分隔符的片段,这是一个Python怪癖而是首先是令人惊讶的.这很重要:用+构建字符串是二次时间而不是线性的!如果你学习了一个成语,那么学习这个.

错误:对于字符串中的s:结果+ = s

右:result =''.join(strings)"

我不确定为什么这是真的.如果我有一些字符串我想加入它们,对我来说,将它们放入列表然后调用''.join并不是直觉上更好.不将它们放入列表会产生一些开销吗？澄清...

Python命令行:

>>> str1 = 'Not'
>>> str2 = 'Cool'
>>> str3 = ''.join([str1, ' ', str2]) #The more efficient way **A**
>>> print str3
Not Cool
>>> str3 = str1 + ' ' + str2 #The bad way **B**
>>> print str3
Not Cool

是一个非常线性的时间而B是二次时间吗？

Answer 1

是.对于您选择的示例,重要性不明确,因为您只有两个非常短的字符串,因此追加可能会更快.

但是每次a + b在Python中使用字符串时都会导致新的分配,然后将a和b中的所有字节复制到新字符串中.如果在具有大量字符串的循环中执行此操作,则必须再次复制这些字节,并且每次必须再次复制,并且每次必须复制的数量变得更长.这给出了二次行为.

另一方面,创建字符串列表不会复制字符串的内容 - 它只是复制引用.这非常快,并且在线性时间内运行.然后,join方法只进行一次内存分配,并将每个字符串复制到正确的位置一次.这也只需要线性时间.

所以是的,''.join如果你有可能处理大量的字符串,请使用这个习惯用法.只需要两个字符串就没关系.

如果您需要更有说服力,请尝试自己创建一个10M字符的字符串:

>>> chars = ['a'] * 10000000
>>> r = ''
>>> for c in chars: r += c
>>> print len(r)

和....相比:

>>> chars = ['a'] * 10000000
>>> r = ''.join(chars)
>>> print len(r)

第一种方法大约需要10秒钟.第二个不到1秒.

Answer 2

重复级联是二次的,因为它是施莱米尔的画家算法(请注意,某些实现会优化它,使其不是二次的).join避免这种情况,因为它占用整个字符串列表,分配必要的空间并在一次传递中进行连接.