Чем больше вы знаете, тем больше вы не знаете
点赞Посмотри еще раз, аромат остался в руке, и слава
введение
Перетасовка массива относится к случайному перетасовке порядка расположения элементов массива.
Это очень простое, но очень распространенное требование перетасовать массив. Например, «думаю, вам это нравится», «щелкните, чтобы изменить пакет», «план победителя» и т. д. — все это может применяться к такой обработке.
сортировка в сочетании с Math.random
Microsoft однажды проводила опрос на browserchoice.eu об использовании разных браузеров, и Microsoft показывала пользователям разные браузеры в случайном порядке на странице.
Однако место, где появляется каждый браузер, не случайно. Вероятность того, что IE окажется на последней позиции, составляет около 50%, а Chrome в большинстве случаев окажется в тройке лучших браузеров.
Что здесь происходит, разве это не случайный порядок?
Вот код, который они используют для случайного перемешивания:
arr.sort(() =>Math.random() - 0.5);
На первый взгляд, это кажется разумным решением. На самом деле, используя поисковую систему для поиска «случайного перетасованного массива», этот метод будет наиболее подходящим ответом.
Впрочем, этот способ не совсем уж из ряда вон выходящий, некоторые элементы не имеют шансов сравниться друг с другом, Вероятность того, где останется последний элемент массива, не является полностью случайной.
Давайте посмотрим пример:
/**
* 数组乱序
*/
function shuffle(arr) {
return arr.sort(() => Math.random() - 0.5);
}
/**
* 用于验证 shuffle 方法是否完全随机
*/
function test_shuffle(shuffleFn) {
// 多次乱序数组的次数
let n = 100000;
// 保存每个元素在每个位置上出现的次数
let countObj = {
a:Array.from({length:10}).fill(0),
b:Array.from({length:10}).fill(0),
c:Array.from({length:10}).fill(0),
d:Array.from({length:10}).fill(0),
e:Array.from({length:10}).fill(0),
f:Array.from({length:10}).fill(0),
g:Array.from({length:10}).fill(0),
h:Array.from({length:10}).fill(0),
i:Array.from({length:10}).fill(0),
j:Array.from({length:10}).fill(0),
}
for (let i = 0; i < n; i ++) {
let arr = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'];
shuffleFn(arr);
countObj.a[arr.indexOf('a')]++;
countObj.b[arr.indexOf('b')]++;
countObj.c[arr.indexOf('c')]++;
countObj.d[arr.indexOf('d')]++;
countObj.e[arr.indexOf('e')]++;
countObj.f[arr.indexOf('f')]++;
countObj.g[arr.indexOf('g')]++;
countObj.h[arr.indexOf('h')]++;
countObj.i[arr.indexOf('i')]++;
countObj.j[arr.indexOf('j')]++;
}
console.table(countObj);
}
//验证 shuffle 方法是否随机
test_shuffle(shuffle)
В этом примере мы определяем две функции: используем sort и Math.random() в shuffle для перемешивания массива; Функция test_shuffle определяет массив длиной 10 ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j '], И используйте входящую неупорядоченную функцию для выполнения 100 000 операций, и сохраните количество раз, когда каждый элемент массива появляется в каждой позиции в переменной countObj, и, наконец, распечатайте countObj.
Результат выглядит следующим образом:
Из этой таблицы видно, что вероятность появления каждого элемента в каждой позиции сильно различается, например, элемент a, 19415 вхождений по индексу 0 и только 7026 по индексу 4, Количество вхождений элемента a в эти две позиции очень разное (разница более чем в два раза). Если порядок действительно случайный, то каждый элемент должен иметь одинаковую вероятность появления в каждой позиции. Числа для каждого местоположения в экспериментальных результатах должны быть очень близкими, а не числами, которые сильно различаются, как сейчас.
Почему возникла проблема? Это нужно начинать с нижнего слоя метода array.sort.
V8 При сортировке метода обработки используя быструю вставку и разрядить два варианта. Когда цель меньше длины массива 10, используя сортировку вставки; наоборот, используя быстрый сортировку.
На самом деле, независимо от того, какой метод сортировки используется, временная сложность большинства алгоритмов сортировки находится между O(n) и O(n²). Количество сравнений между элементами обычно намного меньше n(n-1)/2, т.е. Это означает, что некоторые элементы вообще не имеют шансов сравниться (и нет возможности случайного обмена), Эти алгоритмы сортировки для случайной сортировки, естественно, не могут быть действительно случайными.
На самом деле, мы хотим использовать array.sort для неупорядочения, Идеальное решение или чистое решение неупорядочения состоит в том, чтобы сравнивать каждые два элемента в массиве. Это сравнение имеет 50% вероятность обмена позициями. Таким образом, общее количество сравнений должно быть n(n-1). В алгоритме сортировки сортировкой это условие в большинстве случаев не выполняется. Так что, конечно, это не совсем случайный результат.
Неполное сравнение сортировки с сортировкой вставками
Простой код сортировки вставкой:
function insertSort(list = []) {
for(let i = 1 , len = list.length; i < len; i++){
let j = i - 1;
let temp = list[ i ];
while (j >= 0 && list[ j ] > temp){
list[j + 1] = list[ j ];
j = j - 1;
}
list[j + 1] = temp;
}
return list;
}
Принцип состоит в том, чтобы рассматривать первый элемент как упорядоченную последовательность, проходить массив и вставлять последующие элементы в построенную упорядоченную последовательность по очереди.
Возьмем простую схему:
Результаты [«A», «B», «C»] массива Crambraded наш конкретный анализ, следует отметить, что из-за длины массива меньше 10, функция внутренней сортировки реализуется с использованием сортировки вставки.
Демо-код:
var values = ['a', 'b', 'c'];
values.sort(function(){
return Math.random() - 0.5;
});
Подробный анализ выглядит следующим образом:
Поскольку сортировка вставками обрабатывает первый элемент как упорядоченный, внешний цикл массива начинается с i = 1. сравните a и b в этой точке , так как результат Math.random() - 0.5 с вероятностью 50 % будет меньше 0 и с вероятностью 50 % будет больше 0, поэтому с вероятностью 50 % массив станет ['b',' a','c'], 50% результатов не изменились, массив по-прежнему ['a','b','c'].
Предполагая, что это все еще ['a','b','c'], мы делаем еще один анализ, а затем проходим, i = 2, сравниваем b и c:
Существует 50% вероятность того, что массив останется неизменным, по-прежнему ['a','b','c'], и тогда обход закончится.
Существует 50% вероятность стать ['a', 'c', 'b'], потому что правильная позиция c не найдена, она все равно будет пройдена, поэтому в этой 50% вероятности будет другое сравнение сделано, Сравнивая a и c, есть вероятность 50%, что вероятность остается неизменной, а массив равен ['a','c','b']. В это время обход заканчивается, и есть 50 % вероятность того, что вероятность изменится, и массив станет ['c', 'a','b'].
Таким образом, в ['a','b','c'] существует 50% вероятность того, что он станет ['a','b','c'], и 25% вероятность того, что он станет стать ['a','c','b'], существует 25% вероятность того, что он станет ['c', 'a', 'b'].
Другой случай ['b','a','c'] аналогичен анализу, и мы суммируем окончательные результаты в таблице:
Измените комбинацию sort и Math.random()
Мы уже знаем проблемы с sort и Math.random() для достижения беспорядка массива, В основном из-за отсутствия сравнения между каждым элементом, мы могли бы также преобразовать элементы массива, Превратите его в объект.
let arr = [
{
val:'a',
ram:Math.random()
},
{
val:'b',
ram:Math.random()
}
//...
]
Сохраняем исходное значение в массиве в свойстве val объекта, а к объекту добавляем свойство ram со случайным числом.
Далее нам просто нужно отсортировать случайные числа каждого объекта в массиве, чтобы получить перетасованный массив.
код показывает, как показано ниже:
function shuffle(arr) {
let newArr = arr.map(item=>({val:item,ram:Math.random()}));
newArr.sort((a,b)=>a.ram-b.ram);
arr.splice(0,arr.length,...newArr.map(i=>i.val));
return arr;
}
Примените метод shuffle к функции проверки test_shuffle, которую мы реализовали ранее.
test_shuffle(shuffle)
Результат выглядит следующим образом:
Из таблицы видно, что количество появлений каждого элемента в каждой позиции не сильно отличается.
Хотя требование случайности было соблюдено, эта реализация не очень хороша в производительности, ей нужно несколько раз обходить массив, а также выполнять операции склеивания над массивом.
Итак, как добиться высокой производительности в реальном порядке? Здесь необходимо упомянуть классический алгоритм Фишера-Йейтса.
Фишер-Йейтс
Почему он называется Фишер-Йейтс? Потому что этот алгоритм был впервые предложен Рональдом Фишером и Фрэнком Йейтсом.
Этот алгоритм на самом деле очень прост, он заключается в обходе массива сзади наперед, а затем обмене текущего элемента с элементом в случайной позиции. Объясните с картинками:
Сначала у нас есть отсортированный массив
Шаг 1: Первый шаг — начать с конца массива и выбрать последний элемент.
Всего в массиве 9 позиций, случайным образом генерируется позиция, и элемент этой позиции заменяется последним элементом.
Шаг 2: На предыдущем шаге мы случайным образом переставили элементы в конце массива. Затем обработайте предпоследний элемент массива. В 8 позициях, кроме позиции последнего размещенного элемента, Случайным образом сгенерируйте позицию, которая меняет местами элемент с предпоследним элементом.
Шаг 3: Поняв первые два шага, следующий шаг — действовать последовательно, так просто.
Затем мы используем код для реализации Фишера-Йейтса.
function shuffle(arr) {
let m = arr.length;
while (m > 1){
let index = Math.floor(Math.random() * m--);
[arr[m] , arr[index]] = [arr[index] , arr[m]]
}
return arr;
}
Затем мы используем предыдущую функцию проверки test_shuffle
test_shuffle(shuffle);
Результат выглядит следующим образом:
Из таблицы видно, что количество вхождений каждого элемента в каждую позицию не сильно отличается, что говорит о том, что данный метод удовлетворяет требованиям случайности.
Более того, алгоритм Фишера-Йейтса может случайным образом перетасовывать порядок массива всего за один обход, и производительность его чрезвычайно высока~~
На данный момент мы нашли лучший способ перетасовать массив: Fisher–Yates~
Ссылаться на
Рекомендуемая серия статей
- Анализ и реализация одностраничной маршрутизации «переднего плана»
- «Front-end Advanced» полностью понимает каррирование функций.
- Память кучи памяти стека "Front-end advanced" в JS
- «Расширенное переднее» управление памятью в JS
напиши в конце
- Если в статье есть ошибки, исправьте их в комментариях, если статья вам поможет, добро пожаловать
点赞а также关注 - Эта статья была впервые опубликована одновременно сgithub, доступны наgithubНайдите больше отличных статей в
Watch&Star ★ - Для последующих статей см.:строить планы
Добро пожаловать в публичный аккаунт WeChat
【前端小黑屋】, 1–3 высококачественные высококачественные статьи публикуются каждую неделю, чтобы помочь вам в продвижении вперед.