Pull to refresh

Comments 69

А мне кажется или это правда что теоретически возможны случаи (в зависимости от использованного алгоритма сортировки), когда [1,2,3].sort(() => Math.random - 0.5) не завершится никогда (потому что сортировка не стабильна), ну или будет работать неопределенно большое время.

Я бы ответил так: теоретически, можно написать такой алгоритм сортировки, который на случайном компараторе будет работать неопределённо долго. Допустим, модифицировав пузырёк, чтобы всплытие на каждой итерации производилось по всей длине массива, а критерием завершения стало отсутствие обменов элементами на последней итерации. Однако из существующих и применяющихся алгоритмов те, которые я сумел вспомнить, не обладают подобным недостатком. Эффективный алгоритм сортировки — это по сути то или иное дерево сравнений. Он не сравнивает элементы по два раза и не сравнивает элементы, отношение между которыми может быть выведено из уже произведённых сравнений. Потому он даже не заметит, что царь не настоящий.
SELECT * FROM table ORDER BY RAND() LIMIT 1
— ещё круче (некоторые так делают выборку случайной строки из таблицы)
Сначала вычислить номер, потом получить строку по номеру. На больших таблицах это будет намного быстрее даже несмотря на два запроса вместо одного.
Перемешивание массива подразумевает, что потом, выбирая последовательно элементы, один и тот же элемент не попадётся дважды (например, номера купонов, ещё и проверить, потом, можно будет, что купон выдан). Каждый раз выбор случайного элемента этого не гарантирует, поэтому, собственно, массивы и перемешивают.

Вы точно сейчас говорите про тот запрос с ORDER BY RAND()? Там, если что, нет ни массива, ни последовательной выборки.

Я скорее и о вашем комментарии и о том запросе: что это ситуации не из обсуждаемых в статье. Хотя, если убрать лимит, то как раз получается упорядоченный список, но поскольку порядок хранения строк в таблицах неопределён, то что бы реально это использовать, надо сохранить в таблицу, и кластерный индекс строить по результату или поле добавлять или просто на вывод отдать. Номера не заглядывая в данные таблицы, получить будет быстрей, но если таблица хорошо нагружена на запись, то тут уже вопрос актуальности, впрочем, как и всегда в SQL любой вопрос — не простой.
А как правильно?
Важнее, что не так с этим кодом. Если мне не изменяет память, то вместо быстрого выбора одного случайного элемента вы сначала присваиваете всей таблице случайное число (а там может быть миллионы записей), потом сортируете эту таблицу и потом просто берете первый элемент.
Представьте, что вам надо выбрать случайную карту. Вместо того, чтобы просто взять случайную карту — вы на каждую запускаете генератор случайных чисел, потом записываете на карте это число, сортируете всю колоду по возрастанию этих чисел и берете первую карту. Представьте, как бы это было долго в сравнении с «просто взять случайную карту»
Когда-то перемешивал картинки: шёл до половины массива и менял их со случайными элементами второй половины, с поправкой, при нечётном количестве. Воообще, для перемешивания n элементов, надо n/2 обменов, насколько хорошо у меня получилось — не знаю, но явно лучше, чем у Винампа, в своё время. :-)
Диаграмма бы получилась в виде белого косого креста) А хорошо или нет — опять же, зависит от цели. Возможно, пользователю при частом обновлении страницы надоело бы видеть на первом месте две картинки попеременно.
А можно увидеть реальную диаграмму, я не вижу, почему элементы в данном случае, будут тяготеть к каким-то местам, хотя, то что качество сортировки не слишком высокое — интуитивно понимаю.
Пардон, невнимательно прочитал. Мне почему-то показалось, что элемент случайно меняется местами с симметричным ему элементом. Не знаю, почему я так прочитал.

Сейчас попробую построить диаграмму, так с ходу не соображу, как она должна выглядеть)
В принципе, я уже вижу, что во второй половине, элементы будут чаще оставаться на своих местах, но какая половина проходится последовательно, можно чередовать.
Не слишком ли много никогда не меняющихся элементов? Как-то не вериться, что из второй половины массива никогда не выбиралось 75% элементов.
Белый — это не никогда не меняющиеся, это оказывающиеся на данном месте с вероятностью вдвое или более выше расчётной. Да, немного контринтуитивный способ отображения, но при интуитивном получался недостаточный контраст.
Я как раз про три треугольника чёрного цвета.
А. Клетки чёрного цвета показывают, какие элементы в какие места никогда не попадут. например, элементы из второй половины массива не могут попасть на другое место во второй половине массива. Либо они остаются на месте, либо перемещаются в первую половину. Элементы первой половины массива могут переместиться во вторую, а потом обратно в первую, но только с повышением номера, а не наоборот. Всё же правильно вроде?
Абсолютно верно, я просто думал, что учитывается несколько последовательных итераций над всем массивом.
Хм. Действительно, в описание эксперимента вкралась неточность. Сейчас попробую переформулировать.
Кстати, ещё красивее получается, если увеличить число итераций до миллиона.
спрячу, чтобы не растаращивать страницу

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

