カーネギーメロン大学でのジョン・ベントレーの最初の講義で、彼は焼きたての大学院生にバイナリ検索関数を書くように頼んだことを鮮明に覚えています。 彼は解決策の1つを取り上げてボード上で分解しましたが、もちろん、他の多くの試みと同様に、それは間違いであることが判明しました。 この事件は私にとって、彼の著書「Pearls of Programming」の明確なデモンストレーションでした。 教訓は、プログラム内の不変式を注意深く整理することです。
そして今、2006年です。 Bentleyがテストとテストによって正式に証明したバイナリ検索プログラムにエラーが含まれていることを知ってショックを受けました。 私が過ちを見つけたとは思わない 実際、そのような間違いは何十年もテスターを逃れる可能性があります。 さらに、私がJDKのために書いたバイナリ検索も約9年間バグがありました。 そして今、彼女が誰かのプログラムを破ったとき、彼女はサンに報告されました。
それで、間違いは何ですか？ これは、Javaでの標準のバイナリ検索です。これは、
java.util.Arrays
用に作成したものの1つです。
public static int binarySearch(int[] a, int key) { int low = 0; int high = a.length - 1; while (low <= high) { int mid = (low + high) / 2; int 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. }
6行目のエラー：
int mid = (low + high) / 2;
プログラミングの真珠では、Bentleyは同様の行を犠牲にして、「mをこれらの数値の平均に等しく設定し、最も小さい整数に丸めた」と書いています。 一見、すべてが問題ありませんが、十分な大きさの
low
および
high
場合（つまり、合計が2 31 -1を超える場合）エラーが発生します。 それらの合計は負の数になり、
mid
も負になります。 Cでは、これにより、予想外の結果を伴う配列外のメモリアクセスが発生しますが、Javaは
ArrayIndexOutOfBoundsException
スローし
ArrayIndexOutOfBoundsException
。
このエラーは、2 30 （10億のオーダー）を超える非常に大きな配列でのみ発生します。 80年代、この本がその日の光を見たとき、これは不可能だったでしょうが、今ではGoogle（そして実際、あらゆるプロジェクト）でこれは一般的なことです。 Bentleyは「Pearls of Programming」に次のように書いています。「1946年にバイナリ検索の最初のバージョンが公開されましたが、nのすべての値を処理する正しいコードは1962年に登場しました。」 実際、これまでのところ、最も人気のある言語の実装でも、正しいコードに遭遇することはほとんどありませんでした。
では、このコードをどのように書くのでしょうか？ 6行目は次のように書き換えることができます。
int mid = low + ((high - low) / 2);
ただし、おそらく、このオプションはより高速で簡単です。
int mid = (low + high) >>> 1;
C / C ++には>>>演算子はありませんが、次のように記述できます。
mid = ((unsigned int)low + (unsigned int)high)) >> 1;
さて、これでエラーがもうないことが確実にわかりました。 まあ...おそらく。 プログラムの正確性を完全に厳密に証明するためには、可能なすべての入力データでテストする必要がありますが、実際にはこれはほとんど実行できません。 また、並列コンピューティングの場合はさらに悪いことです。考えられるすべての内部状態についてプログラムをテストする必要があります。 試してはいけません。
このエラーは、マージソートおよびその他の分割統治アルゴリズムで発生する可能性があります。 このようなアルゴリズムを実装している場合は、エラーが不快な結果をもたらすまで、それらを再確認してください。 個人的に、この間違いは、私が毎日使用している本当に複雑なシステムは言うまでもなく、もう少し控えめで、小さくて馴染みのあるコードの証拠にさえ頼らないことを教えてくれました。
プログラマーは、何らかの方法でコードを改善する必要があります。 正確なアーキテクチャ設計が適切です。 アルゴリズムのテストと正式な分析はさらに優れています。 静的分析とコード修正は素晴らしいです。 しかし、最善を尽くしても、半世紀にわたって存続するとらえどころのないバグからこれを個別に救うことはできません。 きちんとした防御的なプログラミングを練習し、警戒する必要があります。
更新2008年2月17日フィンランド研究センターノキアアントワーヌトレックス（アントワーヌトリュクス）のチーフエンジニアは、CおよびC ++の修正案は正しい動作を保証しないと述べました。これらの言語の標準により、加算中の算術オーバーフローは未定義の結果をもたらすためです。 この欠陥を修正したので、プログラムが正しく機能していることを確認します。 ;）
参照：
- 「 プログラミングの真珠 」-ぜひお勧めします。必ず購入してください！ （翻訳者から： ロシア語の翻訳本から引用）
- JDKバグトラッカーのエラーメッセージ
- Salvatore Ruggieriによる 2003年の記事で、より一般的ではあるが、おそらくそれほど興味深い問題ではない：任意の符号の2つの整数の真ん中を見つける。 この記事はパフォーマンスの問題に対処しておらず、提案されたソリューションは内部マージソートサイクルに十分な速度ではありません。