934
技術社區[雲棲]
寫程序很難之去除字符串的空白字符
在做性能調優時，用JProfiler測試Web應用的性能，發現有個replaceBlank函數占用了10%的CPU時間，進去看了下，是個簡單的用正則去除XML文檔裏空白字符串的功能。但是這個簡單功能卻消耗了10%的性能。
在Web應用裏，去掉空白字符串，似乎是個簡單的功能，但是真正寫起來，卻也有些麻煩事。總結下。
方式一：正則表達式
https://stackoverflow.com/questions/5455794/removing-whitespace-from-strings-in-java
有兩種寫法：
s.replaceAll("\\s+", "");
s.replaceAll("\\s", "");至於具體哪一種比較好，和具體的場景有有關。有連續空白字符串的選擇每一種，如果是空白字符串都隻有一個的話，就選擇第二種。個人傾向於第一種。
正則表達式是比較慢的，比下麵的方法要慢3到4倍以上。
方式二：org.springframework.util.StringUtils.trimAllWhitespace
具體的實現代碼如下：
public static String trimAllWhitespace(String str) {
if (!hasLength(str)) {
return str;
}
StringBuilder sb = new StringBuilder(str);
int index = 0;
while (sb.length() > index) {
if (Character.isWhitespace(sb.charAt(index))) {
sb.deleteCharAt(index);
}
else {
index++;
}
}
return sb.toString();
}
看起來，沒有什麼問題，但是程序員的直覺：deleteCharAt函數是怎麼實現的？應該不會有什麼高效的算法可以實現這樣的。
果然，實現代碼如下：
public AbstractStringBuilder deleteCharAt(int index) {
if ((index < 0) || (index >= count))
throw new StringIndexOutOfBoundsException(index);
System.arraycopy(value, index+1, value, index, count-index-1);
count--;
return this;
}顯然，過多地調用System.arraycopy會有性能問題。
方式三：改為調用StringBuilder.append 函數
static public String myTrimAllWhitespace(String str) {
if (str != null) {
int len = str.length();
if (len > 0) {
StringBuilder sb = new StringBuilder(len);
for (int i = 0; i < len; ++i) {
char c = str.charAt(i);
if (!Character.isWhitespace(c)) {
sb.append(c);
}
}
return sb.toString();
}
}
return str;
}這個是最開始的思路。實際測試了下，發現大部分情況上，要比方式二效率高。
但是在某些情況，比如"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa"，這種隻有一個空白字符的，效率要慢。
方式四：結合二，三，隻用System.arraycopy複製部分內存
第二種方式，在調用deleteAt時，要整個拷貝後麵的所有字符串，顯然在字符串很長的情況下，效率會降低。於是考慮隻複製部分內存。
用兩種pos來標記哪一部分是連續的非空白字符串。
static public String myTrimAllWhitespace3(String str) {
if (str != null) {
int len = str.length();
if (len > 0) {
char[] src = str.toCharArray();
char[] dest = new char[src.length];
int destPos = 0;
for (int pos1 = 0, pos2 = 0; pos2 < src.length;) {
if (Character.isWhitespace(src[pos2])) {
if (pos1 == pos2) {
pos1++;
pos2++;
} else {
System.arraycopy(src, pos1, dest, destPos, pos2
- pos1);
destPos += (pos2 - pos1);
pos2++;
pos1 = pos2;
}
} else {
pos2++;
}
if (pos2 == src.length) {
if (pos1 != pos2) {
System.arraycopy(src, pos1, dest, destPos, pos2
- pos1);
destPos += (pos2 - pos1);
}
return new String(dest, 0, destPos);
}
}
}
}
return str;
}
方式五：去掉StringBuilder，直接操作char[]
在寫完方式四，之後，測試發現效率在中間，和方式二，三相比，不好也不壞。似乎找到了一個平衡點。
但是忽然想到，既然在方式四中不直接操作char[]數組，為何不在方式二也這麼做？於是有了：
static public String myTrimAllWhitespace2(String str) {
if (str != null) {
int len = str.length();
if (len > 0) {
char[] dest = new char[len];
int destPos = 0;
for (int i = 0; i < len; ++i) {
char c = str.charAt(i);
if (!Character.isWhitespace(c)) {
dest[destPos++] = c;
}
}
return new String(dest, 0, destPos);
}
}
return str;
}
第六點：Unicode
上麵的幾種方式都隻能處理大部分的情況，對於部分Unicode字符串，可能會有問題。
因為本人對這個比較敏感，最後寫了個Unicode字符的處理：
static public String myTrimAllWhitespace3(String str) {
if (str != null) {
int len = str.length();
if (len > 0) {
char[] src = str.toCharArray();
char[] dest = new char[src.length];
int destPos = 0;
for (int pos1 = 0, pos2 = 0; pos2 < src.length;) {
if (Character.isWhitespace(src[pos2])) {
if (pos1 == pos2) {
pos1++;
pos2++;
} else {
System.arraycopy(src, pos1, dest, destPos, pos2
- pos1);
destPos += (pos2 - pos1);
pos2++;
pos1 = pos2;
}
} else {
pos2++;
}
if (pos2 == src.length) {
if (pos1 != pos2) {
System.arraycopy(src, pos1, dest, destPos, pos2
- pos1);
destPos += (pos2 - pos1);
}
return new String(dest, 0, destPos);
}
}
}
}
return str;
}這個處理Unicode的非常慢。。Java的String類並沒有暴露足夠多的函數來處理Unicode，所以處理起來很蛋疼。
總結：
測試代碼在：
https://gist.github.com/hengyunabc/a4651e90db24cc5ed29a
我的電腦上測試最快的代碼是方式五裏的。
可能在某些特殊情況下，方式四中用System.arraycopy來複製標記兩段內存會快點，但這個算法太複雜了，得不償失。
本人傾向於符合直覺，而且效率線性的算法。
給Spring提了個path，一開始是方式三的代碼，但是在某些情況下效率不高，導致周末心神不寧。。於是就有了後麵的幾種方式。
一個簡單的功能，直正實現起來卻也不容易，所以我盡量避免寫Util類和方式，因為保證代碼的質量，性能，不是一件容易的事。
https://github.com/spring-projects/spring-framework/pull/562
最後更新：2017-04-03 07:57:05