过滤字符的性能调优?挤一挤还是有的-阿里云开发者社区

开发者社区> 开发与运维> 正文
登录阅读全文

过滤字符的性能调优?挤一挤还是有的

简介:

/*

*author: ahuaxuan(张荣华)

*date: 2010-05-28

*/

起因

前一段时间和其他系统集成, 另外一个系统对某个参数有一个限制,需要将字符串中的特殊字符过滤掉, 由于需要过滤的字符是对方定义的, 所以对方直接把他们系统中的过滤的代码给我了, 代码如下:

Java代码 复制代码 收藏代码
  1. private String escape(String s) {
  2. if (s == null) {
  3. return null;
  4. }
  5. StringBuilder sb = new StringBuilder(s.length());
  6. for (int i = 0; i < s.length(); i++) {
  7. char c = s.charAt(i);
  8. if (c == '\\' || c == '+' || c == '-' || c == '!' || c == '('
  9. || c == ')' || c == '^' || c == '[' || c == ']' || c == ':'
  10. || c == '{' || c == '}' || c == '~' || c == '*' || c == '?'
  11. || c == '|' || c == '&' || c == '>' || c == '<') {
  12. sb.append(“ ”);
  13. } else {
  14. sb.append(c);
  15. }
  16. }
  17. return sb.toString();
  18. }
private String escape(String s) {
        if (s == null) {
            return null;
        }

		StringBuilder sb = new StringBuilder(s.length());

      
		for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
          
            if (c == '\\' || c == '+' || c == '-' || c == '!' || c == '('
					|| c == ')' || c == '^' || c == '[' || c == ']' || c == ':'
					|| c == '{' || c == '}' || c == '~' || c == '*' || c == '?'
					|| c == '|' || c == '&' || c == '>' || c == '<') {
				sb.append(“ ”);
			} else {
                sb.append(c);
            }

		}

		return sb.toString();
	}

拿到代码之后, ahuaxuan没有作过多的思考, 而是直接把这段代码贴到自己的代码中, 事实证明它运行”良好”.今天重新审视这段代码的时候,发现还是有改进的余地.

分析

特征分析, 上面这段代码的主要作用是将字符串中出现的固定字符替换成空格, 这些需要替换的字符也是我们常见的字符.

面对这样一个需求, 有的程序员会想到replace方法,有的程序员会想到上面的多次||的方法(但是多次||的问题在于如果你的字符不是需要过滤的字符,那么程序就一直会执行到最后一个||,这绝对性能上的浪费阿), 也有的程序员会想到hash的方式. 其实我们的最终目的其实就是:

给定一个字符, 你怎么判断这个字符是否在某个常见的字符列表中.

你肯定不想用迭代, 你也肯定不想用if else if, 你可能比较喜欢用hash, 但是注意这里的”常见字符”这几个字.

是因为它们在ascii 码里所以它们才常见, 还是因为他们常见,所以放到ascii 码里呢, 但不管怎么样, 事实上它们确实是在ascii码里, 也就是说他们之中最大的都不会超过255.

所以这个时候, 我们的方案就浮出水面了, 由于我们只要检查每个char是否==这些常见的char就行了. 说到这里, 你是不是又想起了if else if, 这个只是思维的惯性, 如果你再把这些char想像成一个个数字呢.

本质和方案

于是需求就转换成了---在个数字段中, 找到某些我们预先定义的需要过滤的数字, 并将起替换成空格,而我们定义的数字都是小于255的.

在这样一个需求中, 最快的方式是啥咧, 数组是不, 比如说我们定义的需要过滤的数字是[2, 5], 我们的数字序列是1 2 3 4 5 10 11 110......

那么我们只要遍历这个数字, 然后判断这个数字在我们的过滤数组中是否存在. 我们的过滤数组怎么组织呢?

filterchars = [0, 0, 1, 0, 0, 1],

然后我们只需要判断filterchars[k] > 1就知道是个字符是否是需要过滤的字符了(当然这里要注意数组越界了).


代码如下:
Java代码 复制代码 收藏代码
  1. public int[] dic = new int[256];
  2. private String filterChars = "\\+-!()^[]:{}~*?|&><";
  3. /**
  4. * User: ahuaxuan
  5. * Date: 2010-5-28
  6. * Time: 13:17:11
  7. */
  8. public CharFilter() {
  9. for (int k = 0; k < filterChars.length(); k++) {
  10. //这里浪费了一些byte.
  11. char c = filterChars.charAt(k);
  12. if (c < 256) {
  13. dic[c] = 1;
  14. }
  15. }
  16. }
  17. public String newEscape(String abc) {
  18. if (abc == null) {
  19. return null;
  20. }
  21. StringBuilder rs = new StringBuilder(abc.length());
  22. for (int k = 0; k < abc.length(); k++) {
  23. char c = abc.charAt(k);
  24. if (c < 256 && dic[c] > 0) {
  25. rs.append(" ");
  26. } else {
  27. rs.append(c);
  28. }
  29. }
  30. return rs.toString();
  31. }
