Какова эффективность и качество этого алгоритма тасования?

Question

Этот недавний вопрос о случайной сортировке с использованием C # заставил меня задуматься о том, как я иногда перетасовывал свои массивы в Perl.

@shuffled = sort { rand() <=> rand() } @array;

Предложенное решение в упомянутом вопросе: Фишер-Йейтс shuffle , которое работает за линейное время.

Вопрос в том, насколько эффективен мой фрагмент и действительно ли такая случайность "действительно" случайна?

Answer 1

Я не эксперт по внутренним компонентам Perl, поэтому не знаю, как здесь будет работать sort. Тем не менее, большинство функций сортировки ожидают последовательности в своих сравнениях, и я ожидаю, что они будут работать непредсказуемо, если функция сама является случайной. К сожалению, непредсказуемость не такая же, как случайность, и поэтому я не буду доверять вашему перетасованному массиву. Это может привести к тому, что элементы будут расположены в некотором порядке, подобно тому, как спешно созданные и сложные рекуррентные отношения могут быть не случайными.

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

Как сказал Кнут, случайность слишком важна, чтобы ее можно было оставить на волю случая.

Answer 2

$ perldoc List::Util
⋮
  shuffle LIST
       Returns the elements of LIST in a random order

           @cards = shuffle 0..51      # 0..51 in a random order
⋮

Это было бы мое предложение.

Answer 3

Я на самом деле немного удивлен, что ваш предложенный случайный порядок работает. В реализации функции Perl sort она пытается привести элементы массива в порядке возрастания в зависимости от значения функции сравнения. Проблема в том, что ваша функция сравнения не возвращает последовательных ответов! Иногда это может сказать "foo" lt "bar", в то время как в других случаях это может сказать "bar" lt "foo". Это может привести к путанице в алгоритме сортировки до такой степени, что он никогда не завершится или не завершится с фатальной ошибкой или каким-либо другим катастрофическим отказом.

Answer 4

Во-первых, вы знаете, что независимо от того, какой компаратор вы используете, sort () не может быть быстрее, чем O (n log n). Так что, даже если тасовка, которую он выполняет, будет честной, ее производительность будет хуже.

Так что же, ярмарка в случайном порядке? Очевидно, это не справедливо для некоторых (легко анализируемых) алгоритмов сортировки. Рассмотрим простую пузырьковую сортировку - для того, чтобы элемент переместился с одного конца на другой, функция сравнения должна оценить положительное значение для n последовательных вызовов - вероятность 1 в 2 ^ n для того, что должно быть событием 1 в n. Для быстрой сортировки сложно проанализировать, и возможно, что в итоге получится честно. Но если важно, чтобы это было правильно, делай это правильно.

Answer 5

Документация Perl на sort говорит это

Функция сравнения обязана вести себя. Если он возвращает противоречивые результаты (иногда говоря, что $ x [1] меньше, чем $ x [2], а иногда, например, говоря обратное)), результаты не будут четко определены.

Так что это плохая идея.

ETA: Я только что сделал тест. В массиве из 100000 элементов использование FY-shuffle также более чем в 10 раз быстрее.

Answer 6

Есть лучшая функция случайного перемешивания Фишера-Йейтса, которая не использует встроенную sort в perlfaq4: как я могу случайным образом перемешивать массив? .

Answer 7

Это просто интуиция, но я думаю, что использование такой сортировки даст набор, порядок которого в некоторой степени зависит от порядка исходного набора. Результаты действительно случайной сортировки вообще не должны зависеть от порядка исходного набора. Я не могу объяснить, почему / как, может быть, кто-то еще может (или показать, что это на самом деле случайно)?

Что касается эффективности, я не уверен, но, вероятно, она не намного менее эффективна, чем любая другая сортировка, использующая sort, поскольку AFAIK rand() относительно дешев Хотя я могу ошибаться.

Answer 8

@shuffled = map {
  $_->[1]
} sort {
  $a->[0] <=> $b->[0]
} map {
  [ rand(), $_ ]
} @array;