recorrer - El código más simple para la intersección de matrices en javascript

multiplicación de matrices javascript

Question

¿Cuál es el código más simple y sin bibliotecas para implementar intersecciones de matriz en javascript? Quiero escribir

intersection([1,2,3], [2,3,4,5])

y obten

[2, 3]

Answer 1

Un enfoque funcional con ES2015.

Un enfoque funcional debe considerar usar solo funciones puras sin efectos secundarios, cada una de las cuales solo se ocupa de un solo trabajo.

Estas restricciones mejoran la composibilidad y la reutilización de las funciones involucradas.

// 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) );

Tenga en cuenta que se utiliza el tipo de Set nativo, que tiene un rendimiento de búsqueda ventajoso.

Evitar duplicados

Obviamente, los elementos que se producen repetidamente del primer Array se conservan, mientras que el segundo Array se desduplica. Este puede ser o no ser el comportamiento deseado. Si necesita un resultado único, simplemente aplique la dedupe al primer argumento:

// 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) );

Calcula la intersección de cualquier número de Array s

Si desea calcular la intersección de un número arbitrario de Array s solo componga la intersect con foldl . Aquí hay una función de conveniencia:

// 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) );

Answer 2

1. Ordénalo
2. marque uno por uno desde el índice 0, cree una nueva matriz a partir de eso.

Algo como esto, aunque no probado bien.

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]));

PD: el algoritmo destinado únicamente a números y cadenas normales, la intersección de matrices de objetos arbitrarios puede no funcionar.

Answer 3

"indexOf" para 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]

Answer 4

¿Qué hay de usar matrices asociativas?

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;
}

editar:

// 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;
}

Answer 5

Aquí está la implementación de underscore.js :

_.intersection = function(array) {
if (array == null) return [];
var result = [];
var argsLength = arguments.length;
for (var i = 0, length = array.length; i < length; i++) {
var item = array[i];
if (_.contains(result, item)) continue;
for (var j = 1; j < argsLength; j++) {
if (!_.contains(arguments[j], item)) break;
}
if (j === argsLength) result.push(item);
}
return result;
};

Fuente: http://underscorejs.org/docs/underscore.html#section-62

Answer 6

Con algunas restricciones en tus datos, puedes hacerlo en tiempo lineal .

Para enteros positivos : use una matriz que asigne los valores a un valor booleano "visto / no visto".

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;
}

Existe una técnica similar para los objetos : tomar una clave ficticia, establecerla en "verdadero" para cada elemento en array1, luego buscar esta clave en elementos de array2. Limpia cuando hayas terminado.

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;
}

Por supuesto, debe asegurarse de que la clave no apareciera antes, de lo contrario destruirá sus datos ...

Answer 7

Contribuiré con lo que ha funcionado mejor para mí:

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;
};
}

Answer 8

Destructivo parece más simple, especialmente si podemos asumir que la entrada está ordenada:

