ランダム・シャッフルがランダムじゃない!

MS、Webブラウザ選択画面にアルゴリズム上のバグか

2010/03/01

 ヨーロッパで出荷されるWindows PCや既存Windowsユーザーに対してマイクロソフトは、IEを含む5つのWebブラウザがランダムな順序で表示されてユーザーに選択を促す「Webブラウザ選択画面」を提供するようになった。このとき表示されるブラウザの順序が、完全なランダムではなく偏りがあると話題になっている。

ballot01.jpg Webブラウザ選択画面

 問題を最初に報じたのはスロバキアの技術系サイト「DSL.sk」で、Windows 7上のIE8で、問題のブラウザ選択画面を開くと、約50%の確率でIEがいちばん最後に表示されるほか、9割近い確率でChromeが1〜3番目に表示されるというデータを示している。

result.png スロバキアの技術系サイトが報じたWebブラウザ選択画面の登場位置の偏り(出典:DSL.sk)

意図的ではない、初歩的な実装ミスか

 この問題について、IBMのRob Weir氏2月27日付けのブログの中で初歩的なミスによるバグの1種ではないかと論じている。

 Weir氏はマイクロソフトがJavaScriptで実装した並べ替え関数に独自のコードを加えてテストし、偏りが統計的に見てランダムな並べ替えである確率は極めて低いとしている。与えられた配列の中身をランダムに並べ替える問題は「ランダム・シャッフル」と呼ばれる古い問題で、コンピュータ史の初期から論じられてきたものだという。

 ランダム・シャッフルには、よく知られたいくつかのアプローチがあるという。

  • 与えられた要素の順列をすべてリストアップし、その中から1つをランダムに選ぶ方法
  • Fisher-Yatesシャッフルと呼ばれるもの
  • 与えられた配列と同サイズの配列を用意し、そこに乱数を入れていってこれをキーに並べ替える方法

 1つ目の方法はデータ量が小さいうちは十分に機能する。3つ目のものはFisher-Yatesシャッフルより計算量が多くなるものの、実装が容易というメリットがあるという。

 マイクロソフトの実装は、これらのいずれでもなく、Weir氏は「悪いアプローチを取ってしまったようだ」と指摘している。これは、バブルソートのように素朴なアルゴリズムを使ってしまったために起こった問題で、「コンピュータ・サイエンスを専攻する100人の新入生にやらせたら、少なくとも1人は同じ間違いを犯すのは確実だと思う」(Weir氏)という。

 具体的には、以下のJavaScript中のRandamSortが問題だという。

code.png ブラウザ選択画面の並べ替え関数のJavaScript

 JavaScriptの配列の並べ替え(sort)は比較関数を渡すことで柔軟な並べ替えが行える。ここではMath.rand()で半々の確率で正負の値を返しているので、隣り合う要素の並べ替えはランダムに起こる。これで結果もランダムになるように思えるが、実際に意味のある並べ替えを行うためには、並べ替えた後の配列が一定の基準に従っている並べられていることが不可欠で、例えば「a>b」であれば「b<a」、「a<bかつb<c」であれば「a<c」でなければならない。これは、隣り合う要素同士をただランダムに入れ替えるだけでは達成できないのだという。

 Weir氏は「このバグに極悪な意図があったとは思わない」とし、経験未熟なプログラマが必ずハマる問題であるとしている。このことから、同氏は「このバグが広まった程度に驚嘆している。これは選択画面がパブリックに出るよりずっと早い時点でマイクロソフトによって見つけられているべきものだった」と指摘。オンラインギャンブルサイトでは乱数生成やシャッフルアルゴリズムには監査が入ることもあるという例をひいて、Webブラウザ市場のステークホルダーのことを考えれば、ギャンブルと比べて取るに足らないものということはないだろう、と書いている。

(@IT 西村賢)

情報をお寄せください:

アイティメディアの提供サービス

キャリアアップ


- PR -
ソリューションFLASH

「ITmedia マーケティング」新着記事

オープンソースCMS「Drupal」商用版提供のAcquiaが日本市場に本格参入
Acquiaは、日本支社としてアクイアジャパンを設立したと発表した。

Macbee Planetの成果報酬型広告運用支援ツール「Robee」、DACのDMP「AudienceOne」とデータ連携
Macbee Planetは、同社が提供する成果報酬型広告運用支援ツール「Robee」を、デジタル・...

ミレニアル世代の85%が動画視聴後に購入の意思決定――Brightcove調査
動画コンテンツは購入の意思決定にどう影響しているのでしょうか。