NewsInsight

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

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

2010/03/01

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

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

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

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

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

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

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

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

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

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

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

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