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

Я помогал кому-то с его кодом JavaScript, и мой взгляд привлек раздел, который выглядел так:

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

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

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

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

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

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

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

Это никогда не было моим любимым способом перетасовки, отчасти потому, что, как вы говорите, он зависит от конкретной реализации. В частности, я, кажется, помню, что стандартная сортировка библиотек из Java или .NET (не уверен, какие из них) часто может обнаружить, если вы в конечном итоге получите несогласованное сравнение между некоторыми элементами (например, вы сначала заявляете A < Bи B < C, а затем C < A).

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

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

Это O (n) и требует только n-1 вызовов генератора случайных чисел, что хорошо. Он также производит настоящее перемешивание - любой элемент имеет шанс 1 / n оказаться в каждом месте, независимо от его исходной позиции (при разумном ГСЧ). Отсортированная версия приближается к равномерному распределению (при условии, что генератор случайных чисел не выбирает одно и то же значение дважды, что маловероятно, если он возвращает случайные двойные значения), но мне легче рассуждать о версии с перемешиванием :)

Этот подход называется перетасовкой Фишера-Йетса .

Я бы счел лучшей практикой закодировать это перемешивание один раз и повторно использовать его везде, где вам нужно перемешивать элементы. Тогда вам не нужно беспокоиться о реализациях сортировки с точки зрения надежности или сложности. Это всего лишь несколько строк кода (которые я не буду использовать в JavaScript!)

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

После того, как Джон уже рассмотрел теорию , вот реализация:

function shuffle(array) {
    var tmp, current, top = array.length;

    if(top) while(--top) {
        current = Math.floor(Math.random() * (top + 1));
        tmp = array[current];
        array[current] = array[top];
        array[top] = tmp;
    }

    return array;
}

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

В комментариях к ответу bobobobo я заявил, что рассматриваемый алгоритм может не давать равномерно распределенные вероятности (в зависимости от реализации sort()).

Мой аргумент состоит в следующем : алгоритм сортировки требует определенного количества cсравнений, например, c = n(n-1)/2для Bubblesort. Наша функция случайного сравнения делает результат каждого сравнения равновероятным, т.е. есть 2^c равновероятные результаты. Теперь каждый результат должен соответствовать одной из n!перестановок элементов массива, что делает невозможным равномерное распределение в общем случае. (Это упрощение, поскольку фактическое количество необходимых сравнений зависит от входного массива, но утверждение все равно должно оставаться в силе.)

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

