[译]Python中有效的字符串合并方法

砂拉豆

[译]Python中有效的字符串合并方法
------对不同方法的性能评估
　　介绍
　　在Python编程语言中，构造一些较长的字符串事常常会产生一些运行很慢的代码。本文我将研究不同字符串合并方法的计算性能。
　　在Python中，字符串(string)对象是不可变的(每次关联一个新的字符串变量都会在内存中创建一个新的对象)(译注:类同于Java,.NET等现代语言，他们都会在其VM中保留一个字符串池，里面保存所有产生的目标字符串值或临时字符串值)。这方面它与perl、VB等语言中的字符串变量可以任意修改有所不同。如果使用一些比较显而易见的方法(比如：每次都是在新产生的字符串末尾添加一个新短字符串片段)从一些短字符串片段构造长字符串在Python中可能会不是很有效率。每次你的在字符串末尾添加内容，Python解释器都会创建一个新的对象并且复制新产生的对象和原来的对象到解释器中(译注:应该是复制到Python解释器的字符串常量池中)。随着处理的字符串的增多，这样的处理过程将会越来越慢。
　　其他一些其他的方法呢？他们是否有效并且与原始方法相比它们性能方面如何？我决定试试一些其他的构造长字符串的方法，并看看它们在效率上都有啥不同。
　　为了比较，我需要一个测试程序来调用大量的字符串片段构造长字符串。它不应该有太多的额外计算，好让我们测试的性能仅仅依赖于字符串操作的性能。
　　我的测试用例是合并一些从0到某个大整数的数字。这样我们也可以很容易的改变需要产生字符串的大小(译注:改变那个大整数)。比如前20个整数产生如下的字符串：

　　0123456789010111213141516171819

　　尽管这个特别的测试问题不会有任何的现实应用，但我想，因为它很容易编程并且在概念和计算上都简单，那么它能是一个很好的测试用例。这些字符串片段在值和长度上都不同，这也可以防止解释器或硬件对依赖于重复字节的优化(译注:比如对重复相同的字符串进行压缩等处理)。我不认为Python解释器真的这样做了，但是作为测试的一个好原则就是不能受这种优化情况的影响。
　　六个方法
　　下面是我测试的一些方法，每小段Python代码都返回相同的字符串。
　　方法一：朴素的添加(Method 1: Naive appending)

　　def method1():
　　out_str = ''
　　for num in xrange(loop_count):
　　out_str += `num` 　　return out_str

　　对于我来说，这是解决该问题的最显而易见的方法。使用字符串连接操作(+=)添加每个字符串片段到字符串中。loop_count告诉我们要添加的字符串片段数。第四行中的数字num两边的重音符(``)会把整数转换为相对于的字符串。你可以使用str()方法完成一样的功能，但是，比较起来它可能稍慢些，因此我所有的方法中都是使用重音符(``)。如我说言，尽管很浅显，但是这个方法根本不是很有效(译注:maybe应该加个”率”子)。你可以再下面的测试中看到它每秒仅仅能合并3770个字符串片段。如果你需要合并很多的字符串片段，那么这可能不是很好的解决方法。
　　方法二：MutableString 类(Method 2: MutableString class)

　　def method2():
　　from UserString import MutableString
　　out_str = MutableString()
　　for num in xrange(loop_count):
　　out_str += `num` 　　return out_str

　　Python类库中包括一个MutableString类。根据其文档描述它主要用于教学目的(译注: "mutable string objects Python strings are immutable objects. This has the advantage, that strings may be used as dictionary keys. If this property isn't needed and you insist on changing string values in place instead, you may cheat and use MutableString. But the purpose of this class is an educational one: to prevent people from inventing their own mutable string class derived from UserString and than forget thereby to remove (override) the __hash__ method inherited from UserString. This would lead to errors that would be very hard to track down. A faster and better solution is to rewrite your program using lists.")。你可以能会以为在一个可变字符串上添加操作不会从分配或者拷贝字符串(译注:本来该类应该很像Java的StringBuilder的)。但是在测试中该方法比方法1还差。通过查看UserString.py的源代码我发现字符串在MutableString中的存储就是string，MutableString甚至都没重写__add__方法。所以使用该类对象合并字符串不会比一般的不可变字符串更快，实际上由于解释MutableString方法需要一些额外的开销会使得该方法更慢。
　　方法三：字符数组(Method 3: Character arrrays)

　　def method3():
　　from array import array
　　char_array = array('c')
　　for num in xrange(loop_count):
　　char_array.fromstring(`num`) 　　return char_array.tostring()

