Code le plus simple pour l'intersection de tableaux en javascript

Quel est le code le plus simple et sans bibliothèque pour implémenter les intersections de tableaux en javascript? Je veux ecrire

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

et obtenir

[2, 3]

Utilisez une combinaison de Array.prototype.filteret Array.prototype.indexOf:

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

Ou comme suggéré par vrugtehagel dans les commentaires, vous pouvez utiliser le plus récent Array.prototype.includespour un code encore plus simple:

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

Pour les navigateurs plus anciens:

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

Destructif semble le plus simple, surtout si l'on peut supposer que l'entrée est triée:

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

Non destructif doit être un cheveu plus compliqué, car nous devons suivre les indices:

/* 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 votre environnement prend en charge ECMAScript 6 Set , une manière simple et supposée efficace (voir lien de spécification):

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

Plus court, mais moins lisible (également sans créer l'intersection supplémentaire Set):

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

Éviter une nouvelle Setde bchaque fois:

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

Notez que lors de l' utilisation des ensembles vous obtenez seulement des valeurs distinctes, donc new Set[1,2,3,3].sizeévalue à 3.

Utilisation de Underscore.js ou lodash.js

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

Ma contribution en termes ES6. En général, il trouve l'intersection d'un tableau avec un nombre indéfini de tableaux fournis comme arguments.

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

Je recommande la solution succincte ci-dessus qui surpasse les autres implémentations sur de grandes entrées. Si les performances sur les petites entrées sont importantes, vérifiez les alternatives ci-dessous.

Alternatives et comparaison des performances:

Consultez l'extrait de code suivant pour d'autres implémentations et consultez https://jsperf.com/array-intersection-comparison pour des comparaisons de performances.

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

Résultats dans Firefox 53:

• Ops / sec sur les grands tableaux (10 000 éléments):

  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 sur de petits tableaux (100 éléments):

  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

Que diriez-vous d'utiliser simplement des tableaux associatifs?

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

Éditer:

// 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. Trier
2. vérifiez un par un à partir de l'index 0, créez un nouveau tableau à partir de cela.

Quelque chose comme ça, pas bien testé cependant.

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: l'algorithme destiné uniquement aux nombres et aux chaînes normales, l'intersection de tableaux d'objets arbitraires peut ne pas fonctionner.

Les performances de l'implémentation de @ atk pour les tableaux triés de primitives peuvent être améliorées en utilisant .pop plutôt que .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;
}

J'ai créé une référence à l'aide de jsPerf: http://bit.ly/P9FrZK . Il est environ trois fois plus rapide d'utiliser .pop.

Utilisation de jQuery :

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

Pour les tableaux contenant uniquement des chaînes ou des nombres, vous pouvez faire quelque chose avec le tri, selon certaines des autres réponses. Pour le cas général des tableaux d'objets arbitraires, je ne pense pas que vous puissiez éviter de le faire à long terme. Ce qui suit vous donnera l'intersection de n'importe quel nombre de tableaux fournis comme paramètres pour 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"]; 

C'est assez court en utilisant ES2015 et Sets. Accepte les valeurs de type tableau comme une chaîne et supprime les doublons.

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

Vous pouvez utiliser un SetasthisArg de Array#filteret prendre Set#hascomme rappel.

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

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

Un petit ajustement au plus petit ici (la solution filter / indexOf ), à savoir la création d'un index des valeurs dans l'un des tableaux à l'aide d'un objet JavaScript, le réduira de O (N * M) à un temps linéaire "probablement". source1 source2

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

Ce n'est pas la solution la plus simple (c'est plus de code que filter + indexOf ), ni la plus rapide (probablement plus lente d'un facteur constant que intersect_safe () ), mais cela semble être un assez bon équilibre. Il est très simple, tout en offrant de bonnes performances, et il ne nécessite pas d'entrées pré-triées.

Une autre approche indexée capable de traiter n'importe quel nombre de tableaux à la fois:

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

Cela ne fonctionne que pour les valeurs qui peuvent être évaluées en tant que chaînes et vous devez les passer sous forme de tableau comme:

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

... mais il accepte de manière transparente les objets comme paramètre ou comme l'un des éléments à recouper (renvoyant toujours un tableau de valeurs communes). Exemples:

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

EDIT: Je viens de remarquer que c'est, en quelque sorte, légèrement buggé.

C'est-à-dire: je l'ai codé en pensant que les tableaux d'entrée ne peuvent pas contenir de répétitions (comme l'exemple fourni ne le fait pas).

Mais si les tableaux d'entrée contiennent des répétitions, cela produira des résultats erronés. Exemple (en utilisant l'implémentation ci-dessous):

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

Heureusement, cela est facile à résoudre en ajoutant simplement une indexation de second niveau. C'est:

Changement:

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

par:

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

...et:

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

par:

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

Exemple complet:

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

Vous pouvez utiliser (pour tous les navigateurs sauf IE):

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

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

Avec quelques restrictions sur vos données, vous pouvez le faire en temps linéaire !

Pour les entiers positifs : utilisez un tableau mappant les valeurs à un booléen "vu / non vu".

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

Il existe une technique similaire pour les objets : prenez une clé factice, définissez-la sur "true" pour chaque élément de array1, puis recherchez cette clé dans les éléments de array2. Nettoyez quand vous avez terminé.

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

Bien sûr, vous devez vous assurer que la clé n'apparaissait pas auparavant, sinon vous allez détruire vos données ...

Je contribuerai avec ce qui a fonctionné le mieux pour moi:

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

Une approche fonctionnelle avec ES2015

Une approche fonctionnelle doit envisager d'utiliser uniquement des fonctions pures sans effets secondaires, dont chacune ne concerne qu'un seul travail.

Ces restrictions améliorent la composabilité et la réutilisabilité des fonctions impliquées.

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

Veuillez noter que le Settype natif est utilisé, ce qui présente des performances de recherche avantageuses.

Évitez les doublons

Les éléments apparaissant de manière répétée du premier Arraysont évidemment conservés, tandis que le second Arrayest dédoublonné. Cela peut être ou ne pas être le comportement souhaité. Si vous avez besoin d'un résultat unique, appliquez simplement dedupele premier argument:

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

Calculer l'intersection de n'importe quel nombre de Arrays

Si vous voulez calculer l'intersection d'un nombre arbitraire de Arrays composez simplement intersectavec foldl. Voici une fonction pratique:

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

Pour la simplicité:

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

Avantages:

• saleté simple
• centré sur les données
• fonctionne pour un nombre arbitraire de listes
• fonctionne pour des longueurs arbitraires de listes
• fonctionne pour les types de valeurs arbitraires
• fonctionne pour l'ordre de tri arbitraire
• conserve sa forme (ordre de première apparition dans n'importe quel tableau)
• sort tôt si possible
• sans danger pour la mémoire, sans altération des prototypes de fonctions / matrices

Désavantages:

• utilisation de la mémoire plus élevée
• utilisation du processeur plus élevée
• nécessite une compréhension de réduire
• nécessite une compréhension du flux de données

Vous ne voudriez pas l'utiliser pour le moteur 3D ou le travail du noyau, mais si vous avez des problèmes pour que cela fonctionne dans une application basée sur des événements, votre conception a de plus gros problèmes.

.reducepour construire une carte et .filtertrouver l'intersection. deletedans le .filternous permet de traiter le deuxième tableau comme s'il s'agissait d'un ensemble unique.

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

Je trouve cette approche assez facile à raisonner. Il fonctionne en temps constant.

C'est probablement le plus simple, en plus 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 vous devez le faire gérer plusieurs tableaux entrecroisés:

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]

Manière simple de style ES6.

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

Exemple:

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

J'ai écrit une fonction d'intersection qui peut même détecter l'intersection d'un tableau d'objets en fonction de la propriété particulière de ces objets.

Par exemple,

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

et nous voulons une intersection basée sur la idpropriété, alors la sortie devrait être:

[{id: 20}]

En tant que tel, la fonction pour le même (note: code ES6) est:

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

et vous pouvez appeler la fonction comme:

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

Notez également: cette fonction trouve une intersection étant donné que le premier tableau est le tableau principal et donc le résultat de l'intersection sera celui du tableau principal.

Pensez que ce sera plus rapide avec le temps O (array1 + array2) en supposant que map.has () est ~ O (1). Veuillez me corriger en cas d'erreur.

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

Voici l' implémentation 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;
};

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