Java 中一个你不常用,但是关键时刻可以帮我们提升性能的一个知识点

最近阿粉在实现一个功能的时候,遇到了一个性能问题,一个方法在某些场景下运行时长达到了 4s 多,虽然说业务功能是实现了,但是不管是从业务的角度还是作为一个有追求的程序员,都是不能接受的,所以优化这个方法势在必行。在优化的过程中就用到了本文要说明的一个知识点,看阿粉慢慢道来。

在提供优化代码之前,先简单的描述一下这个方法做的事情,要做的事情很简单,就是返回一个整数,整数表示的是二进制数组中有多少个 1。给到了入参是一个 Map<String, String> 其中 key 我们不关心,value 是二进制字符串。需要注意的是二进制字符串的长度很长,10 万位左右;并且长度不一定相同。我们需要做的事情就是将所有的二进制字符串数组进行或运算,得到一个最终的二进制数组,然后计算其中 1 的个数进行返回。

根据我们上面的分析,列一下我们写代码的步骤:

  1. 因为我们要按位进行或运算,所以二进制的长度应该要一样才行,我们取最长的二进制的长度为 maxLength,所有没有这么长的二进制字符串,我们需要进行前面补 0 ;
  2. 将所有的二进制字符串按位进行或运算;
  3. 遍历最终的数组输出 1 的个数;

按照这个思路,我们可以写出下面的代码,maxLength 作为入参传递到我们的方法中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public static long version1(Map<String, String> map, int maxLength) {
        long result = 0L;
        if (!CollectionUtils.isEmpty(map)) {
            //1. 将长度不够 maxLength 长的二进制字符串前面补 0
            for (Map.Entry<String, String> m : map.entrySet()) {
                if (m.getValue().length() < maxLength) {
                    StringBuilder newValue = new StringBuilder();
                    for (int i = 0; i < maxLength - m.getValue().length(); i++) {
                        newValue.append(0);
                    }
                    newValue.append(m.getValue());
                    map.put(m.getKey(), newValue.toString());
                }
            }
            //2. 将每个关键字的二进制字符串按位进行或 | 运算
            Integer[] sum = new Integer[maxLength];
            for (int i = 0; i < maxLength; i++) {
                sum[i] = 0;
            }
            for (Map.Entry<String, String> m : map.entrySet()) {
                for (int i = 0; i < maxLength; i++) {
                    String substring = m.getValue().substring(i, i + 1);
                    sum[i] = sum[i] | Integer.parseInt(substring);
                }
            }
            //3. 统计计算结果中 1 的个数
            for (Integer integer : sum) {
                result += integer;
            }
        }
        return result;
    }

简单分析一下,在第一步的时候我们构造了一个 StringBuilder 对象,根据二进制字符串的长度和 maxLength 的长度,在前面进行补 0 操作,两者相差多少就在前面补多少个 0,然后将原始的二进制补到最后,得到一个新的二进制字符串;第二步我们遍历 Map,将二进制字符串中的每一位与之前构造的全是 0 的 sum 数组进行或运算操作,并将结果写到 sum 数组对应的位置上,因为经过第一步的补 0 这里 Map 中所有的 value 的长度是一样的;第三步再遍历 sum 数组,将每一位累加起来,得到的结果就是我们需要的结果,因为 sum 数组中只有 1 和 0,所以总和就是 1 的个数。

代码写到这里,内心毫无波澜,没有一丝丝感觉,毕竟只要思路清晰,代码的实现都是小事。

然而就当把这个功能发到测试环境的时候,测试妹妹反馈某些情况下在前端页面等待的时间太长了,loading 的小按钮一直转不停,往往要 4,5 秒的时间才能得到结果,体验太差了。

抱着以用户体验为目标的决心(其实是怕被扣工资),阿粉看了一下测试用例,追踪了一下代码结果发现当这个方法中 map 中的 key 达到 1000+ 的时候,整个方法竟然执行了4s 多!是可忍孰不可忍,作为一个有追求的程序员怎么能让这种情况发生了,不得已阿粉走上了优化这个方法的道路。

优化之前我们当然需要知道有哪些可以优化的地方,看下这段代码,发现里面好多 for 循环,毫无疑问我们的优化目标就是降低 for 循环的个数以及次数。

仔细看了一下代码,我们想一想真的有必要要先将每个二进制字符串进行前面补 0 的动作吗?是不是可以在进行或运算的时候发现位数不够的时候自动补 0 呢?还有就是我们真的有必要在最后遍历 sum 数组,得到 1 的个数吗?因为是或运算,只要 sum[i] 是 1 了,或运算得到的结果就一定是 1 那这个时候是不是就可以得到结果呢?

带着这两个问题,将代码优化成了下面的样子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public static long version2(Map<String, String> map, int maxLength) {
        long result = 0L;
        if (!CollectionUtils.isEmpty(map)) {
            Integer[] sum = new Integer[maxLength];
            for (int i = 0; i < maxLength; i++) {
                sum[i] = 0;
            }
            // 1. 将长度不够 maxLength 长的二进制字符串前面补 0
            // 2. 并将每个关键字的二进制字符串按位进行或 | 运算
            for (Map.Entry<String, String> m : map.entrySet()) {
                String value = m.getValue();
                for (int i = maxLength - 1; i >= 0; i--) {
                    char c;
                    int index = value.length() - i - 1;
                    if (index < 0) {
                        c = '0';
                    } else {
                        c = value.charAt(index);
                    }
                    //3. 统计计算结果中 1 的个数
                    int temp = sum[i];
                    sum[i] = sum[i] | Integer.parseInt(String.valueOf(c));
                    if (temp == 0 && sum[i] == 1) {
                        result += 1;
                    }
                }
            }
        }
        return result;
    }