Тут вопрос о том, какую нишу занимает ваш алгоритм. Его достоинство — он в два раза быстрее стандартного. Если скорость тасовки массива — самое узкое место в производительности страницы, то это может оказаться важно, но на практике я ещё никогда не встречался с такими ситуациями. Кстати, интересный вопрос, насколько быстрой может быть перетасовка, воспринимаемая человеком как случайная. Мне кажется, можно чуть-чуть ускорить, оставив несколько неподвижных элементов, но сильно быстрее сделать вряд ли получится.

Ещё потенциальное достоинство вашего алгоритма, о котором вы упоминали — что он может казаться человеку более случайным, чем истинно-случайный. Я не могу ни подтвердить, ни опровергнуть, что это действительно так. Но если стоит цель добиться «сверхслучайной псевдослучайности», лучше подробнее изучить вопрос, выяснить, как именно люди воспринимают случайность, и создать алгоритм на основании этих данных, а не с потолка. Скорее всего, кстати, эта работа кем-то уже проделана.

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

Проблема в том, что как только выясняешь, какая половина была выбрана — сразу можно предсказать положение большинства элементов
но явно лучше, чем у Винампа, в своё время. :-)
Это только подтверждает, что «случайность не выглядит случайной», а в Винампе, вероятно, была она.
В более новых плеерах добавлены исправления, чтобы «случайное воспроизведение» казалось более случайным.
Насчёт «неслучайной случайности», с последовательностью всё ещё интересней. Есть такой простой тест: выкладывайте карты из колоды по одной и отсчитывайте значение карты, начиная с любой. Отсчитали, берёте новое значение и так до конца колоды, последняя карта почти всегда совпадёт с тем, кто будет считать параллельно с вами (хорошо на детях срабатывает, типа угадаю карту), но начинали вы с разных карт, просто совпадение в любом месте объединяет цепочки, а мест много, поэтому вероятность очень высокая.
Честно говоря, я не очень понял методологию эксперимента. Можно более подробно?
Карты: валет 2 очка, король 4, тройка 3 и т.п. Карты выкладываются открыто, например серия:
2, 4, 3, 6, 9, 2
Если человек про себя начал считать с первой карты (он сам решает когда начинать, но желательно в начале процесса), то у него будет 2, 3, 2-это последняя карта, которую и надо угадать. Предполагается, что поскольку первая карта была выбрана случайно, то и последняя будет уникальна. Параллельно с ним кто-то так же начинает отсчёт, тоже с любого места, придут к финишу они скорее всего на одной и той же карте, что бы повысить шансы надо оставить двойки и тройки.
шёл до половины массива и менял их со случайными элементами второй половины, с поправкой, при нечётном количестве

Довольно очевидная, но неправильная и ненужная с точки зрения O(n) оптимизация, т.к. «надо n/2 обменов» — это все-равно время линейное. Такие оптимизации стоит делать только если вы уже профилируете и видите, что реально в этом месте в два раза ускорить и будет замечательно, а качество результата не столь важно. И даже в таком случае можно придумать более непредсказуемые алгоритмы — к примеру хватать только четные элементы и менять их с только-нечеткими.
А есть ли принципиальная разница между направлениями прохода в вашем варианте алгоритма? То бишь цикл запускать не с конца массива, а с начала. И «не левее» соотвественно

По сути нет, просто с конца удобнее записывать.

На самом деле для firefox у вас удачно совпало, что дефолтный размер массива равен двум. Видимо, там используется mergesort с делением на степени двойки или что-то подобное. Попробуйте size=24 например. Кстати, это наименьший размер, на котором используется этот алгоритм, 23 еще другой)
Тысяча чертей, это вы здорово подметили)
Совершенно верно. Это описано в статье википедии, на которую я ссылаюсь. У меня реализован продвинутый вариант.
Эх, а я уже стер свой комментарий, т.к. увидел, что у вас продвинутый. Поспешил.

Кстати, почему не «вывернутый», те. слева на право:


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;
}
Потому что я знаю, как доказывать равновероятность для своего варианта, а для вашего надо ещё раз думать) но вообще да, вроде эквивалентно. (бормочу по-математически) Если перестановку вашего варианта перемножить с моей (предполагая, что случайные числа выпадали те же, но в обратном порядке), получится тождественная перестановка. Одинаковые транспозиции схлопнутся. То есть ваша перестановка будет обратна моей. Если моя равновероятна, то и ваша равновероятна.
В Chrome, если size=512 (и меньше), то можно четко увидеть вертикальную полосу посередине, а при size=1024 несколько мелких белых поперечных крапинок. А при size=4096 исчезает диагональная полоса, видная на меньших размерах.
Интересно.
Полагаю, тут дело не в особенностях сортировки, а в особенностях визуализации. У меня канвасы 512 на 512) скорее всего, если увеличить количество пикселей в канвасе, артефакты исчезнут.

Что-то необычное в нём используется для сортировки. Сортирует правда медленнее чем все другие браузеры.

