深入StringBuffer
作者:eckel_cn
最近,閑暇之余,重新整理自用的StringUtil類,在整理到repeat方法(重復字符串)時,發現其存在效率問題,便打算重新寫一下,卻發現了一系列以前沒太注意的東西,覺得很有必要寫下來.
初一看,就能發現一點問題,當n很大,達到一定大小,就能使堆棧溢出.出現OutOfMemery錯誤.
那如何避免這個問題呢,我馬上想到了,既然StringBuffer和String一樣內部都是在操作char數組,
那我就自己直接操作char數組,在最少的循環里面,填充char數組,代碼如下:
1
public static String repeat2(String str, int n) 
{
2
int len = str.length();
3 int maxlen = len * n;
4 char[] chars = new char[len * n];
5 str.getChars(0, len, chars, 0);
6 int count = len;
7 int copyLen = 0;
8
while ((copyLen = maxlen - count > count ? count : maxlen - count) > 0) {
9 System.arraycopy(chars, 0, chars, count, copyLen);
10 count += copyLen;
11
}
12 String outstr = new String(chars);
13 return outstr;
14
} 測試后,發現,循環控制在了最少,但是,性能卻還不如repeat1,也許你會和我一樣開始很驚訝,但看了
StringBuffer的實現后,發現repeat2的實現中,將char數組,轉換為String,是效率多么低的事情,這個過程需要在String內部重新創建一個char數組,然后把傳進去的char數組,復制給它.而repeat1中為什么沒有這個性能問題呢,其實這就是要歸功于SUN在實現StringBuffer中的一個重要屬性:shared,當你使用StringBuffer后,想得到String時,String會共享StringBuffer中的char數組,這樣一來,性能非常高.
共享會不會帶來副作用呢,SUN的實現當然考慮到了,在改變StringBuffer時,如果這個StringBuffer
有其他String共享它的char數組時,StringBuffer就把這個char數組讓給String,自己重新復制一份使用.
既然問題發現了,我又換了種算法來實現,同樣也是把循環控制在最少,同時解決轉換帶來的效率低下問題.
1public static String repeat3(String str, int n) {
2 // if input string is null,return null.
3 if (null == str) {
4 return null;
5 }
6 final int strlen = str.length();
7 // if repeat number is less than two or given string's length is zero,
8 // then return the givien string.
9 if (2 > n || 0 == strlen) {
10 return str;
11 }
12 // assigns the enough size for the string buffer.
13 StringBuffer strBuf = new StringBuffer(strlen * n);
14 // get odd length flag.
15 final boolean oddLen = n % 2 == 1 ? true : false;
16 // calculates the grow times.
17 final int growTimes = (int) Math.floor(Math.log(n) / Math.log(2));
18 // adds one given string.
19 strBuf.append(str);
20 // grows until more than half of the repeat count.
21 for (int i = 0; i < growTimes; i++) {
22 strBuf.append(strBuf);
23 if (Math.pow(2, i - 1) * 2 < n && Math.pow(2, i) * 2 >= n) {
24 break;
25 }
26 }
27 // reset the string buffer's length to half of the repeat count.
28 strBuf.setLength(strlen * Math.round(n / 2));
29 // grows to the repeat count.
30 strBuf.append(strBuf);
31 if (oddLen) {
32 strBuf.append(str);
33 }
34 String returnStr = new String(strBuf);
35 return returnStr;
36}
37
算法實現,再次測試,測試發現,在規模不是特別大的情況下,repeat3的效率要明顯優于前兩個,但在規模大的情況下,會變的差不多,怎么會這樣的呢,再次進行深入調查,結果發現是SUN的System.arrayCopy這個方法有性能問題,特別是當要復制的長度特別大的情況下,性能下降的比較快,再換個IBM的JDK實現,又發現,IBM的這個方法的實現要比SUN有改進.
真是一次比較有意思的深入StringBuffer,在實際運用中repeat3完全可以代替上面兩種方法.