Девятнадцатая часть серии тем по JavaScript, объясняющая беспорядок массива и фокусирующаяся на том, почему Math.random() не может быть действительно беспорядочным?
не работает
Не по порядку означает перетасовку массива.
Ну нет, просто посмотрите на код.
Math.random
Обычный способ написать это — использовать Math.random():
var values = [1, 2, 3, 4, 5];
values.sort(function(){
return Math.random() - 0.5;
});
console.log(values)Math.random() - 0.5Случайным образом получить положительное число, отрицательное число или 0. Если это положительное число, оно будет отсортировано в порядке убывания. Если это отрицательное число, оно будет отсортировано в порядке возрастания. Если это 0, оно останется неизменным .
Казалось бы, хороший план, на самом деле эффект не вызывает нареканий. Если вы мне не верите, давайте напишем демо для проверки:
var times = [0, 0, 0, 0, 0];
for (var i = 0; i < 100000; i++) {
let arr = [1, 2, 3, 4, 5];
arr.sort(() => Math.random() - 0.5);
times[arr[4]-1]++;
}
console.log(times)Принцип теста таков:[1, 2, 3, 4, 5]100 000 раз не по порядку, подсчитайте, сколько раз последний элемент массива не по порядку равен 1, 2, 3, 4 и 5.
Случайный результат:
[30636, 30906, 20456, 11743, 6259]Результат показывает, что из 100 000 раз 30 636 раз последний элемент массива не соответствует порядку 1, 30 906 раз — 2 и так далее.
Мы обнаружим, что количество раз, когда последний элемент равен 5, намного меньше, чем количество раз, когда он равен 1, поэтому эта схема проблематична.
Но я, очевидно, чувствую, что этот метод неплох, не так ли? Когда я впервые увидел это, я был немного удивлен, почему существует проблема?
Да! Мне любопытно!
Сортировка вставками
Если вы хотите исследовать проблему, вы должны понимать принцип работы функции сортировки, однако ECMAScript указывает только эффект, а не метод реализации, поэтому методы реализации в разных браузерах различаются.
Чтобы решить эту проблему, возьмем в качестве примера v8.Когда v8 обрабатывает метод сортировки, когда длина целевого массива меньше 10, используется сортировка вставками, в противном случае используется смешанная сортировка быстрой сортировки и сортировки вставками. использовал.
Итак, давайте взглянем на исходный код v8, потому что он написан на JavaScript, его может понять каждый.
Адрес источника:GitHub.com/V8/V8/blob/…
Чтобы упростить пространство, мы[1, 2, 3]Этот массив анализируется, длина массива равна 3, и в это время используется сортировка вставками.
Вставка отсортированного источника:
function InsertionSort(a, from, to) {
for (var i = from + 1; i < to; i++) {
var element = a[i];
for (var j = i - 1; j >= from; j--) {
var tmp = a[j];
var order = comparefn(tmp, element);
if (order > 0) {
a[j + 1] = tmp;
} else {
break;
}
}
a[j + 1] = element;
}
};Принцип состоит в том, чтобы рассматривать первый элемент как упорядоченную последовательность, проходить массив и вставлять последующие элементы в построенную упорядоченную последовательность по очереди.
Возьмем простую схему:
подробный анализ
Разобравшись с принципом сортировки вставками, давайте проанализируем результат разупорядочения массива [1, 2, 3].
Демонстрационный код:
var values = [1, 2, 3];
values.sort(function(){
return Math.random() - 0.5;
});Обратите внимание, что в настоящее время нижняя часть функции сортировки реализована с использованием сортировки вставками, функция InsertionSort от значения 0 до значения 3.
Начнем поэтапно анализировать процесс выхода из строя:
Поскольку сортировка вставками обрабатывает первый элемент как упорядоченный, внешний цикл массива начинается сi = 1В начале значение a[i] равно 2. В это время внутренний слой выполняет цикл и сравниваетcompare(1, 2),потому чтоMath.random() - 0.5Результат 50% имеет вероятность меньше 0, а 50% вероятность больше 0, поэтому есть вероятность 50%, что массив станет [2, 1, 3], 50% результатов останутся без изменений , а массив по-прежнему [1, 2, 3].
Предполагая, что это все еще [1, 2, 3], мы выполняем еще один анализ, а затем проходим,i = 2, значение a[i] равно 3. В это время внутренний слой выполняет цикл и сравниваетcompare(2, 3):
Существует 50% вероятность того, что массив не изменится, тем не менее[1, 2, 3], то обход заканчивается.
Существует 50% вероятность того, что он станет [1, 3, 2].Поскольку правильная позиция 3 не найдена, она все равно будет пройдена, поэтому при этой 50% вероятности будет сделано другое сравнение,compare(1, 3), есть 50% вероятность того, что он не изменится, массив равен [1, 3, 2], в это время обход окончен, есть 50% вероятность того, что вероятность изменится, и массив станет [3 , 1, 2].
Подводя итог, в [1, 2, 3] существует 50% вероятность того, что он станет [1, 2, 3], 25% вероятность того, что он станет [1, 3, 2] и 25% вероятность того, что он станет [1, 2, 3]. % вероятности станет [3, 1, 2].
Другой случай [2, 1, 3] аналогичен анализу, и мы сводим окончательные результаты в таблицу:
| множество | i = 1 | i = 2 | Всего |
|---|---|---|---|
| [1, 2, 3] | 50% [1, 2, 3] | 50% [1, 2, 3] | 25% [1, 2, 3] |
| 25% [1, 3, 2] | 12.5% [1, 3, 2] | ||
| 25% [3, 1, 2] | 12.5% [3, 1, 2] | ||
| 50% [2, 1, 3] | 50% [2, 1, 3] | 25% [2, 1, 3] | |
| 25% [2, 3, 1] | 12.5% [2, 3, 1] | ||
| 25% [3, 2, 1] | 12.5% [3, 2, 1] |
Чтобы убедиться, что этот расчет точен, давайте напишем демо для его проверки:
var times = 100000;
var res = {};
for (var i = 0; i < times; i++) {
var arr = [1, 2, 3];
arr.sort(() => Math.random() - 0.5);
var key = JSON.stringify(arr);
res[key] ? res[key]++ : res[key] = 1;
}
// 为了方便展示，转换成百分比
for (var key in res) {
res[key] = res[key] / times * 100 + '%'
}
console.log(res)Вот случайный результат:
Мы обнаружим, что после беспорядка3Тем не менее в исходном положении (то есть [1, 2, 3] и [2, 1, 3]) вероятность этого составляет 50%.
Так в чем же первопричина? Фактически, в алгоритме сортировки вставками, когда сортируемый элемент сравнивается с упорядоченным элементом, после определения позиции он не будет сравниваться с упорядоченным элементом перед позицией, поэтому беспорядок является неполным.
Так как же добиться истинного выхода из строя? И это про классический алгоритм Фишера-Йейтса.
Фишер-Йейтс
Почему он называется Фишер-Йейтс? Потому что этот алгоритм был впервые предложен Рональдом Фишером и Фрэнком Йейтсом.
Без лишних слов давайте посмотрим непосредственно на реализацию JavaScript:
function shuffle(a) {
var j, x, i;
for (i = a.length; i; i--) {
j = Math.floor(Math.random() * i);
x = a[i - 1];
a[i - 1] = a[j];
a[j] = x;
}
return a;
}Принцип очень простой, это пройтись по элементам массива, а затем поменять местами текущий элемент с элементом в случайной позиции в будущем.Также из кода видно, что разброс будет более тщательный.
При использовании ES6 код также можно упростить до:
function shuffle(a) {
for (let i = a.length; i; i--) {
let j = Math.floor(Math.random() * i);
[a[i - 1], a[j]] = [a[j], a[i - 1]];
}
return a;
}Или напишите демо для проверки:
var times = 100000;
var res = {};
for (var i = 0; i < times; i++) {
var arr = shuffle([1, 2, 3]);
var key = JSON.stringify(arr);
res[key] ? res[key]++ : res[key] = 1;
}
// 为了方便展示，转换成百分比
for (var key in res) {
res[key] = res[key] / times * 100 + '%'
}
console.log(res)Вот случайный результат:
Действительно добиться эффекта не по порядку!
Тематическая серия
Адрес каталога серии тем JavaScript:GitHub.com/ в настоящее время имеет бриз….
Ожидается, что в серии тем JavaScript будет написано около 20 статей, в основном для изучения реализации некоторых функциональных точек в ежедневной разработке, таких как защита от сотрясений, регулирование, дедупликация, оценка типов, копирование, максимальное значение, плоское, карри, рекурсия, беспорядок. , сортировка и т. д., характеризуется поиском (чао), исследованием (кси), реализацией подчеркивания и jQuery.
Если есть какие-либо ошибки или неточности, пожалуйста, поправьте меня, большое спасибо. Если вам нравится или у вас есть вдохновение, добро пожаловать в звезду, что также является поощрением для автора.