Comments 69
А мне кажется или это правда что теоретически возможны случаи (в зависимости от использованного алгоритма сортировки), когда [1,2,3].sort(() => Math.random - 0.5)
не завершится никогда (потому что сортировка не стабильна), ну или будет работать неопределенно большое время.
SELECT * FROM table ORDER BY RAND() LIMIT 1
— ещё круче (некоторые так делают выборку случайной строки из таблицы)Вы точно сейчас говорите про тот запрос с ORDER BY RAND()
? Там, если что, нет ни массива, ни последовательной выборки.
А как правильно?Важнее, что не так с этим кодом. Если мне не изменяет память, то вместо быстрого выбора одного случайного элемента вы сначала присваиваете всей таблице случайное число (а там может быть миллионы записей), потом сортируете эту таблицу и потом просто берете первый элемент.
Представьте, что вам надо выбрать случайную карту. Вместо того, чтобы просто взять случайную карту — вы на каждую запускаете генератор случайных чисел, потом записываете на карте это число, сортируете всю колоду по возрастанию этих чисел и берете первую карту. Представьте, как бы это было долго в сравнении с «просто взять случайную карту»
Сейчас попробую построить диаграмму, так с ходу не соображу, как она должна выглядеть)
Тут вопрос о том, какую нишу занимает ваш алгоритм. Его достоинство — он в два раза быстрее стандартного. Если скорость тасовки массива — самое узкое место в производительности страницы, то это может оказаться важно, но на практике я ещё никогда не встречался с такими ситуациями. Кстати, интересный вопрос, насколько быстрой может быть перетасовка, воспринимаемая человеком как случайная. Мне кажется, можно чуть-чуть ускорить, оставив несколько неподвижных элементов, но сильно быстрее сделать вряд ли получится.
Ещё потенциальное достоинство вашего алгоритма, о котором вы упоминали — что он может казаться человеку более случайным, чем истинно-случайный. Я не могу ни подтвердить, ни опровергнуть, что это действительно так. Но если стоит цель добиться «сверхслучайной псевдослучайности», лучше подробнее изучить вопрос, выяснить, как именно люди воспринимают случайность, и создать алгоритм на основании этих данных, а не с потолка. Скорее всего, кстати, эта работа кем-то уже проделана.
По прочим параметрам алгоритм Фишера-Йетса предпочтительнее.
Кстати, по поводу идеи, что можно чередовать какую из половин проходим последовательно, то если определять это случайным образом
Проблема в том, что как только выясняешь, какая половина была выбрана — сразу можно предсказать положение большинства элементов
но явно лучше, чем у Винампа, в своё время. :-)Это только подтверждает, что «случайность не выглядит случайной», а в Винампе, вероятно, была она.
В более новых плеерах добавлены исправления, чтобы «случайное воспроизведение» казалось более случайным.
2, 4, 3, 6, 9, 2
Если человек про себя начал считать с первой карты (он сам решает когда начинать, но желательно в начале процесса), то у него будет 2, 3, 2-это последняя карта, которую и надо угадать. Предполагается, что поскольку первая карта была выбрана случайно, то и последняя будет уникальна. Параллельно с ним кто-то так же начинает отсчёт, тоже с любого места, придут к финишу они скорее всего на одной и той же карте, что бы повысить шансы надо оставить двойки и тройки.
шёл до половины массива и менял их со случайными элементами второй половины, с поправкой, при нечётном количестве
Довольно очевидная, но неправильная и ненужная с точки зрения O(n) оптимизация, т.к. «надо n/2 обменов» — это все-равно время линейное. Такие оптимизации стоит делать только если вы уже профилируете и видите, что реально в этом месте в два раза ускорить и будет замечательно, а качество результата не столь важно. И даже в таком случае можно придумать более непредсказуемые алгоритмы — к примеру хватать только четные элементы и менять их с только-нечеткими.
Кстати, почему не «вывернутый», те. слева на право:
function shuffle(list) {
for (let i = 0; i < list.length; i += 1) {
const j = Math.floor(Math.random() * (i + 1)); // rand int 0 =< j =< i
[list[i], list[j]] = [list[j], list[i]];
}
return list;
}
Интересно.
Суть алгоритма, если перевести с JS на русский, следующая: берём последний элемент и меняем его местами со случайно выбранным элементом не правее его
Мне всегда была непонятна необходимость этого условия. Если менять со случайно выбранным элементом (любым, а не только те, что не правее) — будет ровно такая же равномерная случайность. Можете, пожалуйста, подтвердить это картинкой?
Интересно, а кто-то может объяснить, в чем изъян моей логики?
Можете, пожалуйста, подтвердить это картинкой?Как можно подтведить нечто очевидно неверное картинкой?
В вашем подходе на каждом шаге выбирается один из
n
исходов. Вы делаете n
щагов. То есть получаете nⁿ
вариантов. Правда некоторые из них одинаковы (скажем вариант 1, 2, 3, ..., n
получится если ничего никуда не двигалось, но также если 1 попадёт на место 2, а потом вернётся и так далее). То есть вероястности у вас в конечном итогде поучаться вида kα/nⁿ
. А нужно-то нам 1/n!
. Как несложно заметить — это возможно только при n == 1 или n == 2. А для этих двух случаев и так всё понятно.Мне всегда была непонятна необходимость этого условия.Без этого условия нет факториала. Без факториала нет гарантированно правильного перемешивания. Всё просто.
В 2014 на Google Code Jam даже предлагалась задача, в которой требовалось отличить последовательности сгенерированные правильным и вашим алгоритмом:
https://code.google.com/codejam/contest/2984486/dashboard#s=p2
1) разбиваем на списки: [1], [2], [3]
2) сливаем соседние пары, первый слитый список получится честно случайным: [(1|2), (2|1)], [3].
3) а теперь финальное слияние сразу поставит тройку в начало с шансом 50%, и привет, должно было быть ~33%.
То же самое происходит при любых массивах не длины степени двойки: как только сливаются списки разных размеров, последний элемент более длинного имеет больший шанс попасть в конец результата.
Кстати, можно попробовать нарисовать картинку как часто элементы с указанными номерами оказываются рядом.
Среди алгоритмов с неограниченным временем работы такие сортировки точно есть. Например, Bogosort со случайным компаратором даст случайную перестановку (но затратит на это в среднем O(n 2n) времени!).
Нет. Представим, что у нас массив [1,2,3,4]. Какова вероятность, что первые да из них будут 3 и 4 в каком-то порядке? 1/4 т.к перемешивание на нижнем уровне не влияет, а при слиянии двух массивов длины 2 нам нужно выбрать второй массив дважды. Какова вероятность должна быть? 4/24=1/6
на больших все нормально:
www.dropbox.com/s/8874xri2zv5ocx6/Screenshot%202018-05-15%2019.17.18.png?dl=0
впрочем как и на маленьких:
www.dropbox.com/s/sjeu7nu7b5rnndw/Screenshot%202018-05-15%2019.17.46.png?dl=0
но если брать не степень двойки, то наблюдается сдвиг:
www.dropbox.com/s/qos8u123fjdjksn/Screenshot%202018-05-15%2019.17.59.png?dl=0
Пятничный JS: случайное перемешивание