新的起點 新的開始

          快樂生活 !

          java.util.Arrays的BUG - 二分搜索算法

                     Joshua Bloch, 獲得過Jolt最暢銷獎的《Effective Java》的作者, 是Sun Microsystems的杰出工程師和Transarc的資深系統設計師, J2SE 5.0 Tiger的代言人和領路人, 也是還是JSR166的發起人之一..

          后來, Joshua Bloch去了Google, 成為了Google的首席工程師

          Joshua Bloch擁有卡耐基.梅隆大學(CMU)計算機科學的博士學位。

          在 最近Joshua Bloch的一篇文章里, Joshua Bloch回憶了當年在CMU上課的時候, vividly Jon Bentley 第一節算法課, 就要求所有剛進來的PHD學生, 每人都寫一個二分查找算法. 然后發現, 多數人的算法都存在BUG, 這在當時給了Joshua Bloch 一個很深的印象..

          在之后, Joshua Bloch 負責java.util.Arrays 代碼編寫的時候, 采用了Bentley 在<<Programming Pearls >>一書中的二分查找算法, 結果在8年后的今天, Joshua Bloch 發現, 這里面原來還是有一個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:     }


          這是很經典的一個二分查找算法.

          bug出現在第6行:

          6:             int mid =(low + high) / 2;

          在一般情況下, 這個語句是不會出錯的, 但是, 當low+high的值超過了最大的正int值 (231 - 1) 的時候, mid會變成負值,  這個時候, 會拋出ArrayIndexOutOfBoundsException 異常..


          所以當一個數組包含超過2的30次方 個元素的時候, 就很可能會帶來問題... 當然, 在一般的應用里面, 很少數組會包含那么多元素, 但是現在這樣的情況已經越來越多了, 比如Google的海量運算..

          那如何解決這個問題?

          很簡單, 修改這行語句為:

          6:             int mid = low + ((high - low) / 2);
          或者
          6:             int mid = (low + high) >>> 1;


          在c或者c++中, 則可以如下實現:
          6:             mid = ((unsigned) (low + high)) >> 1;


          這個問題告訴我們, 無論什么時候, 我們都不要想當然我們的程序是完美的. 我們需要細心的設計,測試再測試,符合規范的方法等等...對此, 你有什么經驗和大家分享嗎?

          同樣給我們帶來的思考是: 8年了, java.util.Arrays 竟然存在這樣一個bug, 這不得不讓我們對JDK本身的測試性, 穩定性 懷有疑問.. 將來又會有多少個類似的bug出現呢?

          posted on 2007-04-05 16:17 advincenting 閱讀(506) 評論(0)  編輯  收藏


          只有注冊用戶登錄后才能發表評論。


          網站導航:
           

          公告

          Locations of visitors to this pageBlogJava
        1. 首頁
        2. 新隨筆
        3. 聯系
        4. 聚合
        5. 管理
        6. <2025年7月>
          293012345
          6789101112
          13141516171819
          20212223242526
          272829303112
          3456789

          統計

          常用鏈接

          留言簿(13)

          隨筆分類(71)

          隨筆檔案(179)

          文章檔案(13)

          新聞分類

          IT人的英語學習網站

          JAVA站點

          優秀個人博客鏈接

          官網學習站點

          生活工作站點

          最新隨筆

          搜索

          積分與排名

          最新評論

          閱讀排行榜

          評論排行榜

          主站蜘蛛池模板: 深州市| 纳雍县| 富蕴县| 信阳市| 烟台市| 辰溪县| 二手房| 彭山县| 武乡县| 白玉县| 武平县| 盐亭县| 潞城市| 泰来县| 凤阳县| 年辖:市辖区| 资中县| 山丹县| 万全县| 手游| 辽宁省| 鲁山县| 集贤县| 阿勒泰市| 新安县| 资溪县| 温州市| 两当县| 镇巴县| 临高县| 兴安盟| 平南县| 建德市| 彝良县| 景宁| 松江区| 新邵县| 逊克县| 广宁县| 凉城县| 交城县|