Einfachste Code für Array Schnittpunkt in Javascript

Question

Was ist die einfachste, Bibliothek-freien Code für die Umsetzung von Array-Kreuzungen in Javascript? Ich möchte schreiben

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

und erhalten

[2, 3]

Answer 1

Verwenden Sie eine Kombination aus Array.prototype.filter y Array.prototype.includes :

const filteredArray = array1.filter(value => array2.includes(value));

Bei älteren Browsern, mit Array.prototype.indexOf und ohne Pfeilfunktion:

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

NB! Beide .includes y .indexOf vergleicht intern Elemente im Array mit Hilfe von === Wenn das Array also Objekte enthält, werden nur Objektreferenzen verglichen (nicht deren Inhalt). Wenn Sie Ihre eigene Vergleichslogik angeben wollen, verwenden Sie Array.prototype.some stattdessen.

Answer 2

Destruktiv scheint am einfachsten, vor allem wenn wir davon ausgehen können, dass die Eingabe sortiert ist:

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

Die nicht-destruktive Methode ist ein wenig komplizierter, da wir Indizes verfolgen müssen:

/* 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 3

Wenn Ihre Umgebung Folgendes unterstützt ECMAScript 6 Satz eine einfache und vermeintlich effiziente Methode (siehe Link zur Spezifikation):

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

Kürzer, aber weniger lesbar (auch ohne die zusätzliche Kreuzung Set ):

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

Beachten Sie, dass Sie bei der Verwendung von Mengen nur eindeutige Werte erhalten, also new Set([1, 2, 3, 3]).size wertet aus zu 3 .

Answer 4

Verwendung von Underscore.js o lodash.js

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

Answer 5

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

Ich empfehle die obige prägnante Lösung, die andere Implementierungen bei großen Eingaben übertrifft. Wenn die Leistung bei kleinen Eingaben wichtig ist, sollten Sie die nachstehenden Alternativen prüfen.

Alternativen und Leistungsvergleich:

Siehe den folgenden Ausschnitt für alternative Implementierungen und Überprüfung https://jsperf.com/array-intersection-comparison für Leistungsvergleiche.

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

Ergebnisse in Firefox 53:

• Ops/sec auf großen Arrays (10.000 Elemente):

  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 auf kleinen Arrays (100 Elemente):

  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