Простейший код для пересечения массива в JavaScript
Какой самый простой, свободный от библиотек код для реализации пересечений массивов в javascript? Я хочу написать
intersection([1,2,3], [2,3,4,5])
и получить
[2, 3]
53 ответа
Используйте комбинацию Array.prototype.filter а также Array.prototype.indexOf:
array1.filter(value => -1 !== array2.indexOf(value));
Деструктивный кажется самым простым, особенно если мы можем предположить, что вход отсортирован:
/* destructively finds the intersection of
* two arrays in a simple fashion.
*
* PARAMS
* a - first array, must already be sorted
* b - second array, must already be sorted
*
* NOTES
* State of input arrays is undefined when
* the function returns. They should be
* (prolly) be dumped.
*
* Should have O(n) operations, where n is
* 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 /* they're equal */
{
result.push(a.shift());
b.shift();
}
}
return result;
}
Неразрушающий должен быть более сложным, так как мы должны отслеживать показатели:
/* finds the intersection of
* two arrays in a simple fashion.
*
* PARAMS
* a - first array, must already be sorted
* b - second array, must already be sorted
*
* NOTES
*
* Should have O(n) operations, where n is
* 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 /* they're equal */
{
result.push(a[ai]);
ai++;
bi++;
}
}
return result;
}
Если ваша среда поддерживает ECMAScript 6 Set, один простой и предположительно эффективный (см. Ссылку на спецификацию) способ:
function intersect(a, b) {
var setA = new Set(a);
var setB = new Set(b);
var intersection = new Set([...setA].filter(x => setB.has(x)));
return Array.from(intersection);
}
Короче, но менее читабельно (также без создания дополнительного пересечения Set):
function intersect(a, b) {
return [...new Set(a)].filter(x => new Set(b).has(x));
}
Избегать нового Set от b каждый раз:
function intersect(a, b) {
var setB = new Set(b);
return [...new Set(a)].filter(x => setB.has(x));
}
Обратите внимание, что при использовании наборов вы получите только различные значения, таким образом new Set[1,2,3,3].size оценивает 3,
Использование Underscore.js или lodash.js
_.intersection( [0,345,324] , [1,0,324] ) // gives [0,324]
// Return elements of array a that are also in b in linear time:
function intersect(a, b) {
return a.filter(Set.prototype.has, new Set(b));
}
// Example:
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:
Операций в секунду на больших массивах (10000 элементов):
filter + has (this) 523 (this answer) 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 (this answer) filter + has (arrow function) 35,588
Мой вклад в терминах 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>");Самый простой, быстрый O(n) и самый короткий путь:
У @nbarbosa почти такой же ответ, но он привел оба массива кSetа потом обратно вarray. Нет необходимости в каком-либо дополнительном литье.
Как насчет использования ассоциативных массивов?
function intersect(a, b) {
var d1 = {};
var d2 = {};
var results = [];
for (var i = 0; i < a.length; i++) {
d1[a[i]] = true;
}
for (var j = 0; j < b.length; j++) {
d2[b[j]] = true;
}
for (var k in d1) {
if (d2[k])
results.push(k);
}
return results;
}
редактировать:
// new version
function intersect(a, b) {
var d = {};
var results = [];
for (var i = 0; i < b.length; i++) {
d[b[i]] = true;
}
for (var j = 0; j < a.length; j++) {
if (d[a[j]])
results.push(a[j]);
}
return results;
}
Если вам нужно, чтобы он обрабатывал пересекающиеся множественные массивы:
const intersect = (a, b, ...rest) => {
if (rest.length === 0) return [...new Set(a)].filter(x => new Set(b).has(x));
return intersect(a, intersect(b, ...rest));
};
console.log(intersect([1,2,3,4,5], [1,2], [1, 2, 3,4,5], [2, 10, 1])) // [1,2]Производительность реализации @atk для отсортированных массивов примитивов можно улучшить, используя.pop, а не.shift.
function intersect(array1, array2) {
var result = [];
// Don't destroy the original arrays
var a = array1.slice(0);
var b = array2.slice(0);
var aLast = a.length - 1;
var bLast = b.length - 1;
while (aLast >= 0 && bLast >= 0) {
if (a[aLast] > b[bLast] ) {
a.pop();
aLast--;
} else if (a[aLast] < b[bLast] ){
b.pop();
bLast--;
} else /* they're equal */ {
result.push(a.pop());
b.pop();
aLast--;
bLast--;
}
}
return result;
}
Я создал тест, используя jsPerf: http://bit.ly/P9FrZK. Это примерно в три раза быстрее.pop.
- Сортировать
- проверять по одному из индекса 0, создавать новый массив из этого.
Как-то так, хотя не проверено хорошо, хотя.
function intersection(x,y){
x.sort();y.sort();
var i=j=0;ret=[];
while(i<x.length && j<y.length){
if(x[i]<y[j])i++;
else if(y[j]<x[i])j++;
else {
ret.push(x[i]);
i++,j++;
}
}
return ret;
}
alert(intersection([1,2,3], [2,3,4,5]));
PS: алгоритм предназначен только для чисел и нормальных строк, пересечение массивов произвольных объектов может не работать.
Используя jQuery:
var a = [1,2,3];
var b = [2,3,4,5];
var c = $(b).not($(b).not(a));
alert(c);
Небольшая настройка здесь (решение filter/indexOf), а именно создание индекса значений в одном из массивов с использованием объекта JavaScript, уменьшит его с O(N*M) до "вероятно" линейного времени. источник1 источник2
function intersect(a, b) {
var aa = {};
a.forEach(function(v) { aa[v]=1; });
return b.filter(function(v) { return v in aa; });
}
Это не самое простое решение (это больше кода, чем filter + indexOf), и при этом оно не является самым быстрым (вероятно, медленнее на постоянный коэффициент, чем intersect_safe ()), но кажется довольно хорошим балансом. Он очень прост и обеспечивает хорошую производительность и не требует предварительно отсортированных входных данных.
Для массивов, содержащих только строки или числа, вы можете сделать что-то с сортировкой, как в некоторых других ответах. Для общего случая массивов произвольных объектов, я не думаю, что вы можете избежать долгого пути. Следующее даст вам пересечение любого количества массивов, предоставленных в качестве параметров для arrayIntersection:
var arrayContains = Array.prototype.indexOf ?
function(arr, val) {
return arr.indexOf(val) > -1;
} :
function(arr, val) {
var i = arr.length;
while (i--) {
if (arr[i] === val) {
return true;
}
}
return false;
};
function arrayIntersection() {
var val, arrayCount, firstArray, i, j, intersection = [], missing;
var arrays = Array.prototype.slice.call(arguments); // Convert arguments into a real array
// Search for common values
firstArray = arrays.pop();
if (firstArray) {
j = firstArray.length;
arrayCount = arrays.length;
while (j--) {
val = firstArray[j];
missing = false;
// Check val is present in each remaining array
i = arrayCount;
while (!missing && i--) {
if ( !arrayContains(arrays[i], val) ) {
missing = true;
}
}
if (!missing) {
intersection.push(val);
}
}
}
return intersection;
}
arrayIntersection( [1, 2, 3, "a"], [1, "a", 2], ["a", 1] ); // Gives [1, "a"];
Это довольно коротко, используя ES2015 и Sets. Принимает подобные массиву значения, такие как String, и удаляет дубликаты.
let intersection = function(a, b) {
a = new Set(a), b = new Set(b);
return [...a].filter(v => b.has(v));
};
console.log(intersection([1,2,1,2,3], [2,3,5,4,5,3]));
console.log(intersection('ccaabbab', 'addb').join(''));Другой индексный подход, способный обрабатывать любое количество массивов одновременно:
// Calculate intersection of multiple array or object values.
function intersect (arrList) {
var arrLength = Object.keys(arrList).length;
// (Also accepts regular objects as input)
var index = {};
for (var i in arrList) {
for (var j in arrList[i]) {
var v = arrList[i][j];
if (index[v] === undefined) index[v] = 0;
index[v]++;
};
};
var retv = [];
for (var i in index) {
if (index[i] == arrLength) retv.push(i);
};
return retv;
};
Он работает только для значений, которые могут быть оценены как строки, и вы должны передать их как массив, например:
intersect ([arr1, arr2, arr3...]);
... но он прозрачно принимает объекты как параметр или как любой из элементов, которые должны быть пересечены (всегда возвращает массив общих значений). Примеры:
intersect ({foo: [1, 2, 3, 4], bar: {a: 2, j:4}}); // [2, 4]
intersect ([{x: "hello", y: "world"}, ["hello", "user"]]); // ["hello"]
РЕДАКТИРОВАТЬ: я только заметил, что это, в некотором смысле, немного глючит.
То есть: я кодировал его, думая, что входные массивы не могут содержать повторения (как в приведенном примере нет).
Но если входные массивы содержат повторения, это приведет к неверным результатам. Пример (используя реализацию ниже):
intersect ([[1, 3, 4, 6, 3], [1, 8, 99]]);
// Expected: [ '1' ]
// Actual: [ '1', '3' ]
К счастью, это легко исправить, просто добавив индексирование второго уровня. То есть:
Изменить:
if (index[v] === undefined) index[v] = 0;
index[v]++;
от:
if (index[v] === undefined) index[v] = {};
index[v][i] = true; // Mark as present in i input.
...а также:
if (index[i] == arrLength) retv.push(i);
от:
if (Object.keys(index[i]).length == arrLength) retv.push(i);
Полный пример:
// Calculate intersection of multiple array or object values.
function intersect (arrList) {
var arrLength = Object.keys(arrList).length;
// (Also accepts regular objects as input)
var index = {};
for (var i in arrList) {
for (var j in arrList[i]) {
var v = arrList[i][j];
if (index[v] === undefined) index[v] = {};
index[v][i] = true; // Mark as present in i input.
};
};
var retv = [];
for (var i in index) {
if (Object.keys(index[i]).length == arrLength) retv.push(i);
};
return retv;
};
intersect ([[1, 3, 4, 6, 3], [1, 8, 99]]); // [ '1' ]
function intersection(A,B){
var result = new Array();
for (i=0; i<A.length; i++) {
for (j=0; j<B.length; j++) {
if (A[i] == B[j] && $.inArray(A[i],result) == -1) {
result.push(A[i]);
}
}
}
return result;
}
С некоторыми ограничениями на ваши данные, вы можете сделать это за линейное время!
Для натуральных чисел: используйте массив, отображающий значения в логическое значение "видел / не видел".
function intersectIntegers(array1,array2) {
var seen=[],
result=[];
for (var i = 0; i < array1.length; i++) {
seen[array1[i]] = true;
}
for (var i = 0; i < array2.length; i++) {
if ( seen[array2[i]])
result.push(array2[i]);
}
return result;
}
Для объектов существует аналогичная техника: возьмите фиктивный ключ, установите его в "true" для каждого элемента в массиве array1, затем найдите этот ключ в элементах array2. Вымойтесь, когда закончите.
function intersectObjects(array1,array2) {
var result=[];
var key="tmpKey_intersect"
for (var i = 0; i < array1.length; i++) {
array1[i][key] = true;
}
for (var i = 0; i < array2.length; i++) {
if (array2[i][key])
result.push(array2[i]);
}
for (var i = 0; i < array1.length; i++) {
delete array1[i][key];
}
return result;
}
Конечно, вы должны быть уверены, что ключ не появлялся раньше, иначе вы уничтожите свои данные...
"indexOf" для IE 9.0, Chrome, Firefox, Opera,
function intersection(a,b){
var rs = [], x = a.length;
while (x--) b.indexOf(a[x])!=-1 && rs.push(a[x]);
return rs.sort();
}
intersection([1,2,3], [2,3,4,5]);
//Result: [2,3]
Я написал функцию пересечения, которая может даже обнаружить пересечение массива объектов на основе конкретного свойства этих объектов.
Например,
if arr1 = [{id: 10}, {id: 20}]
and arr2 = [{id: 20}, {id: 25}]
и мы хотим пересечение на основе id Свойство, то на выходе должно быть:
[{id: 20}]
Также, функция для того же самого (примечание: код ES6):
const intersect = (arr1, arr2, accessors = [v => v, v => v]) => {
const [fn1, fn2] = accessors;
const set = new Set(arr2.map(v => fn2(v)));
return arr1.filter(value => set.has(fn1(value)));
};
и вы можете вызвать функцию как:
intersect(arr1, arr2, [elem => elem.id, elem => elem.id])
Также обратите внимание: эта функция находит пересечение, учитывая, что первый массив является первичным массивом, и, таким образом, результатом пересечения будет результат первичного массива.
Для простоты:
// Usage
const intersection = allLists
.reduce(intersect, allValues)
.reduce(removeDuplicates, []);
// Implementation
const intersect = (intersection, list) =>
intersection.filter(item =>
list.some(x => x === item));
const removeDuplicates = (uniques, item) =>
uniques.includes(item) ? uniques : uniques.concat(item);
// Example Data
const somePeople = [bob, doug, jill];
const otherPeople = [sarah, bob, jill];
const morePeople = [jack, jill];
const allPeople = [...somePeople, ...otherPeople, ...morePeople];
const allGroups = [somePeople, otherPeople, morePeople];
// Example Usage
const intersection = allGroups
.reduce(intersect, allPeople)
.reduce(removeDuplicates, []);
intersection; // [jill]
Выгоды:
- грязь просто
- ориентированные на данные
- работает для произвольного числа списков
- работает для произвольной длины списков
- работает для произвольных типов значений
- работает для произвольного порядка сортировки
- сохраняет форму (порядок первого появления в любом массиве)
- выходит рано, где это возможно
- память безопасна, если не вмешиваться в прототипы функций / массивов
Недостатки:
- более высокое использование памяти
- более высокая загрузка процессора
- требует понимания уменьшения
- требует понимания потока данных
Вы не захотите использовать это для работы с трехмерным движком или ядром, но если у вас есть проблемы с его запуском в приложении, основанном на событиях, у вашего дизайна большие проблемы.
Я внесу свой вклад в то, что получилось лучше для меня:
if (!Array.prototype.intersect){
Array.prototype.intersect = function (arr1) {
var r = [], o = {}, l = this.length, i, v;
for (i = 0; i < l; i++) {
o[this[i]] = true;
}
l = arr1.length;
for (i = 0; i < l; i++) {
v = arr1[i];
if (v in o) {
r.push(v);
}
}
return r;
};
}
Функциональный подход с ES2015
Функциональный подход должен предусматривать использование только чистых функций без побочных эффектов, каждая из которых связана только с одной работой.
Эти ограничения улучшают компоновку и возможность повторного использования задействованных функций.
// small, reusable auxiliary functions
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));
const apply = f => x => f(x);
// intersection
const intersect = xs => ys => {
const zs = createSet(ys);
return filter(x => zs.has(x)
? true
: false
) (xs);
};
// mock data
const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];
// run it
console.log( intersect(xs) (ys) );Обратите внимание, что родной Set тип используется, который имеет выгодную производительность поиска.
Избегайте дубликатов
Очевидно, многократно встречающиеся предметы из первых Array сохраняются, а второй Array дедублируется Это может быть или не быть желаемым поведением. Если вам нужен уникальный результат, просто подайте заявку dedupe к первому аргументу:
// auxiliary functions
const apply = f => x => f(x);
const comp = f => g => x => f(g(x));
const afrom = apply(Array.from);
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));
// intersection
const intersect = xs => ys => {
const zs = createSet(ys);
return filter(x => zs.has(x)
? true
: false
) (xs);
};
// de-duplication
const dedupe = comp(afrom) (createSet);
// mock data
const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];
// unique result
console.log( intersect(dedupe(xs)) (ys) ); Вычислить пересечение любого числа Array s
Если вы хотите вычислить пересечение произвольного числа Array просто сочинять intersect с foldl, Вот удобная функция:
// auxiliary functions
const apply = f => x => f(x);
const uncurry = f => (x, y) => f(x) (y);
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));
const foldl = f => acc => xs => xs.reduce(uncurry(f), acc);
// intersection
const intersect = xs => ys => {
const zs = createSet(ys);
return filter(x => zs.has(x)
? true
: false
) (xs);
};
// intersection of an arbitrarily number of Arrays
const intersectn = (head, ...tail) => foldl(intersect) (head) (tail);
// mock data
const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];
const zs = [0,1,2,3,4,5,6];
// run
console.log( intersectn(xs, ys, zs) );Эта функция позволяет избежать проблемы N ^ 2 , используя преимущества словарей. Проходит через каждый массив только один раз и третий, более короткий цикл, чтобы вернуть окончательный результат. Он также поддерживает числа, строки и объекты .
function array_intersect(array1, array2)
{
var mergedElems = {},
result = [];
// Returns a unique reference string for the type and value of the element
function generateStrKey(elem) {
var typeOfElem = typeof elem;
if (typeOfElem === 'object') {
typeOfElem += Object.prototype.toString.call(elem);
}
return [typeOfElem, elem.toString(), JSON.stringify(elem)].join('__');
}
array1.forEach(function(elem) {
var key = generateStrKey(elem);
if (!(key in mergedElems)) {
mergedElems[key] = {elem: elem, inArray2: false};
}
});
array2.forEach(function(elem) {
var key = generateStrKey(elem);
if (key in mergedElems) {
mergedElems[key].inArray2 = true;
}
});
Object.values(mergedElems).forEach(function(elem) {
if (elem.inArray2) {
result.push(elem.elem);
}
});
return result;
}
Если есть особый случай, который нельзя решить, просто изменив
В этом варианте есть некоторые улучшения производительности . Избегайте циклов, если какой-либо массив пуст. Он также начинается с обхода сначала более короткого массива, поэтому, если он находит все значения первого массива во втором массиве, выходит из цикла.
function array_intersect(array1, array2)
{
var mergedElems = {},
result = [],
firstArray, secondArray,
firstN = 0,
secondN = 0;
function generateStrKey(elem) {
var typeOfElem = typeof elem;
if (typeOfElem === 'object') {
typeOfElem += Object.prototype.toString.call(elem);
}
return [typeOfElem, elem.toString(), JSON.stringify(elem)].join('__');
}
// Executes the loops only if both arrays have values
if (array1.length && array2.length)
{
// Begins with the shortest array to optimize the algorithm
if (array1.length < array2.length) {
firstArray = array1;
secondArray = array2;
} else {
firstArray = array2;
secondArray = array1;
}
firstArray.forEach(function(elem) {
var key = generateStrKey(elem);
if (!(key in mergedElems)) {
mergedElems[key] = {elem: elem, inArray2: false};
// Increases the counter of unique values in the first array
firstN++;
}
});
secondArray.some(function(elem) {
var key = generateStrKey(elem);
if (key in mergedElems) {
if (!mergedElems[key].inArray2) {
mergedElems[key].inArray2 = true;
// Increases the counter of matches
secondN++;
// If all elements of first array have coincidence, then exits the loop
return (secondN === firstN);
}
}
});
Object.values(mergedElems).forEach(function(elem) {
if (elem.inArray2) {
result.push(elem.elem);
}
});
}
return result;
}
Это, вероятно, самый простой из всех, кроме list1.filter(n => list2.include (n))
var list1 = ['bread', 'ice cream', 'cereals', 'strawberry', 'chocolate']
var list2 = ['bread', 'cherry', 'ice cream', 'oats']
function check_common(list1, list2){
list3 = []
for (let i=0; i<list1.length; i++){
for (let j=0; j<list2.length; j++){
if (list1[i] === list2[j]){
list3.push(list1[i]);
}
}
}
return list3
}
check_common(list1, list2) // ["bread", "ice cream"]'use strict'
// Example 1
function intersection(a1, a2) {
return a1.filter(x => a2.indexOf(x) > -1)
}
// Example 2 (prototype function)
Array.prototype.intersection = function(arr) {
return this.filter(x => arr.indexOf(x) > -1)
}
const a1 = [1, 2, 3]
const a2 = [2, 3, 4, 5]
console.log(intersection(a1, a2))
console.log(a1.intersection(a2)).reduce построить карту и .filter найти пересечение. delete в пределах .filter позволяет нам обрабатывать второй массив как уникальный набор.
function intersection (a, b) {
var seen = a.reduce(function (h, k) {
h[k] = true;
return h;
}, {});
return b.filter(function (k) {
var exists = seen[k];
delete seen[k];
return exists;
});
}
Я нахожу этот подход довольно легко рассуждать. Работает в постоянном времени.
function getIntersection(arr1, arr2){
var result = [];
arr1.forEach(function(elem){
arr2.forEach(function(elem2){
if(elem === elem2){
result.push(elem);
}
});
});
return result;
}
getIntersection([1,2,3], [2,3,4,5]); // [ 2, 3 ]
var listA = [1,2,3,4,5,6,7];
var listB = [2,4,6,8];
var result = listA.filter(itemA=> {
return listB.some(itemB => itemB === itemA);
});
Это предлагаемый стандарт: с текущим предложением этапа 2 https://github.com/tc39/proposal-set-methods вы можете использовать
mySet.intersection(mySet2);
До тех пор вы можете использовать Immutable.jsSet, что вдохновило это предложение
Immutable.Set(mySet).intersect(mySet2)