Вот интересный вопрос по математике и информатике: насколько случайным является новый экран выбора браузера в ЕС от Microsoft? Это не так, согласно нескольким статьям статистического анализа, опубликованным на прошлой неделе.
Инженер IBM Роб Вейр (Rob Weir) подготовил один из лучших отчетов о заказе браузера на browserchoice.eu . Неслучайность довольно сложна и не обязательно поддерживает Internet Explorer; IE появился в последней половине времени, и Chrome, скорее всего, появился на первых трех позициях.
Принося Хаос из Порядка
Генерация случайных чисел на цифровом устройстве не легка. В большинстве реализаций используется математическая функция, которая возвращает псевдослучайное число. Это может показаться случайным, но последовательность предсказуема. Однако это не та проблема, с которой столкнулась Microsoft.
Существуют различные алгоритмы для «случайного» перемешивания множества элементов, но, по словам Роба Вейра, Microsoft выбрала худший. Они использовали следующую функцию сравнения JavaScript для array.sort ():
function RandomSort(a,b) { return (0.5 - Math.random()); } Поскольку функция сравнения возвращает случайный результат, процесс сортировки будет получать противоречивую информацию о ходе выполнения. Он не может выполнять обмен или, теоретически, может продолжаться бесконечно. В конечном итоге результаты не являются случайными.
Вейр предполагает, что Microsoft должна была использовать случайную комбинацию Фишера-Йейтса . По сути, это случайным образом выбирает элемент из исходного массива и перемещает его в конец целевого массива. Процесс продолжается до тех пор, пока все элементы из исходного массива не будут перемещены.
Это имеет значение?
На мой взгляд — нет. Большинство людей увидят экран один или два раза. Перестановочные несоответствия не становятся очевидными, пока вы не изучите выборки, содержащие тысячи пользователей.
Но нужны ли Microsoft дополнительные правовые споры? Для всех вас, юристов, с нетерпением ожидающих многословных технических рассуждений о предвзятости браузера — вы опоздали . Microsoft изменила алгоритм перестановки своих массивов:
function ArrayShuffle(a) { var d, c, b=a.length; while(b) { c=Math.floor(Math.random()*b); d=a[--b]; a[b]=a;
= Д;
}
}При наличии пятиэлементного массива функция будет проходить по элементам с 4 по 0 (переменная b). Случайное число генерируется между 0 и b (переменная c). Элементы b и c затем меняются местами. Это не алгоритм Фишера-Йейтса, но он намного лучше и обязательно завершится после 5 итераций (хотя он может завершиться после 4, поскольку последний элемент всегда будет заменен на себя) .
Я подозреваю, что это приведет к более равномерному случайному распределению позиций браузера. Стремительные статистики наверняка будут внимательно изучать результаты!