Пятничный JS: случайное перемешивание
Экзамен в школе прапорщиков.
— Вот смотрите. Это большой палец, это — указательный, это — средний, это — безымянный, это — мизинец. Мешаем, мешаем, мешаем (двигает пальцами)… Теперь где какой?
Всем привет. С ортодоксальной точки зрения сегодня не настоящая пятница — просто день, когда завтра выходной. Поэтому статья в моей традиционной рубрике тоже будет не совсем настоящая, у неё пониженный градус безумия и повышенная полезность. Однако довольно предисловий, перейдём к сути.
Перед моими студентами регулярно встаёт задача случайного перемешивания массива. За её решением они, как правило, лезут в гугл. И гугл им подсказывает следующее:
var shuffledArr = arr.sort(function{
return Math.random() - 0.5;
});
Сегодня я решил написать о том, какие преимущества и недостатки есть у такого подхода.
Как это вообще работает?
Метод sort у джаваскриптовых массивов в качестве аргумента принимает функцию-компаратор. Эта функция должна принимать два элемента массива и возвращать число. Если число положительное, алгоритм сортировки считает, что первый элемент больше; если отрицательное — значит, первый элемент меньше; если же компаратор возвращает нуль, то в рамках данной сортировки элементы как бы равны. Если под видом компаратора передать функцию, которая будет возвращать положительное или отрицательное число случайным образом, то массив окажется отсортирован в «случайном» порядке.
Преимущества
Такое перемешивание очень быстро пишется. Я честно пытался придумать какое-нибудь ещё преимущество, но мне не удалось.
Недостатки
Этот параграф будет несколько длиннее, потому я разобью его на подпараграфы.
Несоответствие спецификации
Спецификация EcmaScript (я намеренно не называю версию, поскольку во всех версиях этот пункт остаётся примерно одинаковым) заявляет нам следующее:
The sort order is also implementation-defined if comparefn is undefined and SortCompare (22.1.3.24.1) does not act as a consistent comparison function.
В переводе с технического английского на русский разговорный это означает, что если компаратор не отвечает некоторым очевидным требованиям, то порядок сортировки зависит от реализации конкретного джаваскриптового движка. То есть, фактически, не определён. Разработчик браузера имеет, например, полное право сделать так, что при обнаружении того, что компаратор «ненастоящий», возвращается исходный массив без каких-либо перестановок. И это будет полностью соответствовать спецификации. То, что во всех существующий браузерах приведённый метод даёт нечто похожее на случайное перемешивание — не более чем счастливое совпадение.
Временная сложность
Корректный алгоритм перемешивания (см. ниже) имеет временную сложность O (n). Переводя на русский, это означает примерно следующее: если длина массива увеличится в 10 раз, то продолжительность его перемешивания также увеличится в 10 раз.
Самые быстрые алгоритмы сортировки имеют временную сложность O (n*log (n)). Это означает, что при увеличении длины массива в 10 раз продолжительность его перемешивания увеличится более чем в 10 раз.
В сумме эти два факта значат вот что: для достаточно большого массива перемешивание случайной сортировкой будет работать медленнее, чем «правильное» перемешивание (даже если для маленьких массивов это было не так). И чем больше массив, тем больше разница во времени выполнения.
Почему я сделал оговорку в скобках? Потому что Array#sort выполняется нативным кодом, и за счёт этого на небольших массивах потенциально может оказаться быстрее. У него может оказаться меньше константный множитель, сказал бы человек, знакомый с О-нотацией.
Ненастоящая случайность
Те, кто хотя бы поверхностно знаком с теорией вероятностей, знают, что случайность случайности рознь. Монетка может выпасть орлом или решкой, кубик может выпасть шестёркой или не шестёркой. И там, и там имеют место случайные события, однако в первом случае события равновероятны, а во втором нет.
Перемешивание массива называется истинно случайным, если все возможные перестановки его элементов имеют одинаковую вероятность. Именно этим свойством случайная сортировка не обладает, и я покажу это на практике.
Я набросал следующую страничку. На ней находятся две диаграммы, одна соответствует случайному перемешиванию, вторая — случайной сортировке. Впрочем, вы сейчас видите не диаграммы, а квадратики, разбитые на клеточки различных оттенков серого. Чтобы они стали диаграммами, нужна легенда — объяснение, что эти клеточки и их цвета означают. Всё очень просто. Мы берём массив чисел от 0 до n (в данном случае n = 32), затем случайно перемешиваем его тем или иным алгоритмом несколько раз (в данном случае несколько = 10000) и вычисляем частоты, с которыми то или иное число оказывается на том или ином месте. Соответственно, цвет клетки в строке номер i и столбце номер j показывает, насколько часто число i оказывается на месте j. Чёрный цвет означает, что оно там не оказывается никогда, белый — что оно там оказывается вдвое или более чаще, чем положено. Если число попадает на указанное место с теоретически предсказанной частотой 1/n, клетка будет иметь цвет hsl (0, 0%, 50%) — оттенок серого, расположенный в точности посередине между чёрным и белым.
Если вы используете свежую версию браузера Chrome, вы видите, что в квадрате справа много белых или почти белых клеток, расположенных по определённой закономерности. Это означает, что при случайной сортировке определённые элементы имеют тенденцию оказываться в определённых местах. Плохо ли это? Зависит от того, для чего вы используете перемешивание. Если для каких-то косметических эффектов, то, возможно, ничего страшного. Если вам важно, чтобы пользователь не мог предсказать, какой элемент окажется на каком месте, или если закономерности в перемешивании оказываются каким-то образом заметны визуально — то плохо. И упаси вас Гермес использовать такое перемешивание для чего-то, связанного с криптографией.
Что удивительно, если вы используете Firefox, то для вас оба квадрата примерно одинаково серые. Это происходит оттого, что в разных браузерах используются различные алгоритмы сортировки (если интересно, вот моя статья на эту тему). В таком случае, если хотите удивиться ещё раз, допишите в адресной строке? size=8 (вот готовая ссылка для ленивых). Firefox по-разному сортирует большие и маленькие массивы, сюрприз!
Напоследок добавлю, что вот эти мои диаграммы с пятьюдесятью оттенками серого — не критерий, а признак. Из того, что квадрат получился не серый, следует, что сортировка не равномерна, однако неверно обратное. Контрпример — циклический сдвиг на случайную величину. Частоты попадания элементов на места будут совершенно одинаковы, однако ни о какой истинной случайности перемешивания, разумеется, не может быть и речи.
Как правильно?
Истинные джедаи используют одну из вариаций алгоритма Фишера-Йетса. Для своей демки я реализовал его так:
function shuffle(arr){
var j, temp;
for(var i = arr.length - 1; i > 0; i--){
j = Math.floor(Math.random()*(i + 1));
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
return arr;
}
Суть алгоритма, если перевести с JS на русский, следующая: берём последний элемент и меняем его местами со случайно выбранным элементом не правее его (т.е. с любым, в том числе, возможно, и с ним самим). Затем повторяем ту же операцию для предпоследнего элемента, потом для предпредпоследнего и так далее. Вуаля! (этим словом с JS на русский переводится «return arr;»).
Настало время безумия
Кто-то из читателей ждал этого целую статью, остальные, в принципе, могут этот параграф не дочитывать. Я задался вопросом: можно ли написать такую функцию compare, что arr.sort (compare) даст истинно случайную перестановку? Ответ: можно, но с определёнными оговорками. Первая — функцию надо перед каждой сортировкой создавать заново. Вторая — в массиве не должно быть одинаковых элементов. Итак, узрите:
//вспомогательная функция
function putToCache(elem, cache){
if(cache.indexOf(elem) != -1){
return;
}
var i = Math.floor(Math.random()*(cache.length + 1));
cache.splice(i, 0, elem);
}
//функция, возвращающая свеженький, девственный компаратор
function madness(){
var cache = [];
return function(a, b){
putToCache(a, cache);
putToCache(b, cache);
return cache.indexOf(b) - cache.indexOf(a);
}
}
//собственно функция перемешивания
function shuffle(arr){
return arr.sort(madness());
}
Это работает следующим образом: при создании компаратор через замыкание получает доступ к массиву cache. Каждый раз, когда ему передаются аргументы, он кладёт их в cache на случайные места, а затем считает, что тот элемент, который в cache стоит правее, будет больше. То есть по сути в массиве cache постепенно строится тот случайный порядок, в котором элементы должны стоять, а метод sort постепенно приводит исходный массив в соответствии с этим порядком. Если же в нём окажутся равные элементы (равные с точки зрения оператора ===, если мы сортируем объекты — то всё хорошо, даже если у них одинаковое содержание. {a: 1} !== {a: 1}), они, к сожалению, будут идти подряд.
На этом всё. Спасибо за чтение, надеюсь, вам было познавательно, и особенно надеюсь, что я убедил вас не использовать случайную сортировку почти никогда. Приятного грядущего вечера.