简单分析一下,我们可以从数组的最后一位开始进行按位或运算,这样当得到的 index 小于 0 的时候,表示该二进制数组已经遍历完了,那么这个时候如果还没有达到 maxLength 的长度,我们就补 0,用 0 进行或运算;同时我们在进行或运算的时候,通过记录 sum[i] 在或运算前和或运算后差异来记录 1 的个数,我们只记录或运算前 sum[i] == 0 或运算后 sum[1] == 1 的值,就是我们需要的结果。

经过我们优化后的代码,首先从 for 循环的个数来看就已经减少了,我们测试一下效果如下,这里因为二进制的数组很长,不能放到公众号文章里面,就简化了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void main(String[] args) {
    String binaryString1 = "1000101010010101010101010100110101010101001001010101010101...";
        Map<String, String> map = new HashMap<>(16);
        for (int i = 0; i < 1500; i++) {
            map.put("key_" + i, binaryString1);
        }
        int maxLength = 0;
        for (Map.Entry<String, String> m : map.entrySet()) {
            maxLength = Math.max(maxLength, m.getValue().length());
        }
        long start1 = System.currentTimeMillis();
        long aLong1 = version1(map, maxLength);
        System.out.println("version1:" + aLong1 + ":" + (System.currentTimeMillis() - start1));

        long start2 = System.currentTimeMillis();
        long aLong2 = version2(map, maxLength);
        System.out.println("version1:" + aLong2 + ":" + (System.currentTimeMillis() - start2));    
}

从测试结果我们可以看到,当 map size 在 1000 的时候,version1 耗费了 4034ms,version2 耗费了 2090ms,性能提升接近 2 倍说明我们的优化还是有效果的。

事情到了这里,你以为就结束了吗?那就错了,因为还没有提到阿粉前面说的知识点,下面重点来了,请注意看。version2 的代码我们能不能再优化了?不管能不能再优化,有一行代码看起来总是让人很不爽,那就是sum[i] = sum[i] | Integer.parseInt(String.valueOf(c)); 这一行,将 char 字符,转换成 String,再通过 Integer.parseInt() 转成 int 的 0 或者 1 来进行或运算。很容易让人想到,这里经过几层的包装转换,是很浪费资源的,所以这里也是我们优化的点。

这一行的目标是进行或运算,Integer.parseInt(String.valueOf(c)) 的目标就是将 char 的 0 或者 1 转成 int 的 0 或者 1。那为什么我们不直接用 c ?然后我们测试了一下下面的代码,结果跟我们想象的不太一样,但是这个结果也是可以用的,我们再后面减掉一个 48 是不是就可以了呢?得到的就是 0 和 1 了。

经过上面的测试,我们 version3 版本的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public static long version3(Map<String, String> map, int maxLength) {
        long result = 0L;
        if (!CollectionUtils.isEmpty(map)) {
            Integer[] sum = new Integer[maxLength];
            for (int i = 0; i < maxLength; i++) {
                sum[i] = 0;
            }
            // 1. 将长度不够 maxLength 长的二进制字符串前面补 0
            // 2. 并将每个关键字的二进制字符串按位进行或 | 运算
            for (Map.Entry<String, String> m : map.entrySet()) {
                String value = m.getValue();
                for (int i = maxLength - 1; i >= 0; i--) {
                    char c;
                    int index = value.length() - i - 1;
                    if (index < 0) {
                        c = '0';
                    } else {
                        c = value.charAt(index);
                    }
                    //3. 统计计算结果中 1 的个数
                    int temp = sum[i];
                    sum[i] = sum[i] | ((int) c - 48);
                    if (temp == 0 && sum[i] == 1) {
                        result += 1;
                    }
                }
            }
        }
        return result;
    }

测试结果如下:

我们发现在同样大小的情况下,version3 版本直接进入到了 1 秒了,只用了 746ms,这次的优化性能提升了接近 5.5 倍!至此此次的性能优化终于画上了句号。

相信看到这里的小伙伴也知道了阿粉前面提到的知识点是什么了,那就是 char 类型可以跟 int 做转换,其实这就是我们学编程之初学到的 ASCII 码,可能学习的时候并没有想过要怎么用,当真正用到的时候就会发现真香!

总结一下今天阿粉给大家介绍了如果将一个运行 4s 多的方法,优化到了 800ms 以内,通过实战介绍了 ASCII 在我们日常工作中的应用。如果大家觉得看了文章的内容有收获,欢迎小伙伴们收藏,点赞,评论,转发,每一次互动都是对阿粉的鼓励。

文章中的源码和 ASCII 对照表,阿粉以及放在公众号后台了,回复关键字【ASCII】即可获得。

Java Geek Tech wechat
欢迎订阅 Java 极客技术,这里分享关于 Java 的一切。