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

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

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

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

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

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

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

// The shuffle function posted by Cristoph.
var shuffle = function(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;
};

// the random sort function
var rnd = function() {
  return Math.round(Math.random())-0.5;
};
var randSort = function(A) {
  return 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 = permutations(xs);
      for (var j=0; j<subperms.length; j++) {
        perms.push(x.concat(subperms[j]));
      }
    }
    return perms;
  }
};

var test = function(A, iterations, func) {
  // init permutations
  var stats = {};
  var perms = permutations(A);
  for (var i in perms){
    stats[""+perms[i]] = 0;
  }

  // shuffle many times and gather stats
  var start=new Date();
  for (var i=0; i<iterations; i++) {
    var shuffled = func(A);
    stats[""+shuffled]++;
  }
  var end=new Date();

  // format result
  var arr=[];
  for (var i in stats) {
    arr.push(i+" "+stats[i]);
  }
  return arr.join("\n")+"\n\nTime taken: " + ((end - start)/1000) + " seconds.";
};

alert("random sort: " + test([1,2,3,4], 100000, randSort));
alert("shuffle: " + test([1,2,3,4], 100000, shuffle));

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

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 для пузырьковой сортировки. Наша функция случайного сравнения делает результат каждого сравнения одинаково вероятным, т. Е. Существует 2 ^ c равновероятных результатов. Теперь каждый результат должен соответствовать одной из n! перестановок элементов массива, что делает невозможным равномерное распределение в общем случае. (Это упрощение, поскольку фактическое количество необходимых сравнений зависит от входного массива, но утверждение все равно должно оставаться в силе.)

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

Math.random () производит псевдослучайное число в диапазоне [0; 1 []. Поскольку JS использует значения с плавающей запятой двойной точности, это соответствует 2 ^ x возможным значениям, где 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! является крайним случаем), в противном случае все ставки отключены.

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

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

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

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

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

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

Конечно, это взлом. На практике алгоритм с бесконечным циклом маловероятен. Если вы сортируете объекты, вы можете пройти через массив 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)

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

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

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

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

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

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

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

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

Как в MySQL:

SELECT * from table ORDER BY rand()

Интересно, что 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"));