另外昨天看到一篇 Joshua Bloch 的 binary search, merge sort 的實作 bug,Joshua Bloch 發現 Jon Bentley 的 Programming Pearls 書(1986, second edition 2000 )中的演算法,跟他在 JDK 實作 java.util.Array 的 binarySearch (存在九年的 bug) 同樣犯了 divide and conquer 取中間數的錯誤:
6: int mid =(low + high) / 2;
mid 可能遇到太大的 low 跟 high 造成 mid 發生 integer overflow,大於最大正整數 (2^31 - 1),這個 bug 可以藏這麼久的原因是之前沒有人測過這麼大量的 binary search 或 merge sort 解法是
6: int mid = low + ((high - low) / 2);
或用 Java 的 unsigned right shift, ">>>", (最高位補 0 確保為正整數)取代除以 2 較快些
6: int mid = (low + high) >>> 1;
C/C++ 參考解法如下:(參考 Nokia 的 Antonie Trux 指出 C89/90 跟 C++、C99 說明 signed integer 相加 overflow 的話是未定義行為,因此先轉型為 unsigned int)
6: mid = ((unsigned int)low + (unsigned int)high)) >> 1;
該文後面 Joshua Bloch 說明的是這個 bug 讓他學會謙虛,即使是我們認為理所當然的取平均都可能出錯,細心的設計、測試的重要性、正規方法、檢 視程式碼、靜態分析都是很棒的,任何單一方法絕對無法保證沒有 bug。即使我們竭盡全力解一個 bug,也可能要花上幾十年才解掉。因此寫程式必須小心、防衛並時時警覺。
沒有留言:
張貼留言