　　我几乎都没有尝试这种方法，但是邮件列表中有人提到了，所以我决定试试。该方法的思想就是用字符数组存储字符串。Python中的数组是可变的，所以它可以被原地改变(译注:也就是在该对象的那块内存上进行改变，而不需要通过复制到其他的空间上实现)而不需要拷贝现存的数组内容。这里我们对改变现存的数组元素没有兴趣。我们只是在数组末尾添加一些新的数组元素。fromstring()方法一个字符一个字符的添加字符串字符到字符数组对象中。
　　方法四：构造一个字符串列表,然后join它(Method 4: Build a list of strings, then join it)

　　def method4():
　　str_list = []
　　for num in xrange(loop_count):
　　str_list.append(`num`) 　　return ''.join(str_list)

　　这是一种通常被推荐的方法，因为它的字符串合并方法很Python。首先构造一个包含所有需要合并的字符串列表，然后使用一个字符串的join操作构造包含所有列表元素的字符串。
　　这人有点好玩，看看python习语的最后一行-我们在确定的空字符串上调用join方法。不是所有的语言都会让你在一个字面上的字符串调用方法(译注:这里的意识是’’是空字符串)。如果你觉得这儿有点不爽，你可以写成如下形式: string.join(str_list, '')。
　　方法五：写到一个伪文件中去(Method 5: Write to a pseudo file)

　　def method5():
　　from cStringIO import StringIO
　　file_str = StringIO()
　　for num in xrange(loop_count):
　　file_str.write(`num`) 　　return file_str.getvalue()

　　cStringIO模块提供的StringIO类可以像文件一样工作，但是它存储为一个字符串。很明显，添加内容到文件中是很容易的—你可以简单的写入到文件末尾，对StringIO类对象的操作也是一样。还有一个相似的模块叫StringIO, 不过它是以Python实现的，而cStringIO是用C实现的，所以cStringIO速度上会更快。使用cStringIO对象，我么可以构造一个每次写入一次内容的字符串，然后通过调用getvalue()方法收集其中的所有内容。
　　有意思的是，同python类似，在java中字符串也是不可变的对象。Java中有个类叫StringBuffer,它比python中的StringIO和数组方法都更加强大，因为它不仅支持添加字符串还支持插入和删除子字符串操作。
　　方法六：列表推导 (Method 6: List comprehensions)

　　def method6(): 　　return ''.join([`num` for num in xrange(loop_count)])

　　方法的代码是最短的。并且令人惊喜的是他也是最快的。它及其紧凑并且也非常好理解。使用列表推导创建一个列表并使用join方法合并它们。还如比这个简单的吗？实际上这是方法4的简略版，当然，它也需要消耗差不多的空间。它更快是因为不需要在循环的每次都调用list.append()方法。
　　测试结果
　　我想要查看合并字符串时所花费的时间和计算时Python解释器的内存使用情况。尽管内存很便宜(译注:这里应该是内存开销不是非常大的意思)，但是依然有很多原因使其成为一个重要的因素。首先，Python程序常常会运行在资源受限的系统上。例如，在一个共享虚拟主机的环境下，机器可能对每个进程设置了一定大小的内存使用。系统内核往往会杀死内存分配超过一定额度的进程。这种情况对于一些CGI脚本(译注: Computer Graphics Interface)，长时运行的服务器程序来说将是不好的现象。所以在这种情况下，保存内存使用不超过预期是很重要的。另一个原因是当我们处理大量的字符串的时候，解释器的内存分配将会变得非常大可能会导致虚拟内存的访问(译注:paging是操作系统中的一个概念，表示对硬盘页面的访问)。这种情况下的性能将会直线下降。如果你发现了时间上最快的算法当然无所谓了---如果它使用了过多的内存将会允许得和狗(译注:应该是像蜗牛吧,J)一样慢。如果用的算法使用更少的内存，那么就会介绍paging的机会，我们也将会有更多的可预测性能。
　　我使用自己的Python过程分别测试每种方法。
　　我在一台按照了FreeBSD 4.9 的433MHz PII Celeron机器上使用Python 2.2.1运行这些测试程序。
　　结果：两万个整数(Results: Twenty thousand integers)
　　第一个测试将两万个整数合并成一个86kb大小的字符串。

　　结果：五十万个整数(Results: Five hundred thousand integers)
　　接下来我测试了将五十万个整数合并成一个2,821kb大小的字符串。这个测试更严厉，我们开始想看看Python解释器进程的使用资源大小随着用于计算的数据结构变化情况。