/* 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;
}

No destructivo tiene que ser un pelo más complicado, ya que tenemos que seguir los índices:

/* 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;
}

Answer 9

El rendimiento de la implementación de @ atk para arreglos ordenados de primitivas puede mejorarse utilizando .pop en lugar de .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;
}

Creé un punto de referencia usando jsPerf: http://bit.ly/P9FrZK . Es aproximadamente tres veces más rápido de usar .pop.

Answer 10

Es bastante corto usando ES2015 y Sets. Acepta valores parecidos a una matriz como una cadena y elimina duplicados.

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(''''));

Answer 11

Este es probablemente el más simple, además de list1.filter (n => list2.includes (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"]

Answer 12

Mi contribución en términos de ES6. En general, encuentra la intersección de una matriz con un número indefinido de matrices proporcionadas como argumentos.

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>");

Answer 13

Otro enfoque indexado capaz de procesar cualquier número de matrices a la vez:

// 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;
};

Solo funciona con valores que pueden evaluarse como cadenas y debe pasarlos como una matriz como:

intersect ([arr1, arr2, arr3...]);

... pero acepta de forma transparente los objetos como parámetro o como cualquiera de los elementos a intersectar (siempre devolviendo una matriz de valores comunes). Ejemplos:

intersect ({foo: [1, 2, 3, 4], bar: {a: 2, j:4}}); // [2, 4]
intersect ([{x: "hello", y: "world"}, ["hello", "user"]]); // ["hello"]

EDIT: Acabo de notar que esto es, en cierto modo, un poco buggy.

Es decir: lo codifiqué pensando que las matrices de entrada no pueden contener repeticiones (como se muestra en el ejemplo).

Pero si las matrices de entrada contienen repeticiones, eso produciría resultados incorrectos. Ejemplo (usando la siguiente implementación):

intersect ([[1, 3, 4, 6, 3], [1, 8, 99]]);
// Expected: [ ''1'' ]
// Actual: [ ''1'', ''3'' ]

Afortunadamente, esto es fácil de solucionar simplemente agregando indexación de segundo nivel. Es decir:

Cambio:

 if (index[v] === undefined) index[v] = 0;
index[v]++;

por:

 if (index[v] === undefined) index[v] = {};
index[v][i] = true; // Mark as present in i input.

...y:

 if (index[i] == arrLength) retv.push(i);

por:

 if (Object.keys(index[i]).length == arrLength) retv.push(i);

Ejemplo completo:

// 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'' ]

Answer 14

Para las matrices que contienen solo cadenas o números, puede hacer algo con la clasificación, según algunas de las otras respuestas. Para el caso general de matrices de objetos arbitrarios, no creo que pueda evitar hacerlo a lo largo. Lo siguiente le dará la intersección de cualquier número de arreglos provistos como parámetros para 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"];

Answer 15

Por simplicidad:

// 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]

Beneficios:

• suciedad simple
• centrado en los datos
• Trabaja para un número arbitrario de listas
• Trabajos para longitudes arbitrarias de listas.
• Obras para tipos arbitrarios de valores.
• trabaja por orden arbitrario
• retiene la forma (orden de primera aparición en cualquier matriz)
• sale temprano siempre que sea posible
• Memoria segura, sin alterar los prototipos de funciones / arrays

Inconvenientes:

• mayor uso de memoria
• mayor uso de la CPU
• requiere una comprensión de reducir
• requiere la comprensión del flujo de datos

No querría usar esto para el trabajo del motor 3D o del núcleo, pero si tiene problemas para ejecutar esto en una aplicación basada en eventos, su diseño tiene problemas más grandes.

Answer 16

Si su entorno es compatible con el conjunto de ECMAScript 6 , de manera simple y supuestamente eficiente (vea el enlace de especificaciones):

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);
}

Más corto, pero menos legible (también sin crear el Set intersección adicional):

function intersect(a, b) {
return [...new Set(a)].filter(x => new Set(b).has(x));
}

Evitando un nuevo Set de b cada vez:

function intersect(a, b) {
var setB = new Set(b);
return [...new Set(a)].filter(x => setB.has(x));
}

Tenga en cuenta que al usar conjuntos solo obtendrá valores distintos, por lo que el new Set[1,2,3,3].size evalúa en 3 .

Answer 17

Una pequeña modificación del más pequeño aquí (la solución filter / indexOf ), es decir, la creación de un índice de los valores en una de las matrices con un objeto JavaScript, lo reducirá de O (N * M) al tiempo "probablemente" lineal. source2

function intersect(a, b) {
var aa = {};
a.forEach(function(v) { aa[v]=1; });
return b.filter(function(v) { return v in aa; });
}

Esta no es la solución más simple (es más código que filter + indexOf ), ni es la más rápida (probablemente más lenta por un factor constante que intersect_safe() ), pero parece un balance bastante bueno. Está en el lado muy simple, a la vez que proporciona un buen rendimiento, y no requiere entradas pre-ordenadas.

Answer 18

Usando jQuery :

var a = [1,2,3];
var b = [2,3,4,5];
var c = $(b).not($(b).not(a));
alert(c);

Answer 19

Use una combinación de Array.prototype.filter y Array.prototype.indexOf :

array1.filter(value => -1 !== array2.indexOf(value));

Answer 20

Utilizando Underscore.js o lodash.js

_.intersection( [0,345,324] , [1,0,324] ) // gives [0,324]

Answer 21

.reduce para construir un mapa, y .filter para encontrar la intersección. delete dentro del .filter nos permite tratar la segunda matriz como si fuera un conjunto único.

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;
});
}

Encuentro este enfoque bastante fácil de razonar. Se realiza en tiempo constante.

Answer 22

Intersección de matrices N en coffeescript

getIntersection: (arrays) ->
if not arrays.length
return []
a1 = arrays[0]
for a2 in arrays.slice(1)
a = (val for val in a1 when val in a2)
a1 = a
return a1.unique()

Answer 23

Sobre la base de la excelente respuesta de Anon, esta devuelve la intersección de dos o más matrices.

function arrayIntersect(arrayOfArrays)
{
var arrayCopy = arrayOfArrays.slice(),
baseArray = arrayCopy.pop();
return baseArray.filter(function(item) {
return arrayCopy.every(function(itemList) {
return itemList.indexOf(item) !== -1;
});
});
}

Answer 24

''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))

Answer 25

// 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]));

Recomiendo la solución sucinta, que supera a otras implementaciones en entradas grandes. Si el desempeño en pequeños insumos es importante, verifique las alternativas a continuación

Alternativas y comparación de rendimiento:

Consulte el siguiente fragmento de código para implementaciones alternativas y visite https://jsperf.com/array-intersection-comparison para ver las comparaciones de rendimiento.

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;
}

Resultados en Firefox 53:

• Ops / sec en arreglos grandes (10,000 elementos):

  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

• Ops / sec en arreglos pequeños (100 elementos):

  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

Answer 26

Aquí hay una implementación muy ingenua que estoy usando. No es destructivo y también se asegura de no duplicar entidades.

Array.prototype.contains = function(elem) {
return(this.indexOf(elem) > -1);
};
Array.prototype.intersect = function( array ) {
// this is naive--could use some optimization
var result = [];
for ( var i = 0; i < this.length; i++ ) {
if ( array.contains(this[i]) && !result.contains(this[i]) )
result.push( this[i] );
}
return result;
}

Answer 27

Extendí la respuesta de Tarulen para trabajar con cualquier número de arreglos. También debería funcionar con valores no enteros.

function intersect() {
const last = arguments.length - 1;
var seen={};
var result=[];
for (var i = 0; i < last; i++) {
for (var j = 0; j < arguments[i].length; j++) {
if (seen[arguments[i][j]]) {
seen[arguments[i][j]] += 1;
}
else if (!i) {
seen[arguments[i][j]] = 1;
}
}
}
for (var i = 0; i < arguments[last].length; i++) {
if ( seen[arguments[last][i]] === last)
result.push(arguments[last][i]);
}
return result;
}

Answer 28

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 ]

Answer 29

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;
}

Answer 30

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);
});