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

在Python編程語(yǔ)言中，構(gòu)造一些較長(zhǎng)的字符串事常常會(huì)產(chǎn)生一些運(yùn)行很慢的代碼。本文我將研究不同字符串合并方法的計(jì)算性能。

在Python中，字符串(string)對(duì)象是不可變的(每次關(guān)聯(lián)一個(gè)新的字符串變量都會(huì)在內(nèi)存中創(chuàng)建一個(gè)新的對(duì)象)(譯注:類同于Java,.NET等現(xiàn)代語(yǔ)言，他們都會(huì)在其VM中保留一個(gè)字符串池，里面保存所有產(chǎn)生的目標(biāo)字符串值或臨時(shí)字符串值)。這方面它與perl、VB等語(yǔ)言中的字符串變量可以任意修改有所不同。如果使用一些比較顯而易見的方法(比如：每次都是在新產(chǎn)生的字符串末尾添加一個(gè)新短字符串片段)從一些短字符串片段構(gòu)造長(zhǎng)字符串在Python中可能會(huì)不是很有效率。每次你的在字符串末尾添加內(nèi)容，Python解釋器都會(huì)創(chuàng)建一個(gè)新的對(duì)象并且復(fù)制新產(chǎn)生的對(duì)象和原來(lái)的對(duì)象到解釋器中(譯注:應(yīng)該是復(fù)制到Python解釋器的字符串常量池中)。隨著處理的字符串的增多，這樣的處理過(guò)程將會(huì)越來(lái)越慢。

其他一些其他的方法呢？他們是否有效并且與原始方法相比它們性能方面如何？我決定試試一些其他的構(gòu)造長(zhǎng)字符串的方法，并看看它們?cè)谛噬隙加猩恫煌?

為了比較，我需要一個(gè)測(cè)試程序來(lái)調(diào)用大量的字符串片段構(gòu)造長(zhǎng)字符串。它不應(yīng)該有太多的額外計(jì)算，好讓我們測(cè)試的性能僅僅依賴于字符串操作的性能。

我的測(cè)試用例是合并一些從0到某個(gè)大整數(shù)的數(shù)字。這樣我們也可以很容易的改變需要產(chǎn)生字符串的大小(譯注:改變那個(gè)大整數(shù))。比如前20個(gè)整數(shù)產(chǎn)生如下的字符串：

0123456789010111213141516171819

盡管這個(gè)特別的測(cè)試問(wèn)題不會(huì)有任何的現(xiàn)實(shí)應(yīng)用，但我想，因?yàn)樗苋菀拙幊滩⑶以诟拍詈陀?jì)算上都簡(jiǎn)單，那么它能是一個(gè)很好的測(cè)試用例。這些字符串片段在值和長(zhǎng)度上都不同，這也可以防止解釋器或硬件對(duì)依賴于重復(fù)字節(jié)的優(yōu)化(譯注:比如對(duì)重復(fù)相同的字符串進(jìn)行壓縮等處理)。我不認(rèn)為Python解釋器真的這樣做了，但是作為測(cè)試的一個(gè)好原則就是不能受這種優(yōu)化情況的影響。

六個(gè)方法

下面是我測(cè)試的一些方法，每小段Python代碼都返回相同的字符串。

方法一：樸素的添加(Method 1: Naive appending)

def method1():

out_str = ''

for num in xrange(loop_count):

out_str += `num`

return out_str

對(duì)于我來(lái)說(shuō)，這是解決該問(wèn)題的最顯而易見的方法。使用字符串連接操作(+=)添加每個(gè)字符串片段到字符串中。loop_count告訴我們要添加的字符串片段數(shù)。第四行中的數(shù)字num兩邊的重音符(``)會(huì)把整數(shù)轉(zhuǎn)換為相對(duì)于的字符串。你可以使用str()方法完成一樣的功能，但是，比較起來(lái)它可能稍慢些，因此我所有的方法中都是使用重音符(``)。如我說(shuō)言，盡管很淺顯，但是這個(gè)方法根本不是很有效(譯注:maybe應(yīng)該加個(gè)”率”子)。你可以再下面的測(cè)試中看到它每秒僅僅能合并3770個(gè)字符串片段。如果你需要合并很多的字符串片段，那么這可能不是很好的解決方法。

