Najprostszy kod do przecięcia tablicy w javascript

607

Jaki jest najprostszy, pozbawiony biblioteki kod do implementacji skrzyżowań tablic w javascript? Chcę pisać

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

i dostać

[2, 3]
Piotr
źródło
16
Chcesz prosty czy szybki?
SLaks,
11
Priorytet jest prosty, ale nie może być tak oszałamiający, że będzie wieprzowym występem :)
Peter
4
Zrobiłem stronę testową JsFiddle Banchmark dla wszystkich metod tutaj, w tymfunkcji przecięcia _underscore . (im wyższy tym lepszy) ! wprowadź tutaj opis obrazu Do tej pory intersect_safe dawał najlepsze wyniki . TY i podkreśl najgorsze.
neoswf
Dodawanie breakdo Simple js loopswzrostów OPS / s do ~ 10M
Richard
19
W przypadku pominięcia : najprostsza odpowiedź nie jest zaakceptowana, ale na dole: stackoverflow.com/questions/1885557/…
redben

Odpowiedzi:

1076

Użyj kombinacji Array.prototype.filteri Array.prototype.indexOf:

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

Lub, jak sugeruje vrugtehagel w komentarzach, możesz użyć najnowszego Array.prototype.includesdla jeszcze prostszego kodu:

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

W przypadku starszych przeglądarek:

array1.filter(function(n) {
    return array2.indexOf(n) !== -1;
});
Zaraz.
źródło
9
Co możesz rozwiązać, dodając wersję biblioteki na prototypie tablicy.
Anon.
12
Tak, ale warto o tym wspomnieć.
Tim Down
18
Najlepsza odpowiedź tutaj, zarówno dla prostoty i pracy z nie-cyfr
Muhd
41
intersection([1,2,1,1,3], [1])zwraca [1, 1, 1]. Czy nie powinien wrócić [1]?
edjroot
21
Zamiast array2.indexOf(n) != -1jednego można również pisać array2.includes(n)dla jeszcze prostszego kodu.
vrugtehagel
157

Niszczenie wydaje się najprostsze, zwłaszcza jeśli możemy założyć, że dane wejściowe są posortowane:

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

Nieniszczące musi być włosy bardziej skomplikowane, ponieważ musimy śledzić indeksy:

