Question

字符串处理在大多数编程程序语言中都不可避免，字符串的连接也是在编程过程中经常需要面对的问题。Python中的字符串与其他一些程序语言如C++、Java有一些不同，它为不可变对象，一旦创建便不能改变，它的这个特性直接影响到Python中字符串连接的效率。我们首先来看常见的两种字符串连接方法。

1）使用操作符+连接字符串的方法如下：

>>> str1,str2,str3 = 'testing ','string ','concatenation '
>>> str1+str2+str3
'testing string concatenation '
>>>

2）使用join方法连接字符串的方法如下：

>>> str1,str2,str3 = 'testing ','string ','concatenation '
>>> ''.join([str1,str2,str3])
'testing string concatenation '
>>>

思考这么一个问题：上述两种字符串连接的方法除了使用形式上的不同还有其他区别吗？性能上会不会有所差异呢？来看下面这个测试例子：

import timeit
#
生成测试所需要的字符数组
strlist=["it is a long value string will not keep in memory" for n in range(100000)]
#100000
为字符串连接的数目，下面对应的测试数据，每次需要修改
def join_test():
  return ''.join(strlist)   #
使用join
方法连接strlist
中的元素并返回字符串
def plus_test():
  result = ''
  for i,v in enumerate(strlist):
    result= result+ v         #
使用+
进行字符串连接
  return result
if __name__ == '__main__':
  jointimer = timeit.Timer("join_test()","from __main__ import join_test")
  print jointimer.timeit(number = 100)
  plustimer = timeit.Timer("plus_test()","from __main__ import plus_test")
  print plustimer.timeit(number = 100)

给上面的程序传入一组测试参数（测试参数为3，10，100，1000，10000，100000；分别表示每一次测试所要连接的字符串的数量），程序用于测试join_test()和plus_test()这两个方法在字符串连接规模改变时所消耗时间的变化。测试结果记录如表3-1所示。

表3-1　join_test()和plus_test()连接字符串所耗时间记录

表3-1可以用图3-3所示的X-Y图表示，其中X轴表示所要连接的字符串的数量，Y轴表示消耗的时间。

图3-3　join_test()和plus_test()耗时比较图（运行时间扩大10000倍）

从分析测试结果图表我们不难发现：分别使用join()方法和使用+操作符来连接字符串，join()方法的效率要高于+操作符，特别是字符串规模较大的时候，join()方法的优势更为明显（如连接数为100000的时候，两者耗时相差上百倍）。造成这种差别的原因在哪里呢？我们来探讨一下。当用操作符+连接字符串的时候，由于字符串是不可变对象，其工作原理实际上是这样的：如果要连接如下字符串：S1+S2+S3+.......+SN，执行一次+操作便会在内存中申请一块新的内存空间，并将上一次操作的结果和本次操作的右操作数复制到新申请的内存空间，即当执行S1+S2的时候会申请一块内存，并将S1、S2复制到该内存中，依次类推，如图3-4所示。因此，在N个字符串连接的过程中，会产生N-1个中间结果，每产生一个中间结果都需要申请和复制一次内存，总共需要申请N-1次内存，从而严重影响了执行效率。N越大，对内存的申请和复制的次数越多，+操作符的效率就越低。因此，整个字符连接的过程中，相当于S1被复制N-1次，S2被复制N-2次....SN复制1次（并不完全等同于S1复制N-1次，因为后续复制都是对中间结果的复制），所以字符串的连接时间复杂度近似为O(n^2)。

图3-4　操作符+连接字符串示意图

而当用join()方法连接字符串的时候，会首先计算需要申请的总的内存空间，然后一次性申请所需内存并将字符序列中的每一个元素复制到内存中去，所以join操作的时间复杂度为O(n)。

因此，字符串的连接，特别是大规模字符串的处理，应该尽量优先使用join而不是+。