335
使用Rope來高效處理長字符串
前段時間看了這篇文章《Ropes：理論與實踐》。這兩天為了提高工作中某個係統對外接口的效率，才認真學習了一番。本質上Ropes是將字符串表示為一棵二叉樹，特別適用於長字符串的處理，貌似c++ STL庫中也有這麼個實現。具體實現和原理還是看這篇paper。《Ropes：理論與實踐》一文中給出的測試數據相當驚人，Ropes比之String和StringBuffer在append,insert,delete等操作上的效率都有一個數量級以上的差距。跑下作者給出的測試程序，其實在測試的字符串不是很長的情況下，這個差距並沒有那麼大，這也從側麵說明了Rope的應用範圍：即隻有在大量修改大型字符串的應用程序中才能看到明顯的性能提升。那麼是否可以用Rope替代StringBuffer做append生成字符串（比如我要的生成xml)。作者也說啦：
“由於 Rope 的附加性能通常比 StringBuffer 好，這時使用 rope 是否有意義呢？答案還是否。不論何時將輸入的數據組合在一起形成格式化輸出時，最漂亮最有效的方法是使用模板引擎（例如 StringTemplate 或 FreeMarker）。這種方法不僅能幹淨地將表示標記與代碼分開，而且模板隻進行一次編譯（通常編譯為 JVM 字節碼），以後可以重用，從而使它們擁有極佳的性能特征。”
我用Rope for java替代了StringBuffer做XML生成，效率提升在5%-30%左右，xml字符串不是很長，這個提升顯然有限，也帶來了不必要的複雜度。因此最後還是用Velocity模板引擎來生成XML，測試的結果效率並沒有多少改善，但是顯然更容易維護和開發了。回到Rope的話題，我用Ruby實現了個版本，Rubyforge上有一個Rope的實現，但是看了源碼，與paper所述算法有點差異，因此照著Rope for java也實現了一個Rope4r。測試的結果證明在長字符串的累積操作上，Rope4r的append比之String的+=性能可以快上3倍左右，而如果采用String的<<操作，不是immutable的，當然是最快了；比較鬱悶的是slice和insert操作都比String的慢上幾倍，因為Ruby的String、Array的內建對象都是直接用c寫成並做了優化的，我猜測原因在這。
文章轉自莊周夢蝶 ，原文發布時間2008-05-05
最後更新：2017-05-17 18:01:45