Użytkownik ma do wyboru 12 przeglądarek, z czego 5 najpopularniejszych (Internet Explorer, Firefox, Chrome, Opera, Safari) widać na pierwszy rzut oka w losowym porządku, a mniej popularną siódemkę można obejrzeć po przewinięciu listy. "Mali" oczywiście oprotestowali ten układ (słusznie, bo co, 12 się nie zmieści na ekranie?).
Ale jak się okazuje, "losowanie" pierwszej piątki też nie jest losowe. Hm...
O co chodzi? O źle zaprojektowany algorytm losowego uporządkowania. Jest on napisany w JavaScripcie i jest zwykłym sortowaniem z taką funkcją porządkującą:
function RandomSort (a,b)
{
return (0.5 - Math.random());
}
Wynik mniejszy od 0 oznacza a < b, większy: a > b, 0 to a = b. Na pierwszy rzut oka wszystko gra - to czy Internet Explorer jest lepszy od Firefoksa zależy tylko od losowania. Ale...
Problem polega na tym, że raz a < b, a zaraz potem a > b. Ponieważ losujemy liczby zmiennoprzecinkowe, to 0 się praktycznie tam nie trafi, dzięki czemu nigdy nie zajdzie oczywista równość a = b. A algorytmy sortowania przyjmują nieme założenie, że operacje porównywania mają sens.
Aby to sprawdzić napiszmy prosty kod w C++:
int compare(const void* elem1, const void* elem2)
{
return (rand() % 2 == 0) ? 1 : -1;
}
srand(time(NULL));
int numbers[5] = {1, 2, 3, 4, 5};
qsort(numbers, 5, sizeof(int), compare);
Wykonanie tego milion razy w pętli i po policzeniu częstości występowania każdej liczby na każdej pozycji otrzymujemy takie wyniki:
| Pozycja: | 1. | 2. | 3. | 4. | 5. |
| Element 1 | 30.7% | 30.7% | 20.5% | 11.7% | 6.2% |
| Element 2 | 30.7% | 30.7% | 20.5% | 11.7% | 6.3% |
| Element 3 | 16.4% | 16.4% | 32.8% | 21.8% | 12.5% |
| Element 4 | 11.7% | 11.8% | 14.0% | 37.5% | 25.0% |
| Element 5 | 10.4% | 10.3% | 12.1% | 17.1% | 50.0% |
Gdyby to było naprawdę losowe, to wszędzie byśmy mieli 20%. A tak widać, że piąty element w 50% przypadków zostaje na swoim miejscu (czyli z brzegu ekranu). Zgadnijcie jaka to przeglądarka?
Co ciekawe - chciałem to na początku napisać w C# - ale często rzucał się wyjątek, że x.CompareTo(x) powinno zwrócić zero, a nie zwróciło. Czyli już tutaj mielibyśmy sygnał, że jest nie tak coś.
Jest to kolejny dowód na to, że zamiast wymyślać algorytm samemu od podstaw, to zastosować jakiś sprawdzony, np. tasowanie Fishera-Yatesa (http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle), opisane przez Knutha:
void shuffle(int elems[], int length)
{
for (int n = length; n > 1; --n)
{
int k = rand() % n;
int tmp = elems[k];
elems[k] = elems[n - 1];
elems[n - 1] = tmp;
}
}
Jeszcze większa kompromitacja miała miejsce przy polskiej wersji strony wyboru przeglądarki:
http://www.browserchoice.eu/BrowserChoice/browserchoice_pl.htm
Wejdźcie, odświeżcie parę razy. IE zawsze pierwsze, FF zawsze drugi - nie wygląda to losowo, co nie? Bo nie jest.
Problem nie jest już tak subtelny, jest to po prostu babol w kodzie javascriptowym. I to nic wielkiego - po prostu brak znaczka \ przed znaczkiem " w jednym z opisów, przez co javascript się nie uruchamia. I nie losuje.
Poprawa tego błędu to ok. 30 sekund roboty. Aby go odnaleźć trzeba się napracować: może z 3 razy przeładować stronę, zobaczyć że nie losuje, a potem obejrzeć konsolę błędów JavaScript aby się dowiedzieć czemu.
Microsoft wypuści odpowiednią łatkę pod koniec miesiąca kwietnia.
Więcej na blogu Roba Weira:
http://www.robweir.com/blog/2010/02/microsoft-random-browser-ballot.html
http://www.robweir.com/blog/2010/04/browser-choice-fail.html
Brak komentarzy:
Prześlij komentarz