Google
ブログ(iiyu.asablo.jpの検索)
ホットコーナー内の検索
 でもASAHIネット(asahi-net.or.jp)全体の検索です。
 検索したい言葉のあとに、空白で区切ってki4s-nkmrを入れるといいかも。
 例 中村(show) ki4s-nkmr

ウェブ全体の検索

インターネットでPDFをワードやエクセル文書に変換! 「瞬簡PDF for Cloud」

古典的バイナリサーチアルゴリズムにバグ2006年06月05日 09時49分36秒

ASAHIネット(http://www.asahi-net.or.jp)のjouwa/salonからホットコーナー(http://www.asahi-net.or.jp/~ki4s-nkmr/ )に転載したものから。
---
 bajaさんから。
--- ここから ---
こんにちは、bajaといいます。
ちょっと面白い記事を見かけましたのでお知らせします。
古典的Binary Searchのアルゴリズムにバグがあったという話がGoogleReserch
の記事に載っていました。
実際SunのJDKのインプリも間違っていて修正されているようです。
今はプログラムの仕事はしていないので勘違いがあるかもしれませんが、サー
チをする対象の配列の数が2の30乗(10億)を超えてしまうとうまく動かない、
ということでしょうか?
それにしてもずいぶん長い間見つからなかったものですね。
--- ここまで ---

 その記事は、
http://googleresearch.blogspot.com/
GoogleResearchのブログ
にある、
Extra, Extra - Read All About It: Nearly All Binary Searches and
Mergesorts are Broken
です。
 バグは、バイナリサーチの分割点のピボットを計算するところ
int mid =(low + high) / 2;
で、low + highがオーバーフローするってことです。
 普通これは問題にならないんです。いまのほとんどのマシンは、intが32bit
だから、このアルゴリズムで、2 ^ 31 - 1というintの最大値を超えるような
ことはないから。
 でも、著者Joshua Blochが遭遇したのは、最大値を超えた現象だったんです
ね。
 Joshua Blochさんって聞いたことあるなあと思ったら、Effective Javaの著
者ですね。Sunにいたはずなのに、Googleに移ってたんですね。調べたら、
2004年ですね。
http://www.theserverside.com/news/thread.tss?thread_id=27163
Joshua Bloch leaves Sun and joins Google

 なお、「Effective Java」は、Javaプログラマ必読です。参考になることは
多かったです。Effectiveシリーズはほかもなかなかよくて、ぼくは、
「Effective C++」「More Effective C++」も勉強になりました。

http://www.amazon.co.jp/exec/obidos/ASIN/4894714361/showshotcorne-22/ref=nosim
ジョシュア・ブロック著、 柴田芳樹訳「Effective Java プログラミング言語
ガイド」
http://www.amazon.co.jp/exec/obidos/ASIN/4756118089/showshotcorne-22/ref=nosim
Scott Meyers著、吉川邦夫訳「Effective C++ 【改訂第2版】」
http://www.amazon.co.jp/exec/obidos/ASIN/4756118534/showshotcorne-22/ref=nosim
Scott Meyers著、安村通晃、飯田朱美、伊賀聡一郎訳「More Effective C++―
最新35のプログラミング技法」

 Googleは面白いこと、サイエンスをやってるから、いい人材がどんどん集ま
ってますね。ぼくが知ってるだけでも、Unix屋のRob Pike、Lisp屋のPeter
Norvigとかね。
 Microsoftは元々研究やサイエンスはやってなくて、その後Microsoft
Researchを作ったけど、やっぱ、Microsoftにお世話になりたくない人は、
Googleなんでしょう。
 Microsoftはどうしても商売ばっかり、それも独禁法違反のヤクザ会社のイ
メージがあるし(いま必死でテレビCMを流していいイメージを作ろうとしてい
ます)。Googleは大学の研究室の延長みたいな感じがしますからね。
 そんなGoogleのやり方を、単にベスト&ブライテスト戦略だといってしまう
と底が浅いかなと。「Web進化論」はそんな臭いがぷんぷんします。^-^;

http://www.amazon.co.jp/exec/obidos/ASIN/4480062858/showshotcorne-22/ref=nosim
梅田望夫著「ウェブ進化論 本当の大変化はこれから始まる」

 Peter NorvigのAIプログラミングの本には、SICPなどにあるバグの話が出て
ます。これも今回のと似た話で、みんな長い間そのまま使ってきたアルゴリズ
ムで、Norvigさんが指摘したそうです。また時間ができたら、書きますね。

 この記事に出ている「Programming Pearls」の初版は、以前、「プログラム
設計の着想」として翻訳が出ていました。いまは、
http://www.amazon.co.jp/exec/obidos/ASIN/4894712369/showshotcorne-22/ref=nosim
ジョンベントリー著、小林健一郎訳「珠玉のプログラミング―本質を見抜いた
アルゴリズムとデータ構造」
です。
 この本は、ソフトウェアをやる以上、必読書です。問題の捉え方、発想がい
かに大事か痛感させられます。幾何学で補助線一本うまく引くだけで問題が簡
単になるように、問題をどう捉えるか、その発想ひとつで、アホみたいに簡単
に解けることがあることを気づかせてくれます。

 この記事にあるように、merge sortもだめだろうというんだから、ピボット
を同じ手法で選んでいるquick sortなど、分割統治型のものは、たぶん、全部、
だめね(もちろんピボットの選び方はいろいろあるから、影響ないものもある
だろう)。
 それにしてもGoogle的世界では、2^30 の要素数が当たり前になってきてる
のね。すると、こういう何十年も見つからないバグが出ちゃうんですね。
 バイオインフォマティクスも超大量のデータを扱うので、気をつけよう。

 ついでといってはなんですが、先の記事の下にある
Statistical machine translation live
も面白い話で、この統計的機械翻訳という手法は、いままでの翻訳アルゴリズ
ムよりかなりいい訳が出るというので注目されています。
 いま出ている日経サイエンス2006年7月号には、「ここまできた機械翻訳」
という記事があり、この手法の解説が載ってます。もちろん、「Statistical
machine translation live」を書いたFranz Ochの名前も出てます。というか、
彼がこの手法の開拓者です。
 この前、コンピュータ将棋でBonanzaというメモリとプロセッサパワーさえあ
れば、比較的単純な手法でやるプログラムが優勝しましたが、統計的機械翻訳
の手法も似てます。
 例が多ければだんだんよくなるという、大数の法則というか、中心極限定理
というか。\(^O^)/
 だんだん、人間がやることなくなってくるよなあ。
http://www.amazon.co.jp/exec/obidos/ASIN/415011501X/showshotcorne-22/ref=nosim
カート・ヴォネガット・ジュニア著、浅倉久志訳「プレイヤー・ピアノ」(ハ
ヤカワ文庫SF)
をまた買ってきて読んでみようかな。

 ほかに、この号には、「トポロジカル量子コンピューター」の記事もあって、
これはまた奇想天外な面白い話。意外なことに?、Microsoftがこの研究に力
を入れています。

コメント

_ maoyam ― 2006年06月25日 11時16分45秒

自作のソフトウェアにも同じ間違いをやってしまっているのを見つけました。さっそく、修正しました。ありがとうございました。

_ siuye ― 2008年09月02日 19時47分30秒

このタイトルだとアルゴリズムにバグがあるように見えて良くないです.
弾さんも同様の書き方をされていてやっぱり良くないなあ,とアルゴリズム屋の間では評判なのでした(ほんと?)

時々来ては楽しく読ませて頂いています.
応援しています.(アルゴリズム・デザインは名著っぽいですね.
まだ読んでませんが,作者と訳者をみて思いました)

コメントをどうぞ

※メールアドレスとURLの入力は必須ではありません。 入力されたメールアドレスは記事に反映されず、ブログの管理者のみが参照できます。

※なお、送られたコメントはブログの管理者が確認するまで公開されません。

※投稿には管理者が設定した質問に答える必要があります。

名前:
メールアドレス:
URL:
次の質問に答えてください:
一富士、二鷹、三は? ひらがなで。

コメント:

トラックバック

_ 日々礼賛 - 2006年06月07日 14時59分08秒

中村正三郎さんのブログ:
古典的バイナリサーチアルゴリズムにバグ

衝撃的なタイトルだ。
記事のタイトルでは、アルゴリズムそのものに欠陥があったかのように受け取れるが、実はその実装に問題があるコードが発見されたらしい。

GoogleReserch Blog:
Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken
<U><I>1: public static int binarySearch(int[] a, int key) {
2: int low = 0;
3: int high = a.length - 1;
4:
5: while (low &lt;= high) {
6: int mid = (low + high) / 2;
7: int midVal = a[mid];
8:
9: if (midVal &lt; key)
10: low = mid + 1;
11: else if (midVal &gt; key)
12: high = mid - 1;
13: else
14: return mid; // key found
15: }
16: return -(low + 1); // key not found.
17: }</I></U>※ インデントできないのは筆者のせいではない。&amp;nbsp か 欲しい > Doblogさま

6行目に、整数オーバーフローのバグがある。

小飼弾さんは、/* 半世紀もののバグ */ と評しているが、四半世紀も埋もれていたモノが良く見つかったものだ。

32Bitプラットホームで、このバグが顕在化するには、2,147,483,647 の半分ぐらいの検索対象が必要になる。少なくとも、私の守備範囲であるエンプラ系アプリケーションの世界では、あまり取り扱わない数だ。10 桁の数は、数値としては十分取り扱う範囲だが、データの個数としては滅多に無い。仮にあったとして、サーチしたい場合は、データベース・エンジンにお任せする類の代物になる。
引き合いに出されているコードは、java.util.Arrays という SDK ライブラリに含まれるものなので、「滅多に無い」という言い訳は通用しないのだが、アプリ側で<B>滅多に使われない</B>のであれば、ライブラリ側でも<B>滅多に呼ばれない</B>事になる。

話のピントがずれるが、アプリ側の実装(というか設計)においては、仮に10億個のデータを扱うとすれば、その型は int 型では不十分で、ワンランク上の long 型を使うべきだろう。1,073,741,822 個を越えないとわかっていて、仕様上の最大値が、999,999,999 だとしても、long 型だろう。整数を扱う型の選択は、10進で一桁程度以上の余裕が無いと ----- 実際には 16Bit とか 32Bit の無駄が生じるが ------ 予期せぬ処で不都合に遭い兼ねない。(この不具合も氷山の一角かもしれない)
20年前なら叱られたかもしれないが、近年のプログラミング環境においては、組込み系とかドライバのようにシビアな性能要求/リソース要求が無い場合は、そうしたセイフティ・ネットがあった方が良いというのが、市井のソフト屋としての意見だ。


一方で、中村さんの一言は、いたく共感、
<U><I> それにしてもGoogle的世界では、2^30 の要素数が当たり前になってきてるのね。すると、こういう何十年も見つからないバグが出ちゃうんですね。</I></U>
どれだけ進化しても有限値しか持てないコンピュータは、すべての現実を写像する事はできない。
Google 最大の敵は、Microsoft でも Yahoo Search でもなく、レジスタのビット長かもしれない。

_ ホットコーナーの舞台裏 - 2008年09月02日 06時02分48秒

ASAHIネット(http://www.asahi-net.or.jp)のjouwa/salonからホットコーナー(http://www.asahi-net.or.jp/~ki4s-nkmr/ )に転載したものから。
---
http://iiyu.asablo.jp/blog/2008/08/30/3723153
「スペル修正プログラムはどう

_ ホットコーナーの舞台裏 - 2009年02月08日 09時15分37秒

ASAHIネット(http://www.asahi-net.or.jp)のjouwa/salonからホットコーナー(http://www.asahi-net.or.jp/~ki4s-nkmr/ )に転載したものから。
---
 Javaの定番本のひとつである「The Elements of Java Style」の翻訳がや

_ ホットコーナーの舞台裏 - 2009年06月09日 07時50分39秒

ASAHIネット(http://www.asahi-net.or.jp)のjouwa/salonからホットコーナー(http://www.asahi-net.or.jp/~ki4s-nkmr/ )に転載したものから。
---
http://iiyu.asablo.jp/blog/2009/05/22/4318138
クラウドコンピューティングの

_ ホットコーナーの舞台裏 - 2010年05月13日 06時15分46秒

ASAHIネット(http://asahi-net.jp )のjouwa/salonからホットコーナー(http://www.asahi-net.or.jp/~ki4s-nkmr/ )に転載したものから。
---
 オライリージャパンから、
http://www.amazon.co.jp/exec/obidos/ASIN/4873114284/sh

_ ホットコーナーの舞台裏 - 2010年05月24日 04時35分46秒

ASAHIネット(http://asahi-net.jp )のjouwa/salonからホットコーナー(http://www.asahi-net.or.jp/~ki4s-nkmr/ )に転載したものから。
---
 ずいぶん前に翔泳社の古田島さんから、送ってもらっていたが、や

_ ホットコーナーの舞台裏 - 2011年05月23日 05時18分57秒

ASAHIネット(http://asahi-net.jp )のjouwa/salonからホットコーナー(http://www.asahi-net.or.jp/~ki4s-nkmr/ )に転載したものから。
---
 オーム社の鹿野さん、献本ありがとうございます。

http://iiyu.asablo.

_ ホットコーナーの舞台裏 - 2013年06月05日 08時53分40秒

ASAHIネット(http://asahi-net.jp )のjouwa/salonからホットコーナー(http://www.asahi-net.or.jp/~ki4s-nkmr/ )に転載したものから。
---
 献本ありがとうございます。

http://www.amazon.co.jp/exec/obidos/ASIN/47981284

_ ホットコーナーの舞台裏 - 2014年02月24日 10時53分19秒

ASAHIネット(http://asahi-net.jp )のjouwa/salonからホットコーナー(http://www.asahi-net.or.jp/~ki4s-nkmr/ )に転載したものから。
---
 お買い上げありがとうございます。
 おれが、コルメン本と呼んで

_ ホットコーナーの舞台裏 - 2014年06月03日 10時39分02秒

ASAHIネット(http://asahi-net.jp )のjouwa/salonからホットコーナー(http://www.asahi-net.or.jp/~ki4s-nkmr/ )に転載したものから。
---
http://cloud.antenna.co.jp
PDFや画像ファイルをブラウザーからアップロード

_ ホットコーナーの舞台裏 - 2014年09月28日 08時53分15秒

ASAHIネット(http://asahi-net.jp )のjouwa/salonからホットコーナー(http://www.asahi-net.or.jp/~ki4s-nkmr/ )に転載したものから。
---
 Effective C++, Effective Javaなど、Effectiveシリーズのリストを作って
なか

_ ホットコーナーの舞台裏 - 2015年08月04日 10時24分51秒

ASAHIネット(http://asahi-net.jp )のjouwa/salonからホットコーナー(http://www.asahi-net.or.jp/~ki4s-nkmr/ )に転載したものから。
---
 天使すぎるアイドル、橋本環奈ちゃんが、情報省のスパイで、おれ

_ ホットコーナー - 2016年03月04日 10時01分11秒

ASAHIネット(http://asahi-net.jp )のjouwa/salonから。
---
 アルゴリズムの定番教科書、コルメン本のエッセンス本、アルゴリズムの入門書「アルゴリズムの基本」が出ますね
 大事なことだ