写程序很难之去除字符串的空白字符

在做性能调优时,用JProfiler测试Web应用的性能,发现有个replaceBlank函数占用了10%的CPU时间,进去看了下,是个简单的用正则去除XML文档里空白字符串的功能。但是这个简单功能却消耗了10%的性能。

在Web应用里,去掉空白字符串,似乎是个简单的功能,但是真正写起来,却也有些麻烦事。总结下。

方式一:正则表达式

http://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



相关文章

发表评论

Comment form

(*) 表示必填项

还没有评论。

跳到底部
返回顶部