Главная » Хабрахабр » Пятничный JS: случайное перемешивание

Пятничный JS: случайное перемешивание

Это большой палец, это — указательный, это — средний, это — безымянный, это — мизинец. Экзамен в школе прапорщиков.
— Вот смотрите. Мешаем, мешаем, мешаем (двигает пальцами)… Теперь где какой?

Всем привет. С ортодоксальной точки зрения сегодня не настоящая пятница — просто день, когда завтра выходной. Поэтому статья в моей традиционной рубрике тоже будет не совсем настоящая, у неё пониженный градус безумия и повышенная полезность. Однако довольно предисловий, перейдём к сути.

За её решением они, как правило, лезут в гугл. Перед моими студентами регулярно встаёт задача случайного перемешивания массива. И гугл им подсказывает следующее:

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 раз.

Это означает, что при увеличении длины массива в 10 раз продолжительность его перемешивания увеличится более чем в 10 раз. Самые быстрые алгоритмы сортировки имеют временную сложность O(n*log(n)).

И чем больше массив, тем больше разница во времени выполнения. В сумме эти два факта значат вот что: для достаточно большого массива перемешивание случайной сортировкой будет работать медленнее, чем «правильное» перемешивание (даже если для маленьких массивов это было не так).

Потому что Array#sort выполняется нативным кодом, и за счёт этого на небольших массивах потенциально может оказаться быстрее. Почему я сделал оговорку в скобках? У него может оказаться меньше константный множитель, сказал бы человек, знакомый с О-нотацией.

Ненастоящая случайность

Те, кто хотя бы поверхностно знаком с теорией вероятностей, знают, что случайность случайности рознь. Монетка может выпасть орлом или решкой, кубик может выпасть шестёркой или не шестёркой. И там, и там имеют место случайные события, однако в первом случае события равновероятны, а во втором нет.

Именно этим свойством случайная сортировка не обладает, и я покажу это на практике. Перемешивание массива называется истинно случайным, если все возможные перестановки его элементов имеют одинаковую вероятность.

На ней находятся две диаграммы, одна соответствует случайному перемешиванию, вторая — случайной сортировке. Я набросал следующую страничку. Чтобы они стали диаграммами, нужна легенда — объяснение, что эти клеточки и их цвета означают. Впрочем, вы сейчас видите не диаграммы, а квадратики, разбитые на клеточки различных оттенков серого. Мы несколько раз (в данном случае несколько = 10000) берём массив чисел от 0 до n (в данном случае n = 32) и случайно перемешиваем тем или иным алгоритмом. Всё очень просто. Соответственно, цвет клетки в строке номер i и столбце номер j показывает, насколько часто число i оказывается на месте j. Затем мы вычисляем частоты, с которыми то или иное число оказывается на том или ином месте. Если число попадает на указанное место с теоретически предсказанной частотой 1/n, клетка будет иметь цвет hsl(0, 0%, 50%) — оттенок серого, расположенный в точности посередине между чёрным и белым. Чёрный цвет означает, что оно там не оказывается никогда, белый — что оно там оказывается вдвое или более чаще, чем положено.

Это означает, что при случайной сортировке определённые элементы имеют тенденцию оказываться в определённых местах. Если вы используете свежую версию браузера Chrome, вы видите, что в квадрате справа много белых или почти белых клеток, расположенных по определённой закономерности. Зависит от того, для чего вы используете перемешивание. Плохо ли это? Если вам важно, чтобы пользователь не мог предсказать, какой элемент окажется на каком месте, или если закономерности в перемешивании каким-то образом заметны визуально — то плохо. Если для каких-то косметических эффектов, то, возможно, ничего страшного. И упаси вас Гермес использовать такое перемешивание для чего-то, связанного с криптографией.

Это происходит оттого, что в разных браузерах используются различные алгоритмы сортировки (если интересно, вот моя статья на эту тему). Что удивительно, если вы используете Firefox, то для вас оба квадрата примерно одинаково серые. Firefox по-разному сортирует большие и маленькие массивы, сюрприз! В таком случае, если хотите удивиться ещё раз, допишите в адресной строке ?size=8 (вот готовая ссылка для ленивых).

Из того, что квадрат получился не серый, следует, что сортировка не равномерна, однако неверно обратное. Напоследок добавлю, что вот эти мои диаграммы с пятьюдесятью оттенками серого — не критерий, а признак. Частоты попадания элементов на места будут совершенно одинаковы, однако ни о какой истинной случайности перемешивания, разумеется, не может быть и речи. Контрпример — циклический сдвиг на случайную величину.

Как правильно?

Истинные джедаи используют одну из вариаций алгоритма Фишера-Йетса. Для своей демки я реализовал его так:

function shuffle(arr) 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}), они, к сожалению, будут идти подряд.

Спасибо за чтение, надеюсь, вам было познавательно, и особенно надеюсь, что я убедил вас не использовать случайную сортировку почти никогда. На этом всё. Приятного грядущего вечера.


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

[Перевод] Почему процессоры Skylake иногда работают в 2 раза медленнее

Мне сообщили, что на новых компьютерах некоторые регрессиионные тесты стали медленнее. Обычное дело, такое бывает. Неправильная конфигурация где-то в Windows или не самые оптимальные значения в BIOS. Но в этот раз нам никак не удавалось найти ту самую «сбитую» настройку. ...

«Защита авторских прав в ЕС»: новая реформа может повлиять не только на медиаплатформы

Новая директива о защите авторских прав, предложенная в Евросоюзе, которую мы недавно обсуждали в блоге, может существенно повлиять на устройство таких платформ, как YouTube, Facebook и Pinterest. Однако «под ударом» оказались не только они, но и библиотеки и агрегаторы научных ...