同じプログラムを動作させたのに、ブラウザによってなぜこれほど結果が異なるのだろうか?

Microsoftのブラウザ選択画面におけるランダムな並べ替えは、JavaScriptを用いてクライアント側で行われている。Webブラウザ内での、いわゆる"ランダム・シャッフル"が必要になる。これには2つの効果的なソリューションがあるとWeir氏は指摘する。まずアイテム数が少ない場合ならば、順列の可能性を全てテーブルに並べて、その中から1つをランダムに選択する。5つのブラウザでは、テーブルは120列になる。もう1つは、配列からランダムに値を選んで後ろから順に入れ替えていく「Fisher-Yatesシャッフル」だ。こちらの方がよりメジャーなアプローチといえる。

Microsoftは、これらのいずれでもない手法を採り、それが目的のソリューションとなっていないのがブラウザ選択表示の偏りを引き起こしているという。具体的には、隣り合うブラウザを入れ替える以下のプログラムだ。

function RandomSort (a,b)
{
    return (0.5 - Math.random());
}

Math.random()は0から1の間の数字をランダムに生成し、それを0.5と比較した値(-0.5から0.5)が返されて隣り合う要素の入れ替えが起こる。これでランダムな入れ替えが実現するものの、「並べ替え(Sorting)には、矛盾のない配列の定義が求められる」とWeir氏。「a＜bならばb＞a」であり、「b＜cならばa＜c」でなければならない。だが、ただ隣り合う要素同士をランダムに入れ替えるMicrosoftの比較関数では、この配列が成り立つとは限らない。そのため端の方で偏る結果が出てしまう。また、JavaScriptにおける並べ替えに特定の定義がなくブラウザごとに並べ替え関数の処理が異なるため、IEとFirefoxの結果の違いに現れたと見ている。

試しにWeir氏がFisher-Yatesシャッフルを用いて5つのブラウザをシャッフルするプログラムをテストしたところ、以下のような均等な並べ替えになった。

Fisher-Yates法を用いたテストプログラムでの1万回ループ結果。きれいに均等だ

Weir氏はMicrosoftの過ちをバグとは呼ばないものの、「課題を与えられた未熟なプログラマが失敗してしまうバブル・ソートだ。コンピュータ科学を専攻する新入生100人に同じ問題を解かせたら、少なくとも1人は同じ過ちを犯すだろう」と手厳しい。

「Opera」のダウンロードが3倍の伸びを見せる

欧州委員会はMicrosoftに対してランダムな並べ替えを求めているのみで、それらが完全に均等である必要はない。ブラウザ選択ツールはブラウザの順番をシャッフルさせているので、このエラーは許容範囲と呼べるかもしれない。実際、今回のエラーに対しては非難ではなく、苦笑するような反応の方が目立つ。ただし、欧州委員会の並べ替えのこだわりに「均等であるべき」という意味が言外に含まれるのは言うまでもないことだ。Opera Softwareによると、英国、ベルギー、フランスなどブラウザ選択画面が先行導入された地域ではブラウザ「Opera」のダウンロードに3倍の伸びが見られたという。今後も引き続きブラウザ選択ツールの効果が認められるようならば、"完全に均等な並べ替え"を求める声が出てきそうだ。