Почему этот алгоритм случайности не смещен - PullRequest
Новая
       23

Почему этот алгоритм случайности не смещен

6 голосов
/ 08 июля 2011

Мой коллега и я спорим о том, почему алгоритм shuffle, приведенный в этом списке советов и приемов JS , не дает необъективных результатов, подобных тому, который Джефф Этвуд описывает для наивных перемешиваний .

Массив кода перемешивания в подсказках: 

list.sort(function() Math.random() - 0.5);

Наивный код случайного воспроизведения Джеффа: 


for (int i = 0; i < cards.Length; i++)
{
  int n = rand.Next(cards.Length);
  Swap(ref cards[i], ref cards[n]);
}

Я написал этот JS для проверки шаффла: 


var list = [1,2,3];
var result = {123:0,132:0,321:0,213:0,231:0,312:0};
function shuffle() { return Math.random() - 0.5; }
for (var i=0; i<60000000; i++) {
    result[ list.sort(shuffle).join('') ]++;
}

Для которого я получаю результаты (из Firefox 5), например: 

Order   Count          %Diff True Avg
123      9997461       -0.0002539
132     10003451        0.0003451
213     10001507        0.0001507
231      9997563       -0.0002437
312      9995658       -0.0004342
321     10004360        0.000436

Предположительно Array.sort обходит массив list и выполняет обмен (смежными) элементами, как в примере Джеффа. Так почему же результаты не выглядят необъективно?

Ответы [ 3 ]

2 голосов
/ 08 июля 2011

Я нашел причину, по которой кажется несмещенным.

Array.sort () не только возвращает массив, но и меняет сам массив.Если мы повторно инициализируем массив для каждого цикла, мы получим результаты, такие как: 

123 14941
132 7530
321 7377
213 15189
231 7455
312 7508

, что показывает очень существенное смещение.

Для заинтересованных лиц вот модифицированный код: 

var result = {123:0,132:0,321:0,213:0,231:0,312:0};
var iterations = 60000;
function shuffle() { 
    comparisons++;
    return Math.random() - 0.5;
}
for (var i=0; i<iterations; i++) {
    var list = [1,2,3];
    result[ list.sort(shuffle).join('') ]++;
}
console.log(result);
1 голос
/ 08 июля 2011

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

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

Перемешивание Кнута-Фишера-Йейтса отличается от случайного перемешивания, поскольку вы выбираете карту только один раз,Если бы вы выбирали случайные карты из колоды, вы бы положили карту обратно и забрали снова?Нет, вы берете случайные карты по одной за раз.Это первое, что я слышал об этом, но я делал нечто подобное еще в старшей школе, начиная с индекса 0 и выше.KFY, вероятно, быстрее, потому что у меня есть дополнительное дополнение в случайном выражении. 

for (int i = 0; i < cards.Length - 1; i++)
{
  int n = rand.Next(cards.Length - i) + i; // (i to cards.Length - 1)
  Swap(ref cards[i], ref cards[n]);
}

Не думайте об этом как об обмене, думайте об этом как о выборе случайных карт из колоды.Для каждого элемента в массиве (кроме последнего, потому что остался только один) вы выбираете случайную карту из всех оставшихся карт и кладете ее, образуя новую стопку карт, которые перемешиваются случайным образом.Неважно, что ваши оставшиеся карты больше не находятся в исходном порядке, если вы уже сделали какой-либо обмен, вы все равно выбираете одну случайную карту из всех оставшихся карт.

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

0 голосов
/ 08 июля 2011

На самом деле, это не реализует его наивную случайную сортировку. Его алгоритм фактически транспонирует ключи массива вручную, а сортировка активно сортирует список.

сортировка использует быструю сортировку или сортировку вставкой (спасибо cwolves за указание на это - см. Комментарии), чтобы сделать это (это будет зависеть от реализации):

  1. А больше или меньше, чем В? Меньшие? Декремент.
  2. А больше или меньше С? Меньшие? Декремент.
  3. А больше или меньше D? Меньшие? Вставить A после D
  4. B больше или меньше C? Меньшие? Декремент.
  5. B больше или меньше D? Меньшие? Вставьте B после D и до A ...

Это означает, что ваш большой O для среднего случая равен O (n log n), а ваш большой O для худшего случая - O (n ^ 2) для каждой итерации цикла.

Между тем наивная случайная сортировка Этвуда проста:

  1. Начать с А. Найти случайное значение. Своп.
  2. Перейти к B. Найти случайное значение. Своп.
  3. Перейти к C. Найти случайное значение. Своп.

(Кнут-Фишер-Йейтс почти такой же, только в обратном направлении)

Таким образом, его имеет большой для наихудшего случая O (n) и большой O для среднего случая O (n).

...