/* 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;
}
atk
źródło
14
Występuje wiele błędów w intersect_safe: lengthjest właściwością w tablicach, a nie metodą. Jest takie undelared zmienna iw result.push(a[i]);. Wreszcie, to po prostu nie działa w ogólnym przypadku: dwa obiekty, w których żaden nie jest większy od drugiego według >operatora, niekoniecznie są równe. intersect_safe( [ {} ], [ {} ] ), na przykład da (po naprawieniu wcześniej wymienionych błędów) tablicę z jednym elementem, co jest wyraźnie błędne.
Tim Down
1
@ Ogranicz czas: Poprawiono wskazane błędy składniowe. To, czy jest poprawne czy niepoprawne uznanie czegokolwiek, ani geratera, ani mniej za równe, zależy od wymagań. W pierwotnym pytaniu nie zauważam niczego, co mówi, że zawartość powinna zawierać tablice. Teraz masz rację, mówiąc, że należy obsłużyć nieoczekiwane dane wejściowe, ale jeśli specyfikacja już nakazała, że ​​dane wejściowe muszą być tablicami liczb (jak się spodziewałem), to kod byłby w porządku.
atk
1
@atk: Rozumiem twój punkt widzenia, ponieważ przykład w pytaniu wykorzystuje tablice zawierające tylko liczby.
Tim Down
4
Możesz także użyć .slice(0)do utworzenia klonu tablicy intersect_safezamiast śledzenia indeksów.
johnluetke,
1
@thesmart: masz rację, są zdecydowanie bardziej wydajne sposoby, aby to zrobić. Powyższy kod miał być prosty, a nie szybki :)
atk
58

Jeśli twoje środowisko obsługuje Zestaw ECMAScript 6 , to jeden prosty i podobno wydajny (patrz link do specyfikacji) sposób:

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

Krótszy, ale mniej czytelny (również bez tworzenia dodatkowego skrzyżowania Set):

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

Unikanie nowy Setz bkażdej chwili:

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

Należy pamiętać, że podczas korzystania z zestawów będzie można dostać tylko odrębne wartości, co new Set[1,2,3,3].sizema wartość 3.

nbarbosa
źródło
1
jaka jest ta [...setA]składnia? Jakiś specjalny rodzaj operacji javascript?
jxramos
1
@ jxramos, czyli składnia Spread, w tym przypadku jest ona po prostu używana do tworzenia tablicy z elementów zestawu. „Array.from (setA)” również działałoby w tym przypadku, ale ponieważ pytanie brzmiało „najprostsze”, starałem się, aby czytanie tego wiersza było łatwiejsze. W tej kwestii myślę, że kod może być prostszy, więc zaktualizuję fragment kodu.
nbarbosa
@nbarbosa Jestem ciekawy: dlaczego „sklonowałeś” tablicę a? #filter nie niszczy oryginalnej tablicy, prawda? Tworzy nową tablicę?
bplittle
@bplittle Właśnie utworzyłem tablicę z zestawu w celu usunięcia duplikatów, w przeciwnym razie użycie tablicy bezpośrednio spowoduje zwrócenie duplikatów. Na przykład, jeśli użyłbym tablicy bezpośrednio, przecięcie ([1,2,2,4], [2,3]) dałoby [2, 2].
nbarbosa,
2
Czy ta x => new Set(b).has(x)funkcja strzałki nie zmienia bsię w zestaw za każdym razem, gdy jest wykonywana? Prawdopodobnie powinieneś zapisać ten zestaw w zmiennej.
Aran-Fey,
39

Korzystanie z Underscore.js lub lodash.js

_.intersection( [0,345,324] , [1,0,324] )  // gives [0,324]
Sai Ram
źródło
20
Op poprosił o „bez biblioteki”.
LinuxDisciple,
@LinuxDisciple Mój błąd, że tego nie zauważyłem. Dzięki za notatki
Sai Ram
33
W każdym razie jest to najwyższy wpis Google dla tego wyszukiwania, więc przydatne jest uzyskanie odpowiedzi z biblioteki. Dzięki.
webnoob
Ja też się cieszę, że to zostało opublikowane. Po raz pierwszy poczułam potrzebę pliku underscore.js. Zwykle mapowanie JavaScript i redukowanie potoków wykonują zadanie elegancko, ale nie tym razem.
Sridhar Sarnobat
I <3 Underscore i I <3 Jeremy Ashkenas (jego twórca), ale mimo to WYSOKIE polecam zamiast tego sprawdzić Lodash. Jest to w zasadzie lepsza wersja Underscore (pierwotnie był to fork), której jedynym minusem jest superoptymalizowany (a przez to prawie nieczytelny) kod źródłowy. Ludzie z Underscore rozważali nawet całkowite pozbycie się Underscore (i po prostu mówiąc ludziom, aby korzystali z Lodash), ale ludzie, którym zależy na czytelności kodu źródłowego, argumentowali, aby go zachować (właściwie byłem po tej stronie, ale od tego czasu przeszedłem na Lodash). @see github.com/jashkenas/underscore/issues/2182
machineghost
14

Mój wkład w kategoriach ES6. Zasadniczo znajduje przecięcie tablicy z nieokreśloną liczbą tablic podanych jako argumenty.

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

Redu
źródło
ten kod wygląda świetnie, ale nie rozumiem go całkowicie. Czy można to wyjaśnić, proszę?
niezwykły
1
@novembersky Gromadzi wszystkie tablice tematów w tablicy podobnej do, [[0,1,2,3,4,5,6,7,8,9],[0,2,4,6,8],[4,5,6,7],[4,6]]a następnie stosuje się .reduce(). Pierwsza [0,1,2,3,4,5,6,7,8,9].filter( e => [0,2,4,6,8].includes(e)operacja jest wykonywana, a wynik staje się nowy pi cstaje się [4,5,6,7]w następnej turze i kontynuuje tak dalej, aż nie będzie już więcej c.
Redu,
1
Jest to drogie rozwiązanie, jeśli pracujesz z dużymi zestawami danych.
Madbreaks,
1
Nie modyfikuj prototypeniepotrzebnie.
fregante
14

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

Polecam powyższe zwięzłe rozwiązanie, które przewyższa inne wdrożenia przy dużych nakładach. Jeśli wydajność przy małych nakładach ma znaczenie, sprawdź poniższe alternatywy.

Alternatywy i porównanie wydajności:

Zobacz poniższy fragment alternatywnych implementacji i sprawdź https://jsperf.com/array-intersection-comparison w celu porównania wydajności.

Wyniki w przeglądarce Firefox 53:

  • Operacje / s na dużych tablicach (10 000 elementów):

    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
  • Operacje / s na małych tablicach (100 elementów):

    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
le_m
źródło
2
intersect([1,2,2,3], [2,3,4,5])zwraca [2, 2, 3].
SeregPie
1
@SeregPie Dokładnie. Zgodnie z komentarzem „Zwróć elementy tablicy a także w b”
le_m
Odpowiedź jakościowa, jednak użycie zestawów zasadniczo zmienia wyniki, ponieważ pytanie op dotyczyło tylko przecięć tablic i nie wspomina / nie określa, jak radzić sobie z duplikatami. Nieśmiałe, ta odpowiedź może przynieść nieoczekiwane rezultaty, gdy istnieją duplikaty.
Madbreaks
1
Uwielbiam to, ale dodałeś niepotrzebną funkcję z „filter + obejmuje”. spróbuj a.filter(b.includes). Powinien działać znacznie szybciej (tak samo jak aktualizacja funkcji).
SEOF,
11

A może po prostu użyć tablic asocjacyjnych?

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

edytować:

// 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;
}
Steven Huwig
źródło
1
Ma to szansę tylko wtedy, gdy twoje tablice zawierają tylko ciągi lub liczby i jeśli żaden skrypt na twojej stronie się nie pomylił Object.prototype.
Tim Down
2
Przykładem OP było użycie liczb, a jeśli skrypt pomieszał się z Object.prototype, skrypt powinien zostać przepisany lub usunięty.
Steven Huwig,
Nie potrzebujesz zarówno (d1), jak i (d2). Utwórz (d2), a następnie przejdź przez (a) zamiast przez (d1).
StanleyH
Powinien być d[b[i]] = true;zamiast d[b[j]] = true;( inie j). Ale edycja wymaga 6 znaków.
Izhaki
@Izhaki dzięki, naprawiono. (Dodano // komentarz, aby obejść minimalne wymagania dotyczące edycji).
Steven Huwig
8
  1. Posortuj to
  2. sprawdź jeden po drugim z indeksu 0, utwórz z niego nową tablicę.

Coś w tym stylu, choć nie sprawdzone dobrze.

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: Algorytm przeznaczony tylko dla liczb i normalnych ciągów, przecięcie dowolnych tablic obiektów może nie działać.

TY
źródło
3
Sortowanie niekoniecznie pomoże tablicom dowolnych obiektów
Tim Down
Jeśli tablica nie jest posortowana, należy zapętlić około 1 000 000 razy, gdy przecinasz tablicę o długości 1000 x tablicę o długości 1000
TY
Myślę, że nie zrozumiałeś mojego punktu, że dowolne obiekty w JavaScript nie mają naturalnej kolejności sortowania, co oznacza, że ​​sortowanie tablicy dowolnych obiektów nie spowoduje grupowania równych obiektów. Nie jest dobrze mieć wydajny algorytm, który nie działa.
Tim Down
Ach, przepraszam, brakowało mi „dowolnych obiektów”, tak, masz rację. te obiekty nie mogą go posortować, a algorytm może na nich nie działać.
TY
8

Wydajność implementacji @ atk dla sortowanych tablic prymitywów można poprawić, używając .pop zamiast .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;
}

Stworzyłem test porównawczy za pomocą jsPerf: http://bit.ly/P9FrZK . Korzystanie z .pop jest około trzy razy szybsze.

xn.
źródło
1
Podobnie jak uwaga dodatkowa dla innych - będzie to działać tylko w przypadku liczb, a nie ciągów znaków.
Izhaki
Zauważ, że jeśli zastąpi a[aLast] > b[bLast]się a[aLast].localeCompare(b[bLast]) > 0(i tak samo z else ifponiżej), to będzie działać na łańcuchach.
andrew
1
Różnica prędkości zależy od wielkości tablic, ponieważ .popwynosi O (1) i .shift()wynosi O (n)
Esailija
8

Korzystanie z jQuery :

var a = [1,2,3];
var b = [2,3,4,5];
var c = $(b).not($(b).not(a));
alert(c);
Gowsikan
źródło
8
Można to również zapisać jako c = $(b).filter(a);, ale nie polecam polegania na jQuery do tego rodzaju manipulacji tablicami, ponieważ dokumentacja wspomina tylko, że działa ona dla elementów.
Stryner
1
To nie odpowiada na pytanie op: „Jaki jest najprostszy kod bez biblioteki ...”
Madbreaks,
7

W przypadku tablic zawierających tylko ciągi lub liczby możesz coś zrobić z sortowaniem, tak jak w przypadku niektórych innych odpowiedzi. W przypadku ogólnego przypadku tablic dowolnych obiektów nie sądzę, że można tego uniknąć na dłuższą metę. Poniżej przedstawiono skrzyżowanie dowolnej liczby tablic podanych jako parametry do 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"]; 
Tim Down
źródło
Działa to tylko w przypadku, gdy tożsamość obiektu jest jedyną formą równości.
Steven Huwig,
No tak, ale myślę, że to wydaje się naturalne dla większości ludzi. Podłączenie alternatywnej funkcji w celu wykonania innego testu równości jest również trywialne.
Tim Down
Myślę, że przypadkowo tworzysz zmienną globalną firstArr w swoim przykładzie.
Jason Jackson
@JasonJackson: Masz rację, dzięki. Wyraźnie zmieniłem zdanie, czy wywołać zmienną, firstArrczy firstArrayteż nie zaktualizowałem wszystkich referencji. Naprawiony.
Tim Down
7

Używanie ES2015 i zestawów jest dość krótkie. Akceptuje wartości podobne do tablic jak ciąg znaków i usuwa duplikaty.

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

SeregPie
źródło
Konwertuj z zestawu na tablicę za pomocą [... a] usunie zduplikowane elementy, dobry pomysł, dzięki
V-SHY
1
To rozwiązanie zostało dostarczone dwa razy wcześniej niż twoje.
Madbreaks
7

Możesz użyć Setod thisArgdnia Array#filteri przyjąć Set#hasjako oddzwonienie.

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

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

Nina Scholz
źródło
Nie wiem, dlaczego nie ma więcej głosów. To zdecydowanie najlepsza odpowiedź.
Paul Rooney
5

Drobne ulepszenie do najmniejszego tutaj (rozwiązanie filter / indexOf ), a mianowicie utworzenie indeksu wartości w jednej z tablic przy użyciu obiektu JavaScript, zmniejszy go z O (N * M) do „prawdopodobnie” czasu liniowego. źródło1 źródło2

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

To nie jest najprostsze rozwiązanie (jest to więcej kodu niż filter + indexOf ), ani też nie jest ono najszybsze (prawdopodobnie wolniejsze o stały współczynnik niż intersect_safe () ), ale wydaje się całkiem niezłą równowagą. Jest to bardzo prosta strona, przy jednoczesnym zapewnieniu dobrej wydajności i nie wymaga wstępnie posortowanych danych wejściowych.

David
źródło
5

Inne indeksowane podejście, które może przetwarzać dowolną liczbę tablic jednocześnie:

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

Działa tylko w przypadku wartości, które można oceniać jako ciągi znaków, i powinieneś przekazać je jako tablicę:

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

... ale w przejrzysty sposób przyjmuje obiekty jako parametr lub dowolny z elementów do przecięcia (zawsze zwraca tablicę wspólnych wartości). Przykłady:

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

EDYTOWAĆ: Właśnie zauważyłem, że jest to w pewnym sensie nieco wadliwe.

To znaczy: kodowałem to, myśląc, że tablice wejściowe same w sobie nie mogą zawierać powtórzeń (jak podany przykład nie).

Ale jeśli tablice wejściowe zawierają powtórzenia, przyniosłoby to błędne wyniki. Przykład (przy użyciu poniższej implementacji):

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

Na szczęście łatwo to naprawić, dodając indeksowanie drugiego poziomu. To jest:

Zmiana:

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

przez:

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

...i:

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

przez:

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

Kompletny przykład:

// 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' ]
bitifet
źródło
2
To zdecydowanie najlepsza odpowiedź z niewielką modyfikacją. Po var v = dodaniu wiersza if (typeof v == 'function') continue;pominie dodawanie funkcji do wyników. Dzięki!
Zsolti
Dzięki @Zsolti. Nie dodam twojej sugestii, ponieważ posiadanie funkcji (i sposób, w jaki chcemy to obsłużyć) jest poza zakresem oryginalnego pytania. Ale zobacz moją edycję: jeśli możesz mieć powtórzenia w tablicach wejściowych, oryginalna implementacja jest błędna. Naprawiłem to w mojej edycji. ... Z drugiej strony, jeśli wiesz na pewno, że nie będzie powtórzeń, oryginalna implementacja jest nieco tańsza.
bitifet
... o funkcjach można je również przecinać: jeśli wykryjemy je tak, jak mówi @Zsolti (za pomocą if (typeof v == 'function'), możemy użyć jego stringfikacji ( v.toString()) jako klucza do indeksu. Ale musimy zrobić coś, aby zachować go w nienaruszonym stanie. najłatwiejszym sposobem jest po prostu przypisanie oryginalnej funkcji jako wartości zamiast zwykłej wartości logicznej boolean, ale w takim przypadku najnowszy deindeksaton powinien również zostać zmieniony, aby wykryć ten warunek i przywrócić właściwą wartość (funkcję).
bitifet
Jak szybko to może być w przypadku 30 tablic ze 100 elementami. Jaka jest wydajność procesora?
pomocny
5

Możesz użyć (dla wszystkich przeglądarek oprócz IE):

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

lub dla IE:

const intersection = array1.filter(element => array2.indexOf(element) !== -1);
jota3
źródło
Byłoby miło, gdybyś mógł zmienić to w funkcję
lawina 1
@ avalanche1 const intersection = (a1, a2) => a1.filter (e => a2.includes (e));
jota3
4
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;
}
Gabe
źródło
4

Z pewnymi ograniczeniami dotyczącymi danych, możesz to zrobić w czasie liniowym !

Dla dodatnich liczb całkowitych : użyj tablicy odwzorowującej wartości na wartość logiczną „widziany / nie widział”.

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

Istnieje podobna technika dla obiektów : weź klucz zastępczy, ustaw go na „true” dla każdego elementu w tablicy1, a następnie poszukaj tego klucza w elementach tablicy2. Posprzątaj, kiedy skończysz.

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

Oczywiście musisz upewnić się, że klucz nie pojawił się wcześniej, w przeciwnym razie zniszczysz swoje dane ...

tarulen
źródło
Nawiasem mówiąc, można to łatwo rozszerzyć, aby przeciąć dowolną liczbę tablic: zamień wartość logiczną na liczby całkowite i zwiększaj za każdym razem, gdy się pojawi: możesz łatwo odczytać przecięcie w ostatniej rundzie.
tarulen
Ciekawe rozwiązanie, podoba mi się. Większość innych rozwiązań to O (n ^ 2), ale jest to O (n). Dodałem kod liczbowy do skrzypek wydajnościowych ericP tutaj jsfiddle.net/321juyLu/2 . Przyszedł trzeci, ja
lubię
3

Przyczynię się do tego, co dla mnie działa najlepiej:

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;
};
}
Johan
źródło
3

„indexOf” dla 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]
Martin Roberto Mondragon Sotel
źródło
2

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

Vlad Bezden
źródło
2

Funkcjonalne podejście z ES2015

Podejście funkcjonalne musi rozważyć użycie tylko czystych funkcji bez skutków ubocznych, z których każda dotyczy tylko jednego zadania.

Ograniczenia te zwiększają możliwość łączenia i ponownego wykorzystywania zaangażowanych funkcji.

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

Należy pamiętać, że Setużywany jest typ macierzysty , który ma korzystną wydajność wyszukiwania.

Unikaj duplikatów

Oczywiście wielokrotnie powtarzające się przedmioty z pierwszego Arraysą zachowane, podczas gdy drugi Arrayjest zduplikowany. To może być lub nie być pożądane zachowanie. Jeśli potrzebujesz unikalnego wyniku, zastosuj dedupepierwszy 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) );

Oblicz przecięcie dowolnej liczby Arrays

Jeśli chcesz, aby obliczyć przecięcie numer dowolnie ustawionym na Arrays tylko komponować intersectz foldl. Oto funkcja wygody:

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


źródło
Imponująco funkcjonalne: musiałem zrobić podwójną próbę, aby potwierdzić, że to nie jest Haskell. Jedyny nitpick to: (expr ? true : false)jest zbędny. Używaj tylko exprwtedy, gdy rzeczywiste booleany nie są potrzebne, tylko prawda / fałsz.
jose_castro_arnaud
2

Dla prostoty:

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

Korzyści:

  • brud prosty
  • zorientowane na dane
  • działa dla dowolnej liczby list
  • działa dla dowolnych długości list
  • działa dla dowolnych typów wartości
  • działa dla dowolnej kolejności sortowania
  • zachowuje kształt (kolejność pierwszego pojawienia się w dowolnej tablicy)
  • wychodzi wcześniej, jeśli to możliwe
  • bezpieczny dla pamięci, bez manipulacji przy prototypach Function / Array

Wady:

  • wyższe zużycie pamięci
  • wyższe użycie procesora
  • wymaga zrozumienia redukcji
  • wymaga zrozumienia przepływu danych

Nie chciałbyś używać tego do pracy z silnikiem 3D lub jądrem, ale jeśli masz problemy z uruchomieniem go w aplikacji opartej na zdarzeniach, twój projekt ma większe problemy.

Norguard
źródło
2

.reducezbudować mapę i .filterznaleźć skrzyżowanie. deletew obrębie .filterpozwala nam traktować drugą tablicę tak, jakby była unikalnym zestawem.

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

Uważam to podejście za dość łatwe do uzasadnienia. Działa w stałym czasie.

Belden
źródło
2

Jest to prawdopodobnie najprostszy, poza 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"]

Chris Lwin
źródło
to ma złożoność czasową O (nm) ... można to rozwiązać w O (n + m)
Alchuang
2

Jeśli potrzebujesz, aby obsługiwał przecinanie wielu tablic:

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]

Belfordz
źródło
Ale jak szybkie jest to rozwiązanie dla 30 tablic ze 100 elementami?
pomocny
Wykorzystuje to wyłącznie rodzime metody Javascript, dlatego maszyna wirtualna, w której kod będzie działał, może go optymalizować w miarę możliwości. Jestem całkiem pewien, że nie ma szybszego rozwiązania, biorąc pod uwagę, że używasz tego w nowoczesnej wersji V8 w stosunku do wieku tego komentarza.
Belfordz
2

Prosty sposób w stylu ES6.

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

Przykład:

intersection([1, 2, 3], [4, 3, 2]); // [2, 3]
Michaił Gorelyshev
źródło
2

Napisałem funkcję przecięcia, która może nawet wykryć przecięcie tablicy obiektów na podstawie konkretnej właściwości tych obiektów.

Na przykład,

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

i chcemy przecięcia na podstawie idwłaściwości, wówczas dane wyjściowe powinny być:

[{id: 20}]

Jako taka funkcja tego samego (uwaga: kod ES6) to:

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

i możesz wywołać funkcję jako:

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

Uwaga: ta funkcja znajduje przecięcie, biorąc pod uwagę, że pierwsza tablica jest tablicą podstawową, a zatem wynikiem przecięcia będzie tablica podstawowa.

Mridul Meharia
źródło
2

Myślę, że będzie to szybsze z czasem O (tablica 1 + tablica 2) przy założeniu, że map.has () to ~ O (1). Proszę, popraw mnie, jeśli się mylę.

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

ajaix
źródło
1

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

Źródło: http://underscorejs.org/docs/underscore.html#section-62

dorycki
źródło
Niezłe odniesienie, jeśli dostępny jest undesrcore
Dimitrios Mistriotis,