Экзамен в школе прапорщиков.Всем привет. С ортодоксальной точки зрения сегодня не настоящая пятница — просто день, когда завтра выходной. Поэтому статья в моей традиционной рубрике тоже будет не совсем настоящая, у неё пониженный градус безумия и повышенная полезность. Однако довольно предисловий, перейдём к сути.
— Вот смотрите. Это большой палец, это — указательный, это — средний, это — безымянный, это — мизинец. Мешаем, мешаем, мешаем (двигает пальцами)… Теперь где какой?
Перед моими студентами регулярно встаёт задача случайного перемешивания массива. За её решением они, как правило, лезут в гугл. И гугл им подсказывает следующее:
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}), они, к сожалению, будут идти подряд.
На этом всё. Спасибо за чтение, надеюсь, вам было познавательно, и особенно надеюсь, что я убедил вас не использовать случайную сортировку почти никогда. Приятного грядущего вечера.
