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

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

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

其他一些其他的方法呢？他們是否有效并且與原始方法相比它們性能方面如何？我決定試試一些其他的構(gòu)造長字符串的方法，并看看它們在效率上都有啥不同。

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

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

0123456789010111213141516171819

盡管這個特別的測試問題不會有任何的現(xiàn)實應(yīng)用，但我想，因為它很容易編程并且在概念和計算上都簡單，那么它能是一個很好的測試用例。這些字符串片段在值和長度上都不同，這也可以防止解釋器或硬件對依賴于重復(fù)字節(jié)的優(yōu)化(譯注:比如對重復(fù)相同的字符串進(jìn)行壓縮等處理)。我不認(rèn)為Python解釋器真的這樣做了，但是作為測試的一個好原則就是不能受這種優(yōu)化情況的影響。

六個方法

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

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

def method1():

out_str = ''

for num in xrange(loop_count):

out_str += `num`

return out_str

對于我來說，這是解決該問題的最顯而易見的方法。使用字符串連接操作(+=)添加每個字符串片段到字符串中。loop_count告訴我們要添加的字符串片段數(shù)。第四行中的數(shù)字num兩邊的重音符(``)會把整數(shù)轉(zhuǎn)換為相對于的字符串。你可以使用str()方法完成一樣的功能，但是，比較起來它可能稍慢些，因此我所有的方法中都是使用重音符(``)。如我說言，盡管很淺顯，但是這個方法根本不是很有效(譯注:maybe應(yīng)該加個”率”子)。你可以再下面的測試中看到它每秒僅僅能合并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類。根據(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.")。你可以能會以為在一個可變字符串上添加操作不會從分配或者拷貝字符串(譯注:本來該類應(yīng)該很像Java的StringBuilder的)。但是在測試中該方法比方法1還差。通過查看UserString.py的源代碼我發(fā)現(xiàn)字符串在MutableString中的存儲就是string，MutableString甚至都沒重寫__add__方法。所以使用該類對象合并字符串不會比一般的不可變字符串更快，實際上由于解釋MutableString方法需要一些額外的開銷會使得該方法更慢。

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

方法四：構(gòu)造一個字符串列表,然后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。首先構(gòu)造一個包含所有需要合并的字符串列表，然后使用一個字符串的join操作構(gòu)造包含所有列表元素的字符串。

這人有點好玩，看看python習(xí)語的最后一行-我們在確定的空字符串上調(diào)用join方法。不是所有的語言都會讓你在一個字面上的字符串調(diào)用方法(譯注:這里的意識是’’是空字符串)。如果你覺得這兒有點不爽，你可以寫成如下形式: 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類可以像文件一樣工作，但是它存儲為一個字符串。很明顯，添加內(nèi)容到文件中是很容易的—你可以簡單的寫入到文件末尾，對StringIO類對象的操作也是一樣。還有一個相似的模塊叫StringIO, 不過它是以Python實現(xiàn)的，而cStringIO是用C實現(xiàn)的，所以cStringIO速度上會更快。使用cStringIO對象，我么可以構(gòu)造一個每次寫入一次內(nèi)容的字符串，然后通過調(diào)用getvalue()方法收集其中的所有內(nèi)容。

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

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

def method6():

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

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

測試結(jié)果

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

我使用自己的Python過程分別測試每種方法。

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

結(jié)果：兩萬個整數(shù)(Results: Twenty thousand integers)

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

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

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

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

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

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

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

總結(jié)

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

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

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

測試技術(shù)

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

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

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

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

最好，這篇文章也翻譯的匆忙，肯定不如人意的地方大大多于有點價值的地方。還忘大家不要吝嗇批評指正