Перетасовка массивов в JavaScript
Одной из многих функций, которые предоставляет JavaScript, является возможность легко работать с массивами. Массив - это особый тип объекта, который используется для хранения нескольких значений в одной переменной, и в случае JavaScript эти значения не обязательно должны быть одного типа. Время от времени вы можете столкнуться с необходимостью рандомизировать порядок элементов в массиве, иначе называемый перетасовкой.
В этой статье мы познакомим вас с различными методами перетасовки массивов в JavaScript и приведем примеры реализации.
Массивы в JavaScript
Прежде чем мы углубимся в методы перестановки, давайте сначала разберемся, что такое массив в JavaScript. Массив - это структура данных, которая может хранить несколько значений в одной переменной. Каждое значение (также известное как элемент) в массиве имеет числовую позицию, известную как его индекс, который начинается с 0.
Вот пример простого массива JavaScript:
let fruits = ['Apple', 'Banana', 'Cherry', 'Date', 'Elderberry'];
console.log(fruits[0]); // Output: 'Apple'В этом массиве 'Apple' имеет индекс 0, 'Banana' - индекс 1 и так далее. Вы можете получить доступ к элементам массива, обратившись к индексному номеру.
Примечание: В JavaScript массивы являются динамическими, что означает, что они могут изменять размер во время выполнения, и они могут содержать элементы любого типа - числа, строки, объекты или даже другие массивы.
Массивы в JavaScript поставляются с набором встроенных методов, которые позволяют вам манипулировать массивом и его элементами. Некоторые из этих методов включают push() для добавления элементов, pop() для удаления элементов, sort() для сортировки элементов и так далее.
Однако встроенного метода для перестановки элементов массива не существует. Именно здесь пригодятся методы, которые мы обсудим в следующих разделах.
Зачем перемешивать массив?
Перетасовка массива - это операция, которая случайным образом переставляет элементы в массиве. Это особенно полезно в самых разных сценариях.
Например, если вы создаете карточную игру, вам нужно будет перетасовать колоду карт, хранящуюся в массиве, перед началом игры, чтобы обеспечить честность. В машинном обучении принято перемешивать входные данные перед разделением их на обучающие и тестовые наборы, чтобы гарантировать, что на модель не повлияет какой-либо порядок, присутствующий в данных.
Перетасовку также можно использовать для генерации случайной выборки из большего набора данных или для создания более визуально привлекательного отображения элементов на веб-странице. В JavaScript нет встроенной функции для перетасовки массива, но есть несколько хорошо известных алгоритмов, которые могут быть реализованы довольно легко, и мы рассмотрим их.
Перетасовка Фишера-Йейтса (Кнута)
Перетасовка Фишера-Йейтса, также известная как перетасовка Кнута, - это простой и эффективный метод перетасовки массива. Он работает путем перебора массива от последнего элемента к первому, заменяя каждый элемент элементом со случайным индексом, меньшим или равным его текущему индексу.
Вот JavaScript-реализация перетасовки Фишера-Йейтса:
function fisherYatesShuffle(array) {
let currentIndex = array.length;
while (currentIndex !== 0) {
// Pick a remaining element
let randomIndex = Math.floor(Math.random() * currentIndex);
currentIndex--;
// And swap it with the current element
let temporaryValue = array[currentIndex];
array[currentIndex] = array[randomIndex];
array[randomIndex] = temporaryValue;
}
return array;
}
let arr = [1, 2, 3, 4, 5];
console.log(fisherYatesShuffle(arr)); // [ 3, 1, 5, 4, 2 ]Когда вы запустите этот код, он напечатает перетасованную версию массива [1, 2, 3, 4, 5]. Результат будет отличаться каждый раз, когда вы запускаете функцию, как и должно быть при хорошем алгоритме перемешивания.
Примечание. Перетасовка Фишера-Йейтса — это алгоритм на месте, что означает, что он перемешивает исходный массив без создания нового. Это делает его очень экономичным методом перетасовки массива.
Алгоритм фишера-йетса js имеет временную сложность O(n), что делает ее очень эффективным методом перетасовки больших массивов. Это связано с тем, что ему нужно выполнить только один проход по массиву, заменив каждый элемент случайно выбранным элементом, который еще не был перетасован.
Перетасовка Дурштенфельда
Тасовка Дурштенфельда - это оптимизированная для компьютера версия тасовки Фишера-Йейтса, разработанная Ричардом Дурштенфельдом в 1964 году. Этот алгоритм разработан, чтобы быть более эффективным, и работает путем выбора одного случайного элемента для каждого исходного элемента массива, а затем исключения его из следующего розыгрыша.
Давайте посмотрим, как мы можем реализовать это в JavaScript:
function durstenfeldShuffle(array) {
for (let i = array.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[array[i], array[j]] = [array[j], array[i]];
}
return array;
}
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log(durstenfeldShuffle(arr));Когда вы запустите этот скрипт, вы увидите, что элементы массива перемешиваются случайным образом. Опять же, каждое выполнение, скорее всего, приведет к другому результату.
Примечание: Перетасовка Дурштенфельда считается более эффективной, чем перетасовка Фишера-Йейтса, поскольку она позволяет избежать необходимости вставлять выбранные элементы в новый массив, что может быть дорогостоящим с точки зрения вычислений.
Преобразование Шварца
Преобразование Шварца, названное в честь Рэндала Л. Шварца, представляет собой метод сортировки, используемый в компьютерном программировании. Это не совсем алгоритм перемешивания, но он может быть адаптирован для этой цели. Идея состоит в том, чтобы преобразовать массив таким образом, чтобы сделать сортировку более эффективной, а затем отменить преобразование.
В контексте перетасовки массива мы можем использовать преобразование Шварца, чтобы присвоить случайное число каждому элементу массива, отсортировать массив на основе этих чисел, а затем удалить числа, оставив перетасованный массив.
Приведем пример реализация на JavaScript:
function schwartzianShuffle(array) {
return array
.map((a) => [Math.random(), a]) // Assign a random number to each element
.sort((a, b) => a[0] - b[0]) // Sort by the random numbers
.map((a) => a[1]); // Remove the random numbers
}
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log(schwartzianShuffle(arr));Когда вы запустите этот скрипт, вы увидите, что элементы массива перемешиваются случайным образом. Как и в случае с предыдущими алгоритмами, каждое выполнение, скорее всего, приведет к другому результату.
Хотя преобразование Шварца - это умная техника, возможно, это не самый эффективный метод перетасовки больших массивов в JavaScript. Однако это служит для демонстрации того, как вы можете использовать другие методы для достижения желаемого результата.
Перетасовка многомерных массивов
Когда дело доходит до перетасовки многомерных массивов, процесс немного сложнее. Многомерный массив - это, по сути, просто массив массивов. Если бы мы просто применили алгоритм перетасовки к многомерному массиву, мы бы в конечном итоге перетасовали подмассивы, но не отдельные элементы внутри этих подмассивов.
Один из способов правильно перетасовать многомерный массив - это выровнять массив, перетасовать его, а затем перестроить многомерный массив. Вот как вы можете это сделать:
function shuffleMultiDimensionalArray(array) {
// Flatten the array
let flattened = [].concat(...array);
// Shuffle the flattened array
for (let i = flattened.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[flattened[i], flattened[j]] = [flattened[j], flattened[i]];
}
// Rebuild the multidimensional array
let result = [];
while(flattened.length) result.push(flattened.splice(0, array[0].length));
return result;
}
let array = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
console.log(shuffleMultiDimensionalArray(array));Это выведет перетасованный многомерный массив, например:
[[3, 1, 2], [6, 5, 4], [8, 9, 7]]Примечание: Эта функция предполагает, что все подмассивы в многомерном массиве имеют одинаковую длину. Если подмассивы имеют разную длину, эта функция не будет работать должным образом.
Использование Lodash
Если вы используете Lodash, популярную библиотеку утилит JavaScript, вы можете перетасовывать массивы с помощью функции _.shuffle(). Эта функция реализует алгоритм перемешивания Фишера-Йейтса и работает как с одиночными, так и с многомерными массивами.
Вот как вы можете перетасовать массив с помощью Lodash:
const _ = require('lodash');
let array = [1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log(_.shuffle(array));Это выведет перетасованный массив, например:
[3, 2, 9, 1, 6, 8, 7, 4, 5]И вот как вы можете перетасовать многомерный массив:
const _ = require('lodash');
let array = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
console.log(_.shuffle(_.flatten(array)));Это выведет перетасованный массив, например:
[3, 2, 1, 6, 5, 4, 9, 8, 7]Здесь функция _.flatten() используется для выравнивания многомерного массива перед его перетасовкой. Однако он не будет перестраивать многомерный массив после перетасовки. Если вам нужно сохранить многомерную структуру, вам придется перестроить ее самостоятельно.
Вопросы производительности
Когда дело доходит до перетасовки массивов в JavaScript, производительность может быть важным фактором, который следует учитывать, особенно при работе с большими массивами.
Тасовка Фишера-Йейтса (Кнута) и ее оптимизированная версия, тасовка Дурстенфельда, известны своей эффективной O(n) временной сложностью. Это означает, что время, затрачиваемое на перетасовку массива, растет линейно с увеличением размера массива, что довольно хорошо.
Преобразование Шварца, с другой стороны, не столь эффективно. Этот метод включает в себя операцию сортировки, временная сложность которой составляет O(n log n). Это делает его медленнее, чем перетасовки Фишера-Йейтса и Дурстенфельда для больших массивов.
Однако при работе с массивами меньшего размера разница в производительности между этими методами незначительна. Затем выбор метода будет зависеть от других факторов, таких как удобочитаемость и простота кода.
Примечание: Всегда учитывайте компромисс между производительностью и удобочитаемостью кода. Возможно, стоит использовать немного более медленный метод, если он облегчает понимание и поддержку вашего кода.
Использование библиотек, подобных Lodash, также может иметь последствия для производительности. Хотя эти библиотеки оптимизированы и обычно хорошо работают, они добавляют дополнительный уровень абстракции, который может замедлить работу по сравнению с нативными методами JavaScript.
Вот сравнение времени, затраченного на перетасовку массива из 1 миллиона чисел с использованием различных методов:
let arr = Array.from({length: 1000000}, (_, i) => i + 1);
console.time('Fisher-Yates Shuffle');
fisherYatesShuffle(arr);
console.timeEnd('Fisher-Yates Shuffle');
console.time('Durstenfeld Shuffle');
durstenfeldShuffle(arr);
console.timeEnd('Durstenfeld Shuffle');
console.time('Schwartzian Transform');
schwartzianShuffle(arr);
console.timeEnd('Schwartzian Transform');
console.time('Lodash Shuffle');
_.shuffle(arr);
console.timeEnd('Lodash Shuffle');$ node shuffle.js
Fisher-Yates Shuffle: 19.95ms
Durstenfeld Shuffle: 18.118ms
Schwartzian Transform: 898.175ms
Lodash Shuffle: 21.308msТочное время будет варьироваться в зависимости от вашего компьютера и текущей рабочей нагрузки, но вы должны видеть, что тасование Фишера-Йейтса и Дурстенфельда происходит значительно быстрее, чем преобразование Шварца, и немного быстрее, чем тасование Lodash.
Что касается Lodash, то это может быть связано с некоторыми накладными расходами при использовании библиотеки, подобной Lodash.
Вывод
Перетасовка массивов в JavaScript - это распространенное требование, которое может быть достигнуто несколькими способами. В то время как тасование Фишера-Йейтса (Кнута) и тасование Дурстенфельда эффективны и широко используются, другие методы, такие как преобразование Шварца или использование библиотек, таких как Lodash, могут быть более подходящими в зависимости от конкретных требований и ограничений вашего проекта.
Не забывайте учитывать влияние на производительность при выборе метода, особенно при работе с большими массивами. Однако не забывайте, что удобочитаемость и простота кода также являются важными факторами, которые следует учитывать. Лучшим решением обычно являются те, которые обеспечивают баланс между эффективностью, удобочитаемостью и простотой.
