эй, это не может работать!

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

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

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

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

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

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

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

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

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

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

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

Этот подход называется on пришел из разумного источника, вы ‘ все в порядке. Глядя на вывод

Статья в Википедии о тасовании

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

рассмотрел теорию , вот реализация: Алгоритм —

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) Не знаю, является ли он надежным до сих пор sort() в производительности , который должен увеличиваться с размерами массива. В комментариях к ответу


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

для Bubblesort. Наша функция случайного сравнения делает результат каждого сравнения одинаково вероятным, т. е. есть c Если вам нужен доступ к консоли в IE6 для IE7, используйте букмарклет Firebug Lite c = n(n-1)/2 одинаково вероятные 2^c результаты. Теперь каждый результат должен соответствовать одной из перестановок записи массива, что делает равномерное распределение невозможным в общем случае. (Это упрощение, поскольку фактическое число необходимых сравнений зависит от входного массива, но утверждение все еще должно сохраняться.) n! Как указал Джон, это само по себе не является причиной для предпочтения Фишера-Йейтса, а не использования

, поскольку генератор случайных чисел также отобразит конечное число псевдослучайных значений в sort(). Поскольку JS использует значения с плавающей запятой двойной точности, это соответствует n! Он работает на нескольких ОС и имеет встроенную отладку Node.js (а также кучу других вещей) (

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

. Проще говоря, у вас есть заголовок таблицы, который вы визуально скрываете, делая его высотой 0px, который также содержит div, используемый в качестве фиксированного заголовка. Контейнер таблицы оставляет достаточно места наверху, чтобы обеспечить абсолютно позиционированный заголовок, и таблица с полосами прокрутки выглядит так, как вы ожидаете. 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.

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

Мы только что выпустили Этот тест не совсем правильно измерил случайность или ее отсутствие. Смотрите другой ответ, который я написал.

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

// 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") "nnTime taken: "   ((end - start)/1000)   " seconds.";
};

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

Интересно, что 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 % вероятность того, что некоторые элементы не изменятся вообще во время «перемешивания»!

Примечание: вы можете сделать реализацию Shuffle Фишера-Йейтса с помощью @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;
}

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

В JavaScript (где источник передается постоянно), small имеет значение в затратах на пропускную способность.

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

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. Таким образом, сортировка по монетам никогда не приведет к справедливому распределению перемешиваний.

JavaScript — регулярное выражение для соответствия не-ASCII символов?


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


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

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

Если вы используете D3, то есть встроенная функция случайного выбора (с использованием Фишера-Йейтса): А вот Майк подробно расскажет об этом:

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

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

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

Основная логика: Начиная с массива из n элементов

Удалить случайный элемент из массива и поместить его в массив

  • Удалить случайный элемент из первых n — 1 элементов массива и вставить его в массив
  • Удалите случайный элемент из первых n — 2 элементов массива и поместите его в массив
  • Удалите первый элемент массива и поместите его в массив
  • Вы можете использовать функцию
  • , чтобы перетасовать массив — Да.
  • потому что это не итератор, и

    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 () обычно выглядит примерно так:

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

    Ваша задача в sortingFunc — возвращать:

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

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

    Нажмите «Найти», не выбрав ни одного радио

    Как и в MySQL:

    SELECT * from table ORDER BY rand()