　　这个测试中我没有运行方法1和方法2。他们的每次append操作都需要拷贝整个原串，因此他们的性能将是O(n^2)的(译注:这个地方不是很理解，可能说的是包括在常量池中寻找字符串的时间)。使用他们再合并数十万个字符串时可能要花数分钟。
　　从图中可以看书，与前面一个测试相比较，方法3,4,6在规模增大时每秒合并的字符串数目在减少。这个不奇怪(由于整数值的增大，相对于的字符串表示也在增大，大概前一个测试中的5个相当于该测试的4个吧)。在第一个测试中，方法3比前两个方法块了近10倍，但是它性能在更大规模数据上的测试并没有相应的提升。其实它比之前还慢了60%，但相较于其他方法它使用了更少的空间。很明显，Python在有效的存储数组和临时字符串的垃圾回收上做了一些工作。
　　方法4在性能上比朴素的添加提高了很多，在两万个数据的测试中提高了近20倍在五十万的数据上也有很好的提高。方法6始终是最好的，但是方法5也有很好的性能，并且直追方法6。我们猜测，当测试更大规模数据的时候，方法5会超过方法6。
　　我们也要注意到空间开销的大小。方法6的解释器使用了22,844kB的内存，8倍于其实际的大小，反而方法3和方法5仅仅使用了其一般的内存。
　　总结
　　我在实际编程中常常使用方法7，它很快并且也很好理解。它仅需要你写一个返回需要添加字符串的表达式。有的时候这可能不是很方便，比如：有多个不同的字符串快需要用于合并时，这种情况下，你可能需要使用方法4和方法5。
　　方法4在可行上更好。你可以使用在添加的字符串列表上切片，或者插入，删除和修改操作。它在添加操作上的性能也是很好的。
　　方法五在效率上更好。它使用更少的内存(远少于方法4和6)，并且在处理大量数据(大概多于700,000时)时比列表推导的更快。如果你需要添加非常多的字符串，cStringIO是一个很好的方向。
　　测试技术
　　计算每个方法的执行时间相对来说还比较容易。我使用Python类库中的timing模块计算花费的时间。我没有试图去该除了运行于该机上的其他程序，单独计算所运行的Python程序的CPU时间开销，但是除了Python程序，机器是空闲的，所以我不认为此处计算出的时间与CPU的运行时间有什么不一样的。
　　计算内存开销就有点困难了，因为Python本身没有提供方法用于监控其所分配对象的空间占用大小(译注:这点上JVM做的很好，它的tools.jar包里面有很多性能监控的工具)，所以我使用了UNIX的’PS’命令去监控它。因为占用空间会随着程序的运行而改变，而我想计算其最大的分配空间。为了得到结果，我在计算完成的时候运行’ps’命令。ps_stat()的调用插在合并方法return语句前，因此可以在垃圾回收启动前计算其程序占用空间大小。我稍稍的改变了一点你在上面看到的代码---ps_stat()运行的计算结果用一个字符串变量存储。我执行的ps_stat()方法分离ps命令返回的各个域项并选择内存使用大小项所对应的值。这里是使用15，可能不同版本的ps程序需要不同的值。
　　我使用的全部代码在这里。

　　from cStringIO import StringIO
import timing, commands, os
from sys import argv
　　
　　# .....
　　# method definitions go here
　　# .....
　　
　　def ps_stat():
　　global process_size
　　ps = commands.getoutput('ps -up ' + `pid`)
　　process_size = ps.split()[15]
　　
　　def call_method(num):
　　global process_size
　　timing.start()
　　z = eval('method' + str(num))()
　　timing.finish()
　　print "method", num
　　print "time", float(timing.micro()) / 1000000
　　print "output size ", len(z) / 1024, "kb"
　　print "process size", process_size, "kb"
　　print
　　
　　loop_count = 500000
　　pid = os.getpid()
　　 　　call_method(argv[1])

　　备注1：翻译自文章Efficient String Concatenation in Python
　　备注2：在文章题目的翻译上，我纠结于“Python中有效的字符串拼接方法”和“Python中有效的字符串合并方法”很久，最后还是觉得第一句中太口语化了，并且可能也仅仅是我自己喜欢拼接这个词，所以还是选择了“合并”。
　　备注3：其实这些方法中我用到较多的还是方法3和方法6，其他的还真不太了解。另外，文章中的那两个图，我没有通过自己的实验数据结果来画，主要还是我不太会画。Python还不是很熟悉，那些绘图模块更不熟悉了，这个还有加以学习。
　　备注4：文章后面还有两段内容，不过与本文主题没有什么关系，就没有翻译了。这篇文章也算是正了八经的翻译的一篇吧。以前翻译的都是只有几段文字的短文。曾试图翻译过wikipedia的article，但最终都没成文。读书的时候，我其实是很不喜欢，也不是非常欣赏那种通过翻译文章来理解文章的做法，但是现在我发现我错了，理解固然主要，但如果能翻译那就是更高层次的理解；很多时候，我觉得对原文理解了，但是没法用自己的母语去描述它，这说明我还是没有很好的理解。就像对某个概念的理解，我做不到能书写或者讲授，那也说明我没有理解透彻。 　　最好，这篇文章也翻译的匆忙，肯定不如人意的地方大大多于有点价值的地方。还忘大家不要吝啬批评指正。