Math.random()производит псевдослучайное число в диапазоне [0;1[. Поскольку JS использует значения с плавающей запятой двойной точности, это соответствует 2^xвозможным значениям where 52 ≤ x ≤ 63(мне лень находить фактическое число). Распределение вероятностей, сгенерированное с помощью Math.random(), перестанет работать хорошо, если количество атомных событий будет того же порядка величины.

При использовании Fisher-Yates соответствующим параметром является размер массива, который никогда не должен приближаться 2^52из-за практических ограничений.

При сортировке с помощью функции случайного сравнения функция в основном заботится только о том, является ли возвращаемое значение положительным или отрицательным, поэтому это никогда не будет проблемой. Но есть и похожий: поскольку функция сравнения хорошо работает, 2^cвозможные результаты, как указано, равновероятны. Если, c ~ n log nто 2^c ~ n^(a·n)где a = const, что делает это, по крайней мере, возможным, что 2^cимеет ту же величину (или даже меньше) n!и, таким образом, приводит к неравномерному распределению, даже если алгоритм сортировки равномерно отображает перестановки. Если это имеет какое-либо практическое влияние, я не понимаю.

Настоящая проблема в том, что алгоритмы сортировки не гарантируют равномерного отображения на перестановки. Легко видеть, что Mergesort делает, поскольку он симметричен, но рассуждения о чем-то вроде Bubblesort или, что более важно, Quicksort или Heapsort - нет.

sort()Итог : пока используется Mergesort, вы должны быть в достаточной безопасности, за исключением крайних случаев (по крайней мере, я надеюсь, что 2^c ≤ n!это крайний случай), если нет, все ставки отключены.

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

Моя техника заключалась в том, чтобы взять небольшой массив [1,2,3,4] и создать все (4! = 24) его перестановки. Затем я бы применил функцию перетасовки к массиву большое количество раз и подсчитал, сколько раз генерируется каждая перестановка. Хороший алгоритм перетасовки распределил бы результаты довольно равномерно по всем перестановкам, в то время как плохой не дал бы такого единообразного результата.

Используя приведенный ниже код, я тестировал в Firefox, Opera, Chrome, IE6 / 7/8.

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

РЕДАКТИРОВАТЬ: этот тест на самом деле не правильно измерил случайность или ее отсутствие. См. Другой ответ, который я опубликовал.

Но с точки зрения производительности функция перемешивания, данная Кристофом, была явным победителем. Даже для небольших массивов из четырех элементов реальная перестановка выполняется примерно в два раза быстрее, чем произвольная сортировка!

// Функция перемешивания, отправленная Кристофом.
var shuffle = function (array) {
    var tmp, current, top = array.length;

    if (вверху) while (- вверху) {
        current = Math.floor (Math.random () * (верх + 1));
        tmp = массив [текущий];
        массив [текущий] = массив [верх];
        массив [вверху] = tmp;
    }

    возвратный массив;
};

// функция случайной сортировки
var rnd = function () {
  return Math.round (Math.random ()) - 0,5;
};
var randSort = function (A) {
  вернуть A.sort (rnd);
};

var permutations = function (A) {
  if (A.length == 1) {
    return [A];
  }
  else {
    var perms = [];
    for (var i = 0; i <A.length; i ++) {
      var x = A.slice (i, i + 1);
      var xs = A.slice (0, i) .concat (A.slice (i + 1));
      var subperms = перестановки (xs);
      for (var j = 0; j <subperms.length; j ++) {
        perms.push (x.concat (subperms [J]));
      }
    }
    обратная завивка;
  }
};

var test = function (A, iterations, func) {
  // инициализация перестановок
  var stats = {};
  var perms = перестановки (A);
  for (var i in perms) {
    статистика ["" + perms [i]] = 0;
  }

  // перемешать много раз и собрать статистику
  var start = new Date ();
  for (var i = 0; i <итераций; i ++) {
    var shuffled = func (A);
    Статистика [ "" + перетасовал] ++;
  }
  var end = новая дата ();

  // форматируем результат
  var arr = [];
  for (var i в статистике) {
    arr.push (i + "" + stats [i]);
  }
  return arr.join ("\ n") + "\ n \ nВремя:" + ((конец - начало) / 1000) + "секунды.";
};

предупреждение ("случайная сортировка:" + тест ([1,2,3,4], 100000, randSort));
alert ("перемешать:" + тест ([1,2,3,4], 100000, перемешать));

Интересно, что Microsoft использовала ту же технику на своей странице выбора случайного браузера.

Они использовали немного другую функцию сравнения:

function RandomSort(a,b) {
    return (0.5 - Math.random());
}

На мой взгляд, почти то же самое, но оказалось, что это не так уж и случайно ...

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

function shuffle(arr) {
  arr.sort(function(a,b) {
    return (0.5 - Math.random());
  });
}

function shuffle2(arr) {
  arr.sort(function(a,b) {
    return (Math.round(Math.random())-0.5);
  });
}

function shuffle3(array) {
  var tmp, current, top = array.length;

  if(top) while(--top) {
    current = Math.floor(Math.random() * (top + 1));
    tmp = array[current];
    array[current] = array[top];
    array[top] = tmp;
  }

  return array;
}

var counts = [
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0]
];

var arr;
for (var i=0; i<100000; i++) {
  arr = [0,1,2,3,4];
  shuffle3(arr);
  arr.forEach(function(x, i){ counts[x][i]++;});
}

alert(counts.map(function(a){return a.join(", ");}).join("\n"));

Я разместил на своем веб-сайте простую тестовую страницу, показывающую предвзятость вашего текущего браузера по сравнению с другими популярными браузерами с использованием различных методов перемешивания. Это показывает ужасную предвзятость простого использования Math.random()-0.5, еще одного беспристрастного «случайного» перемешивания и упомянутого выше метода Фишера-Йейтса.

Вы можете видеть, что в некоторых браузерах вероятность того, что некоторые элементы вообще не поменяются местами во время «перемешивания», достигает 50%!

Примечание: вы можете немного ускорить реализацию перемешивания Фишера-Йейтса с помощью @Christoph для Safari, изменив код на:

function shuffle(array) {
  for (var tmp, cur, top=array.length; top--;){
    cur = (Math.random() * (top + 1)) << 0;
    tmp = array[cur]; array[cur] = array[top]; array[top] = tmp;
  }
  return array;
}

Результаты тестов: http://jsperf.com/optimized-fisher-yates

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

В JavaScript (где исходный код передается постоянно) small имеет значение в стоимости полосы пропускания.

Конечно, это взлом. На практике алгоритм с бесконечным циклом маловероятен. Если вы сортируете объекты, вы можете пройти через массив coords и сделать что-то вроде:

for (var i = 0; i < coords.length; i++)
    coords[i].sortValue = Math.random();

coords.sort(useSortValue)

function useSortValue(a, b)
{
  return a.sortValue - b.sortValue;
}

(а затем снова пропустите их, чтобы удалить sortValue)

Тем не менее, это все еще хак. Если вы хотите сделать это красиво, вы должны делать это тяжело :)

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

