Joshua Bloch, 獲得過Jolt最暢銷獎的《Effective Java》的作者, 是Sun Microsystems的杰出工程師和Transarc的資深系統(tǒng)設(shè)計師, J2SE 5.0 Tiger的代言人和領(lǐng)路人, 也是還是JSR166的發(fā)起人之一..
后來, Joshua Bloch去了Google, 成為了
Google的首席工程師Joshua Bloch擁有卡耐基.梅隆大學(xué)(CMU)計算機(jī)科學(xué)的博士學(xué)位。
在
最近Joshua Bloch的一篇文章里, Joshua Bloch回憶了當(dāng)年在CMU上課的時候, vividly Jon Bentley
第一節(jié)算法課, 就要求所有剛進(jìn)來的PHD學(xué)生, 每人都寫一個二分查找算法. 然后發(fā)現(xiàn), 多數(shù)人的算法都存在BUG, 這在當(dāng)時給了Joshua
Bloch 一個很深的印象..
在之后, Joshua Bloch 負(fù)責(zé)java.util.Arrays 代碼編寫的時候, 采用了Bentley 在<<Programming Pearls >>一書中的二分查找算法, 結(jié)果在8年后的今天,
Joshua Bloch 發(fā)現(xiàn), 這里面原來還是有一個BUG.
問題到底是出在哪里? 竟然逃過了Bentley 和Joshua Bloch 的雙重檢測?
一起來看看java.util.Arrays的代碼:
1: public static int binarySearch(int[] a, int key) {
2: int low = 0;
3: int high = a.length - 1;
4:
5: while (low <= high) {
6: int mid = (low + high) / 2;
7: int midVal = a[mid];
8:
9: if (midVal < key)
10: low = mid + 1;
11: else if (midVal > key)
12: high = mid - 1;
13: else
14: return mid; // key found
15: }
16: return -(low + 1); // key not found.
17: }
這是很經(jīng)典的一個二分查找算法.
bug出現(xiàn)在第6行:
6: int mid =(low + high) / 2;
在一般情況下, 這個語句是不會出錯的, 但是, 當(dāng)low+high的值超過了最大的正int值 (231 - 1) 的時候, mid會變成負(fù)值, 這個時候, 會拋出ArrayIndexOutOfBoundsException 異常..所以當(dāng)一個數(shù)組包含超過2的30次方 個元素的時候, 就很可能會帶來問題... 當(dāng)然, 在一般的應(yīng)用里面, 很少數(shù)組會包含那么多元素, 但是現(xiàn)在這樣的情況已經(jīng)越來越多了, 比如Google的海量運(yùn)算..
那如何解決這個問題?
很簡單, 修改這行語句為:
6: int mid = low + ((high - low) / 2);
或者
6: int mid = (low + high) >>> 1;
在c或者c++中, 則可以如下實現(xiàn):
6: mid = ((unsigned) (low + high)) >> 1;
這個問題告訴我們, 無論什么時候, 我們都不要想當(dāng)然我們的程序是完美的. 我們需要細(xì)心的設(shè)計,測試再測試,符合規(guī)范的方法等等...對此, 你有什么經(jīng)驗和大家分享嗎?
同樣給我們帶來的思考是: 8年了, java.util.Arrays 竟然存在這樣一個bug, 這不得不讓我們對JDK本身的測試性, 穩(wěn)定性 懷有疑問.. 將來又會有多少個類似的bug出現(xiàn)呢?