public int[] dic = new int[256];
    private String filterChars = "\\+-!()^[]:{}~*?|&><";

    /**
 * User: ahuaxuan
 * Date: 2010-5-28
 * Time: 13:17:11
 */
    public CharFilter() {
        for (int k = 0; k < filterChars.length(); k++) {
            //这里浪费了一些byte.
            char c = filterChars.charAt(k);
            if (c < 256) {
                dic[c] = 1;
            }
        }
    }


    public String newEscape(String abc) {
        if (abc == null) {
            return null;
        }

        StringBuilder rs = new StringBuilder(abc.length());
        for (int k = 0; k < abc.length(); k++) {
            char c = abc.charAt(k);
            if (c < 256 && dic[c] > 0) {
                rs.append(" ");
            } else {
                rs.append(c);
            }
        }

        return rs.toString();
    }

测试报告

下面我们来看看这段代码:

相同功能的两段代码, 运行一下测试, 测试方法如下:

Java代码 复制代码 收藏代码
  1. /**
  2. * User: ahuaxuan
  3. * Date: 2010-5-28
  4. * Time: 13:17:11
  5. */
  6. public static void main(String [] args) {
  7. for (int n = 0; n < 10; n++) {
  8. System.out.println("------------------------" + n);
  9. StringBuilder txt = new StringBuilder(1000);
  10. for (int k = 0; k < 100; k++) {
  11. txt.append(UUID.randomUUID().toString());
  12. }
  13. CharFilter pt = new CharFilter();
  14. String abc = txt.toString();
  15. long begin = System.currentTimeMillis();
  16. for (int k = 0; k < 10000; k++) {
  17. pt.escape(abc);
  18. }
  19. System.out.println("escape : " + (System.currentTimeMillis() - begin) + "ms");
  20. begin = System.currentTimeMillis();
  21. for (int k = 0; k < 10000; k++) {
  22. pt.newEscape(abc);
  23. }
  24. System.out.println("new escape : " + (System.currentTimeMillis() - begin) + "ms");
  25. }
  26. }
/**
 * User: ahuaxuan
 * Date: 2010-5-28
 * Time: 13:17:11
 */
    public static void main(String [] args) {
        for (int n = 0; n < 10; n++) {
            System.out.println("------------------------" + n);
            StringBuilder txt = new StringBuilder(1000);
            for (int k = 0; k < 100; k++) {
                txt.append(UUID.randomUUID().toString());
            }

            CharFilter pt = new CharFilter();
            String abc = txt.toString();
            long begin = System.currentTimeMillis();
            for (int k = 0; k < 10000; k++) {
                pt.escape(abc);
            }
            System.out.println("escape : " + (System.currentTimeMillis() - begin) + "ms");

            begin = System.currentTimeMillis();
            for (int k = 0; k < 10000; k++) {
                pt.newEscape(abc);
            }
            System.out.println("new escape : " + (System.currentTimeMillis() - begin) + "ms");
        }

    }

不到1k的一个文本, 每种方法调用100次, 最终得到的结果是:

ahuaxuan 写道
------------------------0
escape : 103ms
new escape : 67ms
------------------------1
escape : 60ms
new escape : 42ms
------------------------2
escape : 61ms
new escape : 48ms
------------------------3
escape : 58ms
new escape : 39ms
------------------------4
escape : 56ms
new escape : 39ms
------------------------5
escape : 80ms
new escape : 39ms
------------------------6
escape : 55ms
new escape : 40ms
------------------------7
escape : 55ms
new escape : 38ms
------------------------8
escape : 55ms
new escape : 38ms
------------------------9
escape : 59ms
new escape : 41ms

如果我们把对每个不到1K的文本的过滤调用上升到10000次, 那么测试结果是:

ahuaxuan 写道
------------------------0
escape : 627ms
new escape : 433ms
------------------------1
escape : 564ms
new escape : 390ms
------------------------2
escape : 624ms
new escape : 390ms
------------------------3
escape : 561ms
new escape : 385ms
------------------------4
escape : 564ms
new escape : 388ms
------------------------5
escape : 600ms
new escape : 391ms
------------------------6
escape : 559ms
new escape : 382ms
------------------------7
escape : 564ms
new escape : 394ms
------------------------8
escape : 573ms
new escape : 395ms
------------------------9
escape : 566ms
new escape : 406ms

文体大小和过滤次数上升之后, 优化之后的方法比原先的方法快了近200ms.

总结:

性能就像女人的胸, 挤一挤还是有的.

当然如果你觉得文中的手段是太入门级了, 那你可以看看ahuaxuan的这篇文章:

使用DFA实现文字过滤

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章
最新文章
相关文章