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

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

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

y obten

[2, 3]

Use una combinación de Array.prototype.filtery Array.prototype.indexOf:

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

O como vrugtehagel sugirió en los comentarios, puede usar el Array.prototype.includescódigo más reciente para un código aún más simple:

array1.filter(value => array2.includes(value))

Para navegadores antiguos:

array1.filter(function(n) {
    return array2.indexOf(n) !== -1;
});

Destructivo parece más simple, especialmente si podemos suponer 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 cabello más complicado, ya que tenemos que rastrear í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;
}

Si su entorno es compatible con ECMAScript 6 Set , una forma simple y supuestamente eficiente (ver enlace de especificación):

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 la intersección adicional Set):

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

Evitar un nuevo Setde bcada vez:

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

Tenga en cuenta que cuando use conjuntos solo obtendrá valores distintos, por lo tanto se new Set[1,2,3,3].sizeevalúa como 3.

Usando Underscore.js o lodash.js

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

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

// 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 una solución sucinta que supera a otras implementaciones en entradas grandes. Si el rendimiento en entradas pequeñas es importante, verifique las alternativas a continuación.

Alternativas y comparación de rendimiento:

Consulte el siguiente fragmento para ver implementaciones alternativas y consulte 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 / seg en matrices 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 / seg en matrices pequeñas (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

¿Qué tal si solo usamos 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;
}

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

Algo como esto, aunque no se ha 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 solo está destinado a Números y Cadenas normales, la intersección de matrices de objetos arbitrarios puede no funcionar.

El rendimiento de la implementación de @ atk para matrices ordenadas de primitivas se puede mejorar 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 usar .pop.

Usando jQuery :

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

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 puedas evitar hacerlo a la larga. Lo siguiente le dará la intersección de cualquier número de matrices proporcionadas 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"]; 

Es bastante corto usando ES2015 y Sets. Acepta valores de tipo 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(''));

Se puede usar un Setcomo thisArgde Array#filtery tomar Set#hascomo devolución de llamada.

function intersection(a, b) {
    return a.filter(Set.prototype.has, new Set(b));
}

console.log(intersection([1, 2, 3], [2, 3, 4, 5]));

Un pequeño ajuste al más pequeño aquí (la solución filter / indexOf ), es decir, crear un índice de los valores en una de las matrices usando un objeto JavaScript, lo reducirá de O (N * M) a "probablemente" tiempo lineal. Source1 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 buen balance. Es del lado muy simple, a la vez que proporciona un buen rendimiento, y no requiere entradas ordenadas previamente.

Otro enfoque indexado capaz de procesar cualquier cantidad 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;
};

Funciona solo para valores que pueden evaluarse como cadenas y debe pasarlos como una matriz como:

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

... pero acepta objetos de forma transparente como parámetro o como cualquiera de los elementos que se van a intersectar (siempre devuelve 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"]

EDITAR: Acabo de notar que esto es, en cierto modo, un poco defectuoso.

Es decir: lo codifiqué pensando que las matrices de entrada por sí mismas no pueden contener repeticiones (como el ejemplo provisto no lo hace).

Pero si las matrices de entrada contienen repeticiones, eso produciría resultados incorrectos. Ejemplo (usando la implementación a continuació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' ]

Puede usar (para todos los navegadores excepto IE):

const intersection = array1.filter(element => array2.includes(element));

o para IE:

const intersection = array1.filter(element => array2.indexOf(element) !== -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;
}

Con algunas restricciones en sus datos, puede hacerlo en forma lineal. tiempo !

Para enteros positivos : utilice una matriz que asigne los valores a un 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 : tome una clave ficticia, configúrela como "verdadera" para cada elemento de la matriz1, luego busque esta clave en los elementos de la matriz2. 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, debes asegurarte de que la clave no apareció antes, de lo contrario estarás destruyendo tus datos ...

Contribuiré con lo que me ha funcionado mejor:

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

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

Un enfoque funcional con ES2015

Un enfoque funcional debe considerar el uso de funciones puras sin efectos secundarios, cada uno de los cuales solo tiene que ver con un solo trabajo.

Estas restricciones mejoran la componibilidad 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 el nativo Set se utiliza el tipo , que tiene un rendimiento de búsqueda ventajoso.

Evitar duplicados

Obviamente, los elementos que ocurren repetidamente del primero Arrayse conservan, mientras que el segundo Arrayse desduplica. Este puede ser o no el comportamiento deseado. Si necesita un resultado único, simplemente aplique dedupeel 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) );

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

Si desea calcular la intersección de un número arbitrario de Arrays simplemente componga intersectcon 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) );

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 datos
• funciona para un número arbitrario de listas
• funciona para longitudes arbitrarias de listas
• funciona para tipos de valores arbitrarios
• funciona para un orden de clasificación arbitrario
• conserva la forma (orden de la primera aparición en cualquier matriz)
• sale temprano donde sea posible
• memoria segura, sin alterar los prototipos de función / matriz

Inconvenientes:

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

No querrás usar esto para el motor 3D o el trabajo del kernel, pero si tienes problemas para que esto se ejecute en una aplicación basada en eventos, tu diseño tiene problemas más grandes.

.reducepara construir un mapa y .filterencontrar la intersección. deletedentro de .filternos 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;
  });
}

Me parece bastante fácil razonar sobre este enfoque. Se realiza en tiempo constante.

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

Si necesita que maneje la intersección de múltiples matrices:

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]

Estilo ES6 de forma sencilla.

const intersection = (a, b) => {
  const s = new Set(b);
  return a.filter(x => s.has(x));
};

Ejemplo:

intersection([1, 2, 3], [4, 3, 2]); // [2, 3]

He escrito una función de intersección que incluso puede detectar la intersección de una matriz de objetos en función de la propiedad particular de esos objetos.

Por ejemplo,

if arr1 = [{id: 10}, {id: 20}]
and arr2 =  [{id: 20}, {id: 25}]

y queremos intersección basada en la idpropiedad, entonces la salida debería ser:

[{id: 20}]

Como tal, la función para el mismo (nota: código ES6) es:

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

y puedes llamar a la función como:

intersect(arr1, arr2, [elem => elem.id, elem => elem.id])

También tenga en cuenta: esta función encuentra la intersección considerando que la primera matriz es la matriz primaria y, por lo tanto, el resultado de la intersección será el de la matriz primaria.

Piense que esto será más rápido con el tiempo O (array1 + array2) suponiendo que map.has () es ~ O (1). Corríjame si está equivocado.

const intersection = (a1, a2) => {
  let map = new Map();
  let result = []
  for (let i of a1) {
    if (!map.has(i)) map.set(i, true);
  }
  for (let i of a2) {
    if (map.has(i)) result.push(i)
  }
  return result;
}

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