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"
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,但最终都没成文。读书的时候,我其实是很不喜欢,也不是非常欣赏那种通过翻译文章来理解文章的做法,但是现在我发现我错了,理解固然主要,但如果能翻译那就是更高层次的理解;很多时候,我觉得对原文理解了,但是没法用自己的母语去描述它,这说明我还是没有很好的理解。就像对某个概念的理解,我做不到能书写或者讲授,那也说明我没有理解透彻。
最好,这篇文章也翻译的匆忙,肯定不如人意的地方大大多于有点价值的地方。还忘大家不要吝啬批评指正
数据分析咨询请扫描二维码
若不方便扫码,搜微信号:CDAshujufenxi
Excel是数据分析的重要工具,强大的内置功能使其成为许多分析师的首选。在日常工作中,启用Excel的数据分析工具库能够显著提升数 ...
2024-12-23在当今信息爆炸的时代,数据分析师如同一位现代社会的侦探,肩负着从海量数据中提炼出有价值信息的重任。在这个过程中,掌握一系 ...
2024-12-23在现代的职场中,制作吸引人的PPT已经成为展示信息的重要手段,而其中数据对比的有效呈现尤为关键。为了让数据在幻灯片上不仅准 ...
2024-12-23在信息泛滥的现代社会,数据分析师已成为企业决策过程中不可或缺的角色。他们的任务是从海量数据中提取有价值的洞察,帮助组织制 ...
2024-12-23在数据驱动时代,数据分析已成为各行各业的必需技能。无论是提升个人能力还是推动职业发展,选择一条适合自己的学习路线至关重要 ...
2024-12-23在准备数据分析师面试时,掌握高频考题及其解答是应对面试的关键。为了帮助大家轻松上岸,以下是10个高频考题及其详细解析,外加 ...
2024-12-20互联网数据分析师是一个热门且综合性的职业,他们通过数据挖掘和分析,为企业的业务决策和运营优化提供强有力的支持。尤其在如今 ...
2024-12-20在现代商业环境中,数据分析师是不可或缺的角色。他们的工作不仅仅是对数据进行深入分析,更是协助企业从复杂的数据信息中提炼出 ...
2024-12-20随着大数据时代的到来,数据驱动的决策方式开始受到越来越多企业的青睐。近年来,数据分析在人力资源管理中正在扮演着至关重要的 ...
2024-12-20在数据分析的世界里,表面上的技术操作只是“入门票”,而真正的高手则需要打破一些“看不见的墙”。这些“隐形天花板”限制了数 ...
2024-12-19在数据分析领域,尽管行业前景广阔、岗位需求旺盛,但实际的工作难度却远超很多人的想象。很多新手初入数据分析岗位时,常常被各 ...
2024-12-19入门数据分析,许多人都会感到“难”,但这“难”究竟难在哪儿?对于新手而言,往往不是技术不行,而是思维方式、业务理解和实践 ...
2024-12-19在如今的行业动荡背景下,数据分析师的职业前景虽然面临一些挑战,但也充满了许多新的机会。随着技术的不断发展和多领域需求的提 ...
2024-12-19在信息爆炸的时代,数据分析师如同探险家,在浩瀚的数据海洋中寻觅有价值的宝藏。这不仅需要技术上的过硬实力,还需要一种艺术家 ...
2024-12-19在当今信息化社会,大数据已成为各行各业不可或缺的宝贵资源。大数据专业应运而生,旨在培养具备扎实理论基础和实践能力,能够应 ...
2024-12-19阿里P8、P9失业都找不到工作?是我们孤陋寡闻还是世界真的已经“癫”成这样了? 案例一:本硕都是 985,所学的专业也是当红专业 ...
2024-12-19CDA持证人Louis CDA持证人基本情况 我大学是在一个二线城市的一所普通二本院校读的,专业是旅游管理,非计算机非统计学。毕业之 ...
2024-12-18最近,知乎上有个很火的话题:“一个人为何会陷入社会底层”? 有人说,这个世界上只有一个分水岭,就是“羊水”;还有人说,一 ...
2024-12-18在这个数据驱动的时代,数据分析师的技能需求快速增长。掌握适当的编程语言不仅能增强分析能力,还能帮助分析师从海量数据中提取 ...
2024-12-17在当今信息爆炸的时代,数据分析已经成为许多行业中不可或缺的一部分。想要在这个领域脱颖而出,除了热情和毅力外,你还需要掌握 ...
2024-12-17