Доказательство:

1. Для массива nэлементов есть точно n!перестановки (т. Е. Возможные перетасовки).
2. Каждое сравнение во время перемешивания - это выбор между двумя наборами перестановок. Для случайного компаратора есть 1/2 шанса выбрать каждый набор.
3. Таким образом, для каждой перестановки p шанс получить перестановку p представляет собой дробь со знаминателем 2 ^ k (для некоторого k), потому что это сумма таких дробей (например, 1/8 + 1/16 = 3/16 ).
4. Для n = 3 существует шесть равновероятных перестановок. Таким образом, шанс каждой перестановки равен 1/6. 1/6 не может быть выражена дробью со степенью 2 в качестве знаменателя.
5. Следовательно, сортировка подбрасыванием монеты никогда не приведет к справедливому распределению тасовок.

Единственные размеры, которые можно было бы правильно распределить, - это n = 0,1,2.

В качестве упражнения попробуйте нарисовать дерево решений различных алгоритмов сортировки для n = 3.

В доказательстве есть пробел: если алгоритм сортировки зависит от согласованности компаратора и имеет неограниченное время выполнения с несовместимым компаратором, он может иметь бесконечную сумму вероятностей, которая может составлять до 1/6, даже если каждый знаменатель в сумме равен степени 2. Попытайтесь найти один.

Кроме того, если компаратор имеет фиксированный шанс дать любой ответ (например (Math.random() < P)*2 - 1, для константы P), приведенное выше доказательство остается в силе. Если вместо этого компаратор изменит свои шансы на основе предыдущих ответов, возможно, удастся получить справедливые результаты. Поиск такого компаратора для данного алгоритма сортировки может быть исследовательской работой.

Если вы используете D3, есть встроенная функция перемешивания (с использованием Fisher-Yates):

var days = ['Lundi','Mardi','Mercredi','Jeudi','Vendredi','Samedi','Dimanche'];
d3.shuffle(days);

И вот Майк подробно рассказывает об этом:

http://bost.ocks.org/mike/shuffle/

Вот подход, который использует один массив:

Основная логика:

Код:

for(i=a.length;i--;) a.push(a.splice(Math.floor(Math.random() * (i + 1)),1)[0]);

Можете ли вы использовать эту 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 () не следует использовать для перетасовки массива.

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

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

функция sortingFunc (первая, вторая)
{
  // пример:
  возврат первый - второй;
}

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

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

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

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

Как в MySQL:

ВЫБРАТЬ * из таблицы ORDER BY rand ()