Экзамен в школе прапорщиков.Всем привет. С ортодоксальной точки зрения сегодня не настоящая пятница — просто день, когда завтра выходной. Поэтому статья в моей традиционной рубрике тоже будет не совсем настоящая, у неё пониженный градус безумия и повышенная полезность. Однако довольно предисловий, перейдём к сути.
— Вот смотрите. Это большой палец, это — указательный, это — средний, это — безымянный, это — мизинец. Мешаем, мешаем, мешаем (двигает пальцами)… Теперь где какой?
Перед моими студентами регулярно встаёт задача случайного перемешивания массива. За её решением они, как правило, лезут в гугл. И гугл им подсказывает следующее:
var shuffledArr = arr.sort(function(){
return Math.random() - 0.5;
});
Здесь и далее будем называть этот метод случайной сортировкой. Сегодня я решил написать о том, какие преимущества и недостатки есть у такого подхода.
Как это вообще работает?
Метод sort у джаваскриптовых массивов в качестве аргумента принимает функцию-компаратор. Эта функция должна принимать два элемента массива и возвращать число. Если число положительное, алгоритм сортировки считает, что первый элемент больше; если отрицательное — значит, первый элемент меньше; если же компаратор возвращает нуль, то в рамках данной сортировки элементы как бы равны. Если под видом компаратора передать функцию, которая будет возвращать положительное или отрицательное число случайным образом, то массив окажется отсортирован в «случайном» порядке.
Преимущества
Такое перемешивание очень быстро пишется. Я честно пытался придумать какое-нибудь ещё преимущество, но мне не удалось.
Недостатки
Этот параграф будет несколько длиннее, потому я разобью его на подпараграфы.
Несоответствие спецификации
Спецификация EcmaScript (я намеренно не называю версию, поскольку во всех версиях этот пункт остаётся примерно одинаковым) заявляет нам следующее:
If comparefn is not undefined and is not a consistent comparison function for the elements of this array (see below), the sort order is implementation-defined.
В переводе с технического английского на русский разговорный это означает, что если компаратор не отвечает некоторым очевидным требованиям (ниже в спецификации разъясняется, что, в частности, он должен для одних и тех же аргументов всегда возвращать одно и то же значение), то порядок сортировки зависит от реализации конкретного джаваскриптового движка. То есть, фактически, не определён. Разработчик браузера имеет, например, полное право сделать так, что при обнаружении того, что компаратор «ненастоящий», возвращается исходный массив без каких-либо перестановок. И это будет полностью соответствовать спецификации. То, что во всех существующих браузерах приведённый метод даёт нечто похожее на случайное перемешивание — не более чем счастливое совпадение.
Временна́я сложность
Корректный алгоритм перемешивания (см. ниже) имеет временную сложность O(n). Попросту говоря, это означает примерно следующее: если длина массива увеличится в 10 раз, то продолжительность его перемешивания также увеличится в 10 раз.
Самые быстрые алгоритмы сортировки имеют временную сложность O(n*log(n)). Это означает, что при увеличении длины массива в 10 раз продолжительность его перемешивания увеличится более чем в 10 раз.
В сумме эти два факта значат вот что: для достаточно большого массива перемешивание случайной сортировкой будет работать медленнее, чем «правильное» перемешивание (даже если для маленьких массивов это было не так). И чем больше массив, тем больше разница во времени выполнения.
Почему я сделал оговорку в скобках? Потому что Array#sort выполняется нативным кодом, и за счёт этого на небольших массивах потенциально может оказаться быстрее. У него может оказаться меньше константный множитель, сказал бы человек, знакомый с О-нотацией.
Ненастоящая случайность
Те, кто хотя бы поверхностно знаком с теорией вероятностей, знают, что случайность случайности рознь. Монетка может выпасть орлом или решкой, кубик может выпасть шестёркой или не шестёркой. И там, и там имеют место случайные события, однако в первом случае события равновероятны, а во втором нет.
Перемешивание массива называется истинно случайным, если все возможные перестановки его элементов имеют одинаковую вероятность. Именно этим свойством случайная сортировка не обладает, и я покажу это на практике.
Я набросал следующую страничку. На ней находятся две диаграммы, одна соответствует случайному перемешиванию, вторая — случайной сортировке. Впрочем, вы сейчас видите не диаграммы, а квадратики, разбитые на клеточки различных оттенков серого. Чтобы они стали диаграммами, нужна легенда — объяснение, что эти клеточки и их цвета означают. Всё очень просто. Мы несколько раз (в данном случае несколько = 10000) берём массив чисел от 0 до n (в данном случае n = 32) и случайно перемешиваем тем или иным алгоритмом. Затем мы вычисляем частоты, с которыми то или иное число оказывается на том или ином месте. Соответственно, цвет клетки в строке номер i и столбце номер j показывает, насколько часто число i оказывается на месте j. Чёрный цвет означает, что оно там не оказывается никогда, белый — что оно там оказывается вдвое или более чаще, чем положено. Если число попадает на указанное место с теоретически предсказанной частотой 1/n, клетка будет иметь цвет hsl(0, 0%, 50%) — оттенок серого, расположенный в точности посередине между чёрным и белым.
Если вы используете свежую версию браузера Chrome, вы видите, что в квадрате справа много белых или почти белых клеток, расположенных по определённой закономерности. Это означает, что при случайной сортировке определённые элементы имеют тенденцию оказываться в определённых местах. Плохо ли это? Зависит от того, для чего вы используете перемешивание. Если для каких-то косметических эффектов, то, возможно, ничего страшного. Если вам важно, чтобы пользователь не мог предсказать, какой элемент окажется на каком месте, или если закономерности в перемешивании каким-то образом заметны визуально — то плохо. И упаси вас Гермес использовать такое перемешивание для чего-то, связанного с криптографией.
Что удивительно, если вы используете Firefox, то для вас оба квадрата примерно одинаково серые. Это происходит оттого, что в разных браузерах используются различные алгоритмы сортировки (если интересно, вот моя статья на эту тему). В таком случае, если хотите удивиться ещё раз, допишите в адресной строке ?size=8 (вот готовая ссылка для ленивых). Firefox по-разному сортирует большие и маленькие массивы, сюрприз!
Upd: товарищ mk2 заметил, что равномерно-серым квадрат в Firefox будет только при размере, равном степени двойки. Нужно больше таких внимательных товарищей, товарищи!
Upd2: товарищи Stalker_RED и yaZva не поленились (в отличие от меня) сделать скрины в различных браузерах.
Напоследок добавлю, что вот эти мои диаграммы с пятьюдесятью оттенками серого — не критерий, а признак. Из того, что квадрат получился не серый, следует, что сортировка не равномерна, однако неверно обратное. Контрпример — циклический сдвиг на случайную величину. Частоты попадания элементов на места будут совершенно одинаковы, однако ни о какой истинной случайности перемешивания, разумеется, не может быть и речи.
Upd3: в этой ветке обсуждается, почему случайная сортировка не даёт равномерную случайность в 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){
var compare = madness();
return arr.sort(compare);
}
Это работает следующим образом: при создании компаратор через замыкание получает доступ к массиву cache. Каждый раз, когда ему передаются аргументы, он кладёт их в cache на случайные места (если их там ещё нет), а затем считает, что тот элемент, который в cache стоит правее, будет больше. То есть по сути в массиве cache постепенно строится тот случайный порядок, в котором элементы должны стоять, а метод sort постепенно приводит исходный массив в соответствии с этим порядком. Если же в нём окажутся равные элементы (равные с точки зрения оператора ===, если мы сортируем объекты — то всё хорошо, даже если у них одинаковое содержание. {a: 1} !== {a: 1}), они, к сожалению, будут идти подряд.
На этом всё. Спасибо за чтение, надеюсь, вам было познавательно, и особенно надеюсь, что я убедил вас не использовать случайную сортировку почти никогда. Приятного грядущего вечера.
