Правильно ли использовать метод JavaScript Array.sort () для перемешивания? - PullRequest
Новая
       69

Правильно ли использовать метод JavaScript Array.sort () для перемешивания?

124 голосов
/ 08 июня 2009

Я помогал кому-то с его JavaScript-кодом, и мои глаза привлекли внимание к следующему разделу: 

function randOrd(){
  return (Math.round(Math.random())-0.5);
}
coords.sort(randOrd);
alert(coords);

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

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

Но мое внутреннее чувство говорит мне, что это должно быть неправильно. Тем более что алгоритм сортировки не указан стандартом ECMA. Я думаю, что разные алгоритмы сортировки приведут к различным неравномерным перемешиваниям. Некоторые алгоритмы сортировки могут, вероятно, даже зацикливаться бесконечно ...

Но что вы думаете?

И в качестве еще одного вопроса ... как бы я теперь оценил, насколько случайны результаты этой техники перетасовки?

обновление: Я сделал несколько измерений и опубликовал результаты ниже как один из ответов.

Ответы [ 12 ]

0 голосов
/ 24 февраля 2012

Можете ли вы использовать функцию Array.sort() для перемешивания массива - Да.

Достаточно ли случайны результаты - Нет.

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

var array = ["a", "b", "c", "d", "e"];
var stats = {};
array.forEach(function(v) {
  stats[v] = Array(array.length).fill(0);
});
//stats = {
//    a: [0, 0, 0, ...]
//    b: [0, 0, 0, ...]
//    c: [0, 0, 0, ...]
//    ...
//    ...
//}
var i, clone;
for (i = 0; i < 100; i++) {
  clone = array.slice(0);
  clone.sort(function() {
    return Math.random() - 0.5;
  });
  clone.forEach(function(v, i) {
    stats[v][i]++;
  });
}

Object.keys(stats).forEach(function(v, i) {
  console.log(v + ": [" + stats[v].join(", ") + "]");
})

Пример вывода: 

a [29, 38, 20,  6,  7]
b [29, 33, 22, 11,  5]
c [17, 14, 32, 17, 20]
d [16,  9, 17, 35, 23]
e [ 9,  6,  9, 31, 45]

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

Дополнительная информация предоставляется в этой статье:
Array.sort () не должен использоваться для перемешивания массива

0 голосов
/ 08 июня 2009

В этом нет ничего плохого.

Функция, которую вы передаете .sort () обычно выглядит как 

function sortingFunc( first, second )
{
  // example:
  return first - second ;
}

Ваша задача в sortingFunc - вернуть:

  • отрицательное число, если первый идет перед вторым
  • положительное число, если первое должно идти после второго
  • и 0, если они полностью равны

Вышеуказанная функция сортировки упорядочивает вещи.

Если вы в случайном порядке возвращаете «+» и «+», вы получаете случайный порядок.

Как в MySQL: 

SELECT * from table ORDER BY rand()
Страница:
...