Говорят, там модифицированная сортировка вставками до 512 элементов.
Суть алгоритма, если перевести с JS на русский, следующая: берём последний элемент и меняем его местами со случайно выбранным элементом не правее его

Мне всегда была непонятна необходимость этого условия. Если менять со случайно выбранным элементом (любым, а не только те, что не правее) — будет ровно такая же равномерная случайность. Можете, пожалуйста, подтвердить это картинкой?
Подтвердить не могу.
Заголовок спойлера

Любопытно. Значит я ошибался, а это тоже важно узнать, спасибо.

Интересно, а кто-то может объяснить, в чем изъян моей логики?
Мне затруднительно это сделать, поскольку мне неизвестен ход вашей мысли. Но я знал, что вы неправы, ещё до того, как запустил симуляцию. В результате n итераций, каждая из которых имеет n возможных равновероятных вариантов перестановки, мы получаем nn равновероятных вариантов перемешивания. В то же время возможных перестановок у нас n!. Чтобы перестановки оказались равновероятны, каждой из них должно соответствовать одинаковое количество вариантов перемешивания. Но nn не делится на n! для n > 3.
Звучит чертовски логично, спасибо.
Для n == 3 тоже не делится. А так всё верно.
Больше либо равно хотел написать, да.
Можете, пожалуйста, подтвердить это картинкой?
Как можно подтведить нечто очевидно неверное картинкой?

В вашем подходе на каждом шаге выбирается один из n исходов. Вы делаете n щагов. То есть получаете nⁿ вариантов. Правда некоторые из них одинаковы (скажем вариант 1, 2, 3, ..., n получится если ничего никуда не двигалось, но также если 1 попадёт на место 2, а потом вернётся и так далее). То есть вероястности у вас в конечном итогде поучаться вида kα/nⁿ. А нужно-то нам 1/n!. Как несложно заметить — это возможно только при n == 1 или n == 2. А для этих двух случаев и так всё понятно.

Мне всегда была непонятна необходимость этого условия.
Без этого условия нет факториала. Без факториала нет гарантированно правильного перемешивания. Всё просто.
Да, согласен со всеми вашими аргументами, видимо мне стоило больше подумать перед тем, как задавать тот вопрос.
Раз уж mk2 упомянул merge sort, то, кажется, было бы полезно наглядно продемонстрировать, почему сортировка случайным сравнением не работает. Пусть есть массив [1, 2, 3]. Пройдем самый простой алгоритм сортировки слиянием:
1) разбиваем на списки: [1], [2], [3]
2) сливаем соседние пары, первый слитый список получится честно случайным: [(1|2), (2|1)], [3].
3) а теперь финальное слияние сразу поставит тройку в начало с шансом 50%, и привет, должно было быть ~33%.
То же самое происходит при любых массивах не длины степени двойки: как только сливаются списки разных размеров, последний элемент более длинного имеет больший шанс попасть в конец результата.
Мне вот интереснее, для степени двойки получается действительно случайное перемешивание или нет.
Нет. Потому что при слиянии двух списков одинаковой длины вероятность того что первый и последний элементы будут взяты из разных списков больше 1/2.

Кстати, можно попробовать нарисовать картинку как часто элементы с указанными номерами оказываются рядом.
Правда ли, что если прогнать merge sort, но при сливании выбирать элемент с вероятностью пропорциональной остатку длины его списка, то получится равномерно случайное перемешивание в итоге? Похоже на то, на длинах 3 и 4 точно работает.
Да, правда. Это легко доказывается по индукции. Одна проблема: компаратор про длину списка не знает :-)
Я пытаюсь как-то строго сформулировать вопрос о том, существует ли сортировка, которая со случайным компаратором даст равномерное перемешивание. Но надо как-то отсечь случай, когда сортировка, допустим, совершает стопицот тестовых прогонов компаратора и дальше действует в зависимости от их результата.
Если время работы ограничено — то таких сортировок точно не существует. Просто потому что вероятность 1/n! нельзя «набрать» степенями двойки (т.е. представить в виде m/2k).

Среди алгоритмов с неограниченным временем работы такие сортировки точно есть. Например, Bogosort со случайным компаратором даст случайную перестановку (но затратит на это в среднем O(n 2n) времени!).
Сортировка с ограниченным временем работы не обязана быть детерминированной. Напримем, квиксорт со случайным выбором опорного элемента. Так что аргумент про степени двойки не канает.
Хм. Гениально. Сортировка даст равномерное перемешивание со случайным компаратором, если перед сортировкой массив случайно перемешать)))

Нет. Представим, что у нас массив [1,2,3,4]. Какова вероятность, что первые да из них будут 3 и 4 в каком-то порядке? 1/4 т.к перемешивание на нижнем уровне не влияет, а при слиянии двух массивов длины 2 нам нужно выбрать второй массив дважды. Какова вероятность должна быть? 4/24=1/6

Никто тут не сказал про Safari, покажу пару скринов:

на больших все нормально:
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
Sign up to leave a comment.

Articles