二分查找真的那么快吗？

红太狼 2022-09-06 04:55 132阅读 0赞

# 1. 背景 #

今天刷博客，无意中看到一个题目，对于一个同样升序排列的字符串和字节数组，分别使用`String.indexOf()`和`Arrays.binarySearch`查询特定字符，前者竟然比后者快？对于一个升序的数组，二分查找可是最强的武器，怎么还被顺序查找的indexOf干掉了。带着这个好奇，我做了一个无聊的测试。

# 2. 先上实例代码 #

public class StringCharCompare { 
        long count = 100000000;
        private String testStr = "abcdefg";
        private char[] testChar = { 'a','b','c','d','e','f','g'};
    
        @Test
        public void testString(){ 
            for (int i = 0; i < count; i++) { 
                testStr.indexOf('c');
            }
        }
        @Test
        public void testChar(){ 
            for (int i = 0; i < count; i++) { 
                Arrays.binarySearch(testChar,'c');
            }
        }
    }

# 3. 疯狂测试 #

## 3.1 随机测试 ##

我们随机找一个字符`e`进行测试，得到如下结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29ZaW5IZVpoaUd1YW5n_size_16_color_FFFFFF_t_70]  
好像真是这样的哈，`String.indexOf`竟然比`Arrays.binarySearch`快一倍。是不是很有意思。

## 3.2 了解源码 ##

在接下来测试之前，我们先了解一下各自的源码：

*  String.indexOf()

public int indexOf(int ch, int fromIndex) { 
            final int max = value.length;
            if (fromIndex < 0) { 
                fromIndex = 0;
            } else if (fromIndex >= max) { 
                return -1;
            }
            if (ch < Character.MIN_SUPPLEMENTARY_CODE_POINT) { 
                final char[] value = this.value;
                for (int i = fromIndex; i < max; i++) { 
                    if (value[i] == ch) { 
                        return i;
                    }
                }
                return -1;
            } else { 
                return indexOfSupplementary(ch, fromIndex);
            }
        }

上面核心代码就是10-13行那个for循环。

*  Arrays.binarySearch

private static int binarySearch0(char[] a, int fromIndex, int toIndex,
                                         char key) { 
            int low = fromIndex;
            int high = toIndex - 1;
            while (low <= high) { 
                int mid = (low + high) >>> 1;
                char midVal = a[mid];
                if (midVal < key)
                    low = mid + 1;
                else if (midVal > key)
                    high = mid - 1;
                else
                    return mid; // key found
            }
            return -(low + 1);  // key not found.
        }

以上的核心代码是4-13行，貌似二分查找代码量多一点哈。接下来我们继续测试：

## 3.3 首次命中 ##

为了做到首次命中，我们通过字符`a`验证`String.IndexOf()`方法，通过字符`d`验证`Arrays.binarySearch`方法。得到结果如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29ZaW5IZVpoaUd1YW5n_size_16_color_FFFFFF_t_70 1]  
哎呀，这次`Arrays.binarySearch`厉害了，竟然比`String.IndexOf()`快了一倍。在这里二分查找是不是发挥出巨大威力了？貌似并不是那么回事，因为他们都首次命中，谈不上二分查找的优势。我们数一下执行代码行数，`Arrays.binarySearch`也多很多，这是什么原因呢？如果我们仔细分析一下这两段代码，发现`String.IndexOf()`有一个很耗时的操作，`final char[] value = this.value`，它是要把数组复制一份出来，效率自然就低下来了。那么他为什么要来这次多次一举呢，直接使用成员变量的value不香吗？如果没有这些复制操作，首次命中也能战胜二分查找，它这么设计也是出于性能考虑。这里也是我的猜测(不一定正确)，主要也是性能考虑，因为成员变量的value在堆中，而复制过来的在方法栈，对于下面for循环的代码，从栈取肯定优于从堆中获取。

## 3.4 二次命中 ##

二次命中，对于`String.IndexOf()`，我们很容易确定为字符`b`,对于`Arrays.binarySearch`，根据源码，我们分析取`b`。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29ZaW5IZVpoaUd1YW5n_size_16_color_FFFFFF_t_70 2]  
这次`String.IndexOf()`占上风,大约快1倍。

## 3.5 三次命中 ##

三次命中，对于`String.IndexOf()`，我们很容易确定为字符`c`,对于`Arrays.binarySearch`，根据源码，我们分析取`b`。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29ZaW5IZVpoaUd1YW5n_size_16_color_FFFFFF_t_70 3]  
这次`String.IndexOf()`更厉害了,大于快2倍。

## 3.5 临界点 ##

经过多次试验，`String.IndexOf()`5此命中和`Arrays.binarySearch`的两次命中耗时接近。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29ZaW5IZVpoaUd1YW5n_size_16_color_FFFFFF_t_70 4]

# 4 总结 #

二分查找的优势在于对于一个随机的字符，它会以遍历尽量少的次数获取性能的优化，然而这毕竟有一个临界值。生活中也有很多这样的例子，比如步行和摩托车比谁快，如果是5m,我觉得人肯定快，因为摩托车起步需要开锁、启动、压离合、挂挡、松离合、加油，还有一个加速度，而步行只需一个接近于光速的反射弧。但是如果1公里，那就不一样了。再比如，二叉树要由于列表，但是有序数组又是它的克星。所以，`世界上没有最好的工具，只有最适合的工具`。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29ZaW5IZVpoaUd1YW5n_size_16_color_FFFFFF_t_70]: /images/20220829/41d3423455214cbda062e000943a6001.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29ZaW5IZVpoaUd1YW5n_size_16_color_FFFFFF_t_70 1]: /images/20220829/5c8bb716a19a4090b9ac03ec0a0e5e74.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29ZaW5IZVpoaUd1YW5n_size_16_color_FFFFFF_t_70 2]: /images/20220829/a27b323e14fa48db95bbc1c23423fe48.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29ZaW5IZVpoaUd1YW5n_size_16_color_FFFFFF_t_70 3]: /images/20220829/1049abcd65f24e16995179b1e2ab2948.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29ZaW5IZVpoaUd1YW5n_size_16_color_FFFFFF_t_70 4]: /images/20220829/3416c7a9d6284fde9bd9ce3b6deb76a1.png