Самый простой код для пересечения массивов на JavaScript
Заголовок: Как реализовать пересечение массивов в JavaScript без использования библиотек?
Описание проблемы: Мне нужно написать функцию для нахождения пересечения массивов в JavaScript. Я хотел бы, чтобы код был максимально простым и без использования сторонних библиотек.
Например, если я вызову:
intersection([1, 2, 3], [2, 3, 4, 5])
то ожидаю получить:
[2, 3]
Как я могу это реализовать?
5 ответ(ов)
Для нахождения пересечения двух массивов, если у вас уже есть отсортированные массивы, можно использовать два подхода: разрушительный и неразрушительный.
Разрушительный метод
Разрушительный метод является более простым и работает следующим образом:
/* Находит пересечение двух массивов разрушительно
*
* ПАРАМЕТРЫ
* a - первый массив, должен быть отсортирован
* b - второй массив, должен быть отсортирован
*
* ЗАМЕТКИ
* Состояние входных массивов не определено после
* выполнения функции. Их следует (вероятно) удалить.
*
* Должен иметь O(n) операций, где n = MIN(a.length, b.length)
*/
function intersection_destructive(a, b) {
var result = [];
while (a.length > 0 && b.length > 0) {
if (a[0] < b[0]) {
a.shift();
} else if (a[0] > b[0]) {
b.shift();
} else { /* они равны */
result.push(a.shift());
b.shift();
}
}
return result;
}
В этом методе мы постоянно сравниваем первые элементы обоих массивов. Если один из элементов меньше, он удаляется из массива, а если равен — добавляется в результат.
Неразрушительный метод
Неразрушительный метод немного сложнее, поскольку нам нужно отслеживать индексы:
/* Находит пересечение двух массивов неразрушительно
*
* ПАРАМЕТРЫ
* a - первый массив, должен быть отсортирован
* b - второй массив, должен быть отсортирован
*
* ЗАМЕТКИ
*
* Должен иметь O(n) операций, где n = MIN(a.length, b.length)
*/
function intersect_safe(a, b) {
var ai = 0, bi = 0;
var result = [];
while (ai < a.length && bi < b.length) {
if (a[ai] < b[bi]) {
ai++;
} else if (a[ai] > b[bi]) {
bi++;
} else { /* они равны */
result.push(a[ai]);
ai++;
bi++;
}
}
return result;
}
В этом варианте мы используем два указателя ai
и bi
, чтобы отслеживать текущие индексы в массиве a
и b
, что позволяет нам не изменять сами массивы.
Итог
Оба метода имеют временную сложность O(n), где n — это минимальная длина одного из массивов. Выбор метода зависит от требований вашего конкретного случая — хотите ли вы сохранить исходные массивы нетронутыми или нет.
Вы можете использовать библиотеки Underscore.js или lodash.js для нахождения пересечения массивов. Ваш пример использует метод _.intersection
, который возвращает массив, содержащий все элементы, которые присутствуют в обоих массивах.
Вот как это работает:
_.intersection([0, 345, 324], [1, 0, 324]); // возвращает [0, 324]
В данном случае, метод _.intersection
принимает два массива: [0, 345, 324]
и [1, 0, 324]
, и возвращает новый массив, содержащий только те значения, которые есть в обоих исходных массивах. В результате вы получаете [0, 324]
, так как эти два элемента присутствуют в обоих массивов.
Таким образом, для нахождения пересечения массивов с помощью Underscore.js или lodash.js просто используйте метод _.intersection
.
Для нахождения элементов массива a
, которые также присутствуют в массиве b
, можно использовать следующий код, который работает за линейное время:
// Возвращает элементы массива a, которые также находятся в b за линейное время:
function intersect(a, b) {
return a.filter(Set.prototype.has, new Set(b));
}
// Пример:
console.log(intersect([1, 2, 3], [2, 3, 4, 5]));
Я рекомендую данное лаконичное решение, которое превосходит другие реализации на больших объемах данных. Если производительность на небольших входных данных важна, проверьте альтернативы ниже.
Альтернативы и сравнение производительности:
Посмотрите следующий фрагмент для альтернативных реализаций и проверьте https://jsperf.com/array-intersection-comparison для сравнений производительности.
function intersect_for(a, b) {
const result = [];
const alen = a.length;
const blen = b.length;
for (let i = 0; i < alen; ++i) {
const ai = a[i];
for (let j = 0; j < blen; ++j) {
if (ai === b[j]) {
result.push(ai);
break;
}
}
}
return result;
}
function intersect_filter_indexOf(a, b) {
return a.filter(el => b.indexOf(el) !== -1);
}
function intersect_filter_in(a, b) {
const map = b.reduce((map, el) => { map[el] = true; return map; }, {});
return a.filter(el => el in map);
}
function intersect_for_in(a, b) {
const result = [];
const map = {};
for (let i = 0, length = b.length; i < length; ++i) {
map[b[i]] = true;
}
for (let i = 0, length = a.length; i < length; ++i) {
if (a[i] in map) result.push(a[i]);
}
return result;
}
function intersect_filter_includes(a, b) {
return a.filter(el => b.includes(el));
}
function intersect_filter_has_this(a, b) {
return a.filter(Set.prototype.has, new Set(b));
}
function intersect_filter_has_arrow(a, b) {
const set = new Set(b);
return a.filter(el => set.has(el));
}
function intersect_for_has(a, b) {
const result = [];
const set = new Set(b);
for (let i = 0, length = a.length; i < length; ++i) {
if (set.has(a[i])) result.push(a[i]);
}
return result;
}
Результаты в Firefox 53:
Операций в секундах на больших массивах (10,000 элементов):
filter + has (this) 523 (данный ответ) for + has 482 for-loop + in 279 filter + in 242 for-loops 24 filter + includes 14 filter + indexOf 10
Операций в секундах на маленьких массивах (100 элементов):
for-loop + in 384,426 filter + in 192,066 for-loops 159,137 filter + includes 104,068 filter + indexOf 71,598 filter + has (this) 43,531 (данный ответ) filter + has (стрелочная функция) 35,588
Эти данные показывают, что для больших массивов использование filter
с Set
является наиболее эффективным подходом. Однако для небольших массивов цикл for
с in
может давать лучшие результаты.
Самый простой, быстрый O(n) и короткий способ:
function intersection (a, b) {
const setA = new Set(a);
return b.filter(value => setA.has(value));
}
console.log(intersection([1,2,3], [2,3,4,5]))
@nbarbosa предложил почти такое же решение, но он преобразует оба массива в Set
, а затем обратно в массив. Главная разница в том, что его код будет возвращать только уникальные элементы, в то время как результат этого кода будет содержать повторяющиеся значения из массива b
(при условии, что оба массива не заполнены уникальными значениями).
Так что используйте тот код, который соответствует вашим требованиям.
В вашем коде вы создаете метод intersect
для массива в ES6, который находит пересечение исходного массива с произвольным количеством других массивов, переданных в качестве аргументов. Давайте разберем этот код:
Array.prototype.intersect = function(...a) {
return [this, ...a].reduce((p, c) => p.filter(e => c.includes(e)));
}
var arrs = [[0, 2, 4, 6, 8], [4, 5, 6, 7], [4, 6]],
arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
document.write("<pre>" + JSON.stringify(arr.intersect(...arrs)) + "</pre>");
Объяснение кода:
Метод
intersect
:- Данный метод добавляется в прототип
Array
, что позволяет вызывать его на любом массиве. - Он принимает неопределенное количество массивов в качестве аргументов, благодаря использованию оператора распаковки
(...a)
. - Метод создает новый массив, который включает исходный массив (
this
) и переданные массивы (a
).
- Данный метод добавляется в прототип
reduce
:- С помощью метода
reduce
мы проходим по массивам, выполняя операцию фильтрации. - На первом шаге
p
(предыдущее значение) будет равен исходному массиву, аc
(текущий элемент) — первому массиву изa
. - Мы используем
filter
, чтобы оставить только те элементы изp
, которые содержатся в массивеc
.
- С помощью метода
Пример использования:
- Массив
arrs
содержит несколько массивов, с которыми мы будем находить пересечение относительно массиваarr
. - Когда мы вызываем
arr.intersect(...arrs)
, результатом будет массив, содержащий только те элементы, которые присутствуют во всех массивов.
- Массив
Таким образом, этот код позволит вам легко находить пересечение массивов в JavaScript, используя современные возможности ES6.
Как реализовать стек и очередь на JavaScript?
В чем разница между String.slice и String.substring?
Проверка соответствия строки регулярному выражению в JS
Существует ли ссылка на "последнюю" библиотеку jQuery в Google APIs?
Как создать диалог с кнопками "Ок" и "Отмена"