Почему алгоритм Collections.shuffle() работает лучше, чем моя реализация

Collections.shuffle() проходит через каждый индекс a Collection назад и затем свопит его со случайным индексом, включающим или перед ним. Мне было интересно, почему, поэтому я попытался сделать то же самое, но обмен с любым случайным индексом в Collection.

Вот перетасованная часть кода Collections.shuffle():

for (int i=size; i>1; i--)
    swap(arr, i-1, rnd.nextInt(i));

И вот мой алгоритм:

Random r = new Random();
for (int i = 0; i < a.size(); i++) {
    int index = r.nextInt(a.size());
    int temp = a.get(i);
    a.set(i, a.get(index));
    a.set(index, temp);
}

Я обнаружил, что Collections.shuffle() был гораздо более равномерно распределен, чем мой код, когда я запускал оба на одном и том же ArrayList миллион раз. Кроме того, при запуске моего кода:

[0, 1, 2, 3, 4]

кажется, что наиболее часто встречаются следующие перестановки:

[1, 0, 3, 4, 2]
[1, 2, 3, 4, 0]
[1, 2, 0, 4, 3]
[0, 2, 3, 4, 1]
[1, 2, 3, 0, 4]

Может кто-нибудь объяснить, почему?

Ответы

Ответ 1

Collections.Shuffle() выполняет Fisher-Yates shuffle. Это более равномерно распределенная форма перетасовки и не перетасовывает то, что уже ранее было перетасовано, в отличие от вашего алгоритма.

Что ваш алгоритм (также известный как наивная реализация) заключается в том, что он будет произвольно выбирать любой индекс массива и перетасовывать его, что означает, что существует высокая вероятность того, что он будет выбирать тот же индекс, который имеет ранее были перетасованы уже.

Перетасовка Fisher-Yates (также известная как Donald Knuth Shuffle) - это объективный алгоритм, который чередует элементы в массиве с равной вероятностью. Это позволяет избежать возможности, если он "перемещает" те же объекты дважды.

Здесь хорошее объяснение Fisher Yates Shuffle нашим собственным Джеффом Этвудом в Coding Horror, он обсуждает наивную реализацию случайного тасования против Фишера Йейта.

См. также этот вопрос SO о реализации Java. Он упоминает, что вы просили. Вы также можете посмотреть исходный код, если хотите, как упоминалось выше. Я нашел его по Googling Collections.Shuffle() в 5 лучших ссылках.

В будущем обсудите это, всегда рекомендуется использовать Shuffle Fisher-Yates по сравнению с наивными реализациями, особенно в тех реализациях, которые требуют более высокого уровня случайности (например, потасовки в покер), чтобы избежать появления шансов и несправедливой игры, Было бы нехорошо, если бы случайности, когда они были реализованы на основе нашей наивной реализации, , поскольку смещение приводит к тому, что вы наблюдали, где одна и та же перестановка, по-видимому, появляется чаще, чем другие.

Наконец,, как упоминал пользователь @jmruc, здесь очень хороший учебник по визуализации алгоритмов, он содержит Shuffle Fisher-Yates, а также другие алгоритмы, все красиво представленные. Можете помочь вам обернуть голову вокруг концепций, если вы больше визуализатор: Визуализация алгоритмов Майком Бостоком

Ответ 2

Это еще одно объяснение Фишер-Йейтс.

Рассмотрим следующий метод:

  • Есть два списка: A и B. Первоначально все элементы включены list A, поэтому список B пуст.

  • На каждом шаге:

    Выберите с равномерной вероятностью из элементов, находящихся в настоящее время в списке A.

    Переместить список A, чтобы сделать выбранный элемент последним.

    Удалите последний элемент из списка A и добавьте его в список B.

  • Когда список A пуст, верните список B.

Я считаю, что этот алгоритм легко понять и визуализировать.

Вероятность выбора выбранного элемента на первом шаге 1/n. Вероятность выбора выбранного элемента на втором шаге - это вероятность того, что он не будет выбран на первом шаге, (n-1)/n, раз его вероятность быть выбранным на втором шаге, если он все еще находится в списке A, 1/(n-1). Этот продукт 1/n.

Аналогично, у него есть вероятность ((n-1)/n)*((n-2)/(n-1)) = (n-2)/n по-прежнему находиться в списке A после перемещения двух элементов и, следовательно, вероятность 1/n быть выбранным третьим элементом.

В общем, вероятность того, что все еще находится в списке A после k элементов, выбрана ((n-1)/n)*((n-2)/(n-1))*...*((n-k)/(n-k+1)) = (n-k)/n. Вероятность выбора на следующем шаге, если элемент все еще находится в списке A, составляет 1/(n-k), поэтому безусловная вероятность выбирается на этапе, когда список A имеет (n-k) элементов ((n-k)/n)*(1/(n-k)) = 1/n.

Fisher-Yates - это просто этот алгоритм с двумя списками, общая длина которых всегда n, объединенная в один массив. На каждом шаге он выбирает элемент из списка A с равномерной вероятностью, переставляет список A, чтобы поместить этот элемент в список B, а затем перемещает границу так, чтобы она менялась от того, что элемент списка A является последним добавленным элементом список B.