方法二：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類庫(kù)中包括一個(gè)MutableString類。根據(jù)其文檔描述它主要用于教學(xué)目的(譯注: "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.")。你可以能會(huì)以為在一個(gè)可變字符串上添加操作不會(huì)從分配或者拷貝字符串(譯注:本來(lái)該類應(yīng)該很像Java的StringBuilder的)。但是在測(cè)試中該方法比方法1還差。通過(guò)查看UserString.py的源代碼我發(fā)現(xiàn)字符串在MutableString中的存儲(chǔ)就是string，MutableString甚至都沒(méi)重寫__add__方法。所以使用該類對(duì)象合并字符串不會(huì)比一般的不可變字符串更快，實(shí)際上由于解釋MutableString方法需要一些額外的開銷會(huì)使得該方法更慢。

方法三：字符數(shù)組(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()

我?guī)缀醵紱](méi)有嘗試這種方法，但是郵件列表中有人提到了，所以我決定試試。該方法的思想就是用字符數(shù)組存儲(chǔ)字符串。Python中的數(shù)組是可變的，所以它可以被原地改變(譯注:也就是在該對(duì)象的那塊內(nèi)存上進(jìn)行改變，而不需要通過(guò)復(fù)制到其他的空間上實(shí)現(xiàn))而不需要拷貝現(xiàn)存的數(shù)組內(nèi)容。這里我們對(duì)改變現(xiàn)存的數(shù)組元素沒(méi)有興趣。我們只是在數(shù)組末尾添加一些新的數(shù)組元素。fromstring()方法一個(gè)字符一個(gè)字符的添加字符串字符到字符數(shù)組對(duì)象中。

方法四：構(gòu)造一個(gè)字符串列表,然后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)

這是一種通常被推薦的方法，因?yàn)樗淖址喜⒎椒ê躊ython。首先構(gòu)造一個(gè)包含所有需要合并的字符串列表，然后使用一個(gè)字符串的join操作構(gòu)造包含所有列表元素的字符串。

這人有點(diǎn)好玩，看看python習(xí)語(yǔ)的最后一行-我們?cè)诖_定的空字符串上調(diào)用join方法。不是所有的語(yǔ)言都會(huì)讓你在一個(gè)字面上的字符串調(diào)用方法(譯注:這里的意識(shí)是’’是空字符串)。如果你覺得這兒有點(diǎn)不爽，你可以寫成如下形式: string.join(str_list, '')。

方法五：寫到一個(gè)偽文件中去(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類可以像文件一樣工作，但是它存儲(chǔ)為一個(gè)字符串。很明顯，添加內(nèi)容到文件中是很容易的—你可以簡(jiǎn)單的寫入到文件末尾，對(duì)StringIO類對(duì)象的操作也是一樣。還有一個(gè)相似的模塊叫StringIO, 不過(guò)它是以Python實(shí)現(xiàn)的，而cStringIO是用C實(shí)現(xiàn)的，所以cStringIO速度上會(huì)更快。使用cStringIO對(duì)象，我么可以構(gòu)造一個(gè)每次寫入一次內(nèi)容的字符串，然后通過(guò)調(diào)用getvalue()方法收集其中的所有內(nèi)容。

有意思的是，同python類似，在java中字符串也是不可變的對(duì)象。Java中有個(gè)類叫StringBuffer,它比python中的StringIO和數(shù)組方法都更加強(qiáng)大，因?yàn)樗粌H支持添加字符串還支持插入和刪除子字符串操作。

方法六：列表推導(dǎo) (Method 6: List comprehensions)

def method6():

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

方法的代碼是最短的。并且令人驚喜的是他也是最快的。它及其緊湊并且也非常好理解。使用列表推導(dǎo)創(chuàng)建一個(gè)列表并使用join方法合并它們。還如比這個(gè)簡(jiǎn)單的嗎？實(shí)際上這是方法4的簡(jiǎn)略版，當(dāng)然，它也需要消耗差不多的空間。它更快是因?yàn)椴恍枰谘h(huán)的每次都調(diào)用list.append()方法。

測(cè)試結(jié)果

我想要查看合并字符串時(shí)所花費(fèi)的時(shí)間和計(jì)算時(shí)Python解釋器的內(nèi)存使用情況。盡管內(nèi)存很便宜(譯注:這里應(yīng)該是內(nèi)存開銷不是非常大的意思)，但是依然有很多原因使其成為一個(gè)重要的因素。首先，Python程序常常會(huì)運(yùn)行在資源受限的系統(tǒng)上。例如，在一個(gè)共享虛擬主機(jī)的環(huán)境下，機(jī)器可能對(duì)每個(gè)進(jìn)程設(shè)置了一定大小的內(nèi)存使用。系統(tǒng)內(nèi)核往往會(huì)殺死內(nèi)存分配超過(guò)一定額度的進(jìn)程。這種情況對(duì)于一些CGI腳本(譯注: Computer Graphics Interface)，長(zhǎng)時(shí)運(yùn)行的服務(wù)器程序來(lái)說(shuō)將是不好的現(xiàn)象。所以在這種情況下，保存內(nèi)存使用不超過(guò)預(yù)期是很重要的。另一個(gè)原因是當(dāng)我們處理大量的字符串的時(shí)候，解釋器的內(nèi)存分配將會(huì)變得非常大可能會(huì)導(dǎo)致虛擬內(nèi)存的訪問(wèn)(譯注:paging是操作系統(tǒng)中的一個(gè)概念，表示對(duì)硬盤頁(yè)面的訪問(wèn))。這種情況下的性能將會(huì)直線下降。如果你發(fā)現(xiàn)了時(shí)間上最快的算法當(dāng)然無(wú)所謂了---如果它使用了過(guò)多的內(nèi)存將會(huì)允許得和狗(譯注:應(yīng)該是像蝸牛吧,J)一樣慢。如果用的算法使用更少的內(nèi)存，那么就會(huì)介紹paging的機(jī)會(huì)，我們也將會(huì)有更多的可預(yù)測(cè)性能。

我使用自己的Python過(guò)程分別測(cè)試每種方法。

我在一臺(tái)按照了FreeBSD 4.9 的433MHz PII Celeron機(jī)器上使用Python 2.2.1運(yùn)行這些測(cè)試程序。

結(jié)果：兩萬(wàn)個(gè)整數(shù)(Results: Twenty thousand integers)

第一個(gè)測(cè)試將兩萬(wàn)個(gè)整數(shù)合并成一個(gè)86kb大小的字符串。

結(jié)果：五十萬(wàn)個(gè)整數(shù)(Results: Five hundred thousand integers)

接下來(lái)我測(cè)試了將五十萬(wàn)個(gè)整數(shù)合并成一個(gè)2,821kb大小的字符串。這個(gè)測(cè)試更嚴(yán)厲，我們開始想看看Python解釋器進(jìn)程的使用資源大小隨著用于計(jì)算的數(shù)據(jù)結(jié)構(gòu)變化情況。

這個(gè)測(cè)試中我沒(méi)有運(yùn)行方法1和方法2。他們的每次append操作都需要拷貝整個(gè)原串，因此他們的性能將是O(n^2)的(譯注:這個(gè)地方不是很理解，可能說(shuō)的是包括在常量池中尋找字符串的時(shí)間)。使用他們?cè)俸喜?shù)十萬(wàn)個(gè)字符串時(shí)可能要花數(shù)分鐘。

從圖中可以看書，與前面一個(gè)測(cè)試相比較，方法3,4,6在規(guī)模增大時(shí)每秒合并的字符串?dāng)?shù)目在減少。這個(gè)不奇怪(由于整數(shù)值的增大，相對(duì)于的字符串表示也在增大，大概前一個(gè)測(cè)試中的5個(gè)相當(dāng)于該測(cè)試的4個(gè)吧)。在第一個(gè)測(cè)試中，方法3比前兩個(gè)方法塊了近10倍，但是它性能在更大規(guī)模數(shù)據(jù)上的測(cè)試并沒(méi)有相應(yīng)的提升。其實(shí)它比之前還慢了60%，但相較于其他方法它使用了更少的空間。很明顯，Python在有效的存儲(chǔ)數(shù)組和臨時(shí)字符串的垃圾回收上做了一些工作。

方法4在性能上比樸素的添加提高了很多，在兩萬(wàn)個(gè)數(shù)據(jù)的測(cè)試中提高了近20倍在五十萬(wàn)的數(shù)據(jù)上也有很好的提高。方法6始終是最好的，但是方法5也有很好的性能，并且直追方法6。我們猜測(cè)，當(dāng)測(cè)試更大規(guī)模數(shù)據(jù)的時(shí)候，方法5會(huì)超過(guò)方法6。

我們也要注意到空間開銷的大小。方法6的解釋器使用了22,844kB的內(nèi)存，8倍于其實(shí)際的大小，反而方法3和方法5僅僅使用了其一般的內(nèi)存。

總結(jié)

我在實(shí)際編程中常常使用方法7，它很快并且也很好理解。它僅需要你寫一個(gè)返回需要添加字符串的表達(dá)式。有的時(shí)候這可能不是很方便，比如：有多個(gè)不同的字符串快需要用于合并時(shí)，這種情況下，你可能需要使用方法4和方法5。

方法4在可行上更好。你可以使用在添加的字符串列表上切片，或者插入，刪除和修改操作。它在添加操作上的性能也是很好的。

方法五在效率上更好。它使用更少的內(nèi)存(遠(yuǎn)少于方法4和6)，并且在處理大量數(shù)據(jù)(大概多于700,000時(shí))時(shí)比列表推導(dǎo)的更快。如果你需要添加非常多的字符串，cStringIO是一個(gè)很好的方向。

測(cè)試技術(shù)

計(jì)算每個(gè)方法的執(zhí)行時(shí)間相對(duì)來(lái)說(shuō)還比較容易。我使用Python類庫(kù)中的timing模塊計(jì)算花費(fèi)的時(shí)間。我沒(méi)有試圖去該除了運(yùn)行于該機(jī)上的其他程序，單獨(dú)計(jì)算所運(yùn)行的Python程序的CPU時(shí)間開銷，但是除了Python程序，機(jī)器是空閑的，所以我不認(rèn)為此處計(jì)算出的時(shí)間與CPU的運(yùn)行時(shí)間有什么不一樣的。

計(jì)算內(nèi)存開銷就有點(diǎn)困難了，因?yàn)镻ython本身沒(méi)有提供方法用于監(jiān)控其所分配對(duì)象的空間占用大小(譯注:這點(diǎn)上JVM做的很好，它的tools.jar包里面有很多性能監(jiān)控的工具)，所以我使用了UNIX的’PS’命令去監(jiān)控它。因?yàn)檎加每臻g會(huì)隨著程序的運(yùn)行而改變，而我想計(jì)算其最大的分配空間。為了得到結(jié)果，我在計(jì)算完成的時(shí)候運(yùn)行’ps’命令。ps_stat()的調(diào)用插在合并方法return語(yǔ)句前，因此可以在垃圾回收啟動(dòng)前計(jì)算其程序占用空間大小。我稍稍的改變了一點(diǎn)你在上面看到的代碼---ps_stat()運(yùn)行的計(jì)算結(jié)果用一個(gè)字符串變量存儲(chǔ)。我執(zhí)行的ps_stat()方法分離ps命令返回的各個(gè)域項(xiàng)并選擇內(nèi)存使用大小項(xiàng)所對(duì)應(yīng)的值。這里是使用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：在文章題目的翻譯上，我糾結(jié)于“Python中有效的字符串拼接方法”和“Python中有效的字符串合并方法”很久，最后還是覺得第一句中太口語(yǔ)化了，并且可能也僅僅是我自己喜歡拼接這個(gè)詞，所以還是選擇了“合并”。

備注3：其實(shí)這些方法中我用到較多的還是方法3和方法6，其他的還真不太了解。另外，文章中的那兩個(gè)圖，我沒(méi)有通過(guò)自己的實(shí)驗(yàn)數(shù)據(jù)結(jié)果來(lái)畫，主要還是我不太會(huì)畫。Python還不是很熟悉，那些繪圖模塊更不熟悉了，這個(gè)還有加以學(xué)習(xí)。

備注4：文章后面還有兩段內(nèi)容，不過(guò)與本文主題沒(méi)有什么關(guān)系，就沒(méi)有翻譯了。這篇文章也算是正了八經(jīng)的翻譯的一篇吧。以前翻譯的都是只有幾段文字的短文。曾試圖翻譯過(guò)wikipedia的article，但最終都沒(méi)成文。讀書的時(shí)候，我其實(shí)是很不喜歡，也不是非常欣賞那種通過(guò)翻譯文章來(lái)理解文章的做法，但是現(xiàn)在我發(fā)現(xiàn)我錯(cuò)了，理解固然主要，但如果能翻譯那就是更高層次的理解；很多時(shí)候，我覺得對(duì)原文理解了，但是沒(méi)法用自己的母語(yǔ)去描述它，這說(shuō)明我還是沒(méi)有很好的理解。就像對(duì)某個(gè)概念的理解，我做不到能書寫或者講授，那也說(shuō)明我沒(méi)有理解透徹。

最好，這篇文章也翻譯的匆忙，肯定不如人意的地方大大多于有點(diǎn)價(jià)值的地方。還忘大家不要吝嗇批評(píng)指正