Jaki jest najszybszy lub najbardziej elegancki sposób obliczenia różnicy zestawów przy użyciu tablic JavaScript?

105

Niech Ai Bbędą dwoma zbiorami. Szukam naprawdę szybkich lub eleganckich sposobów na obliczenie różnicy zestawów ( A - Blub A \B, w zależności od preferencji) między nimi. Zgodnie z tytułem oba zestawy są przechowywane i przetwarzane jako tablice JavaScript.

Uwagi:

  • Sztuczki specyficzne dla Gecko są w porządku
  • Wolałbym trzymać się natywnych funkcji (ale jestem otwarty na lekką bibliotekę, jeśli jest znacznie szybsza)
  • Widziałem, ale nie testowałem, JS.Set (patrz poprzedni punkt)

Edycja: zauważyłem komentarz dotyczący zestawów zawierających zduplikowane elementy. Kiedy mówię „ustaw” mam na myśli definicję matematyczną, co oznacza (między innymi), że nie zawierają one zduplikowanych elementów.

Matt Ball
źródło
Co to za terminologia „ustawiania różnicy”, której używasz? Czy to z C ++ czy coś?
Josh Stodola
Co masz w zestawach? W zależności od typu, do którego celujesz (np. Liczby), obliczenie różnicy zestawu może być wykonane naprawdę szybko i elegancko. Jeśli twoje zestawy zawierają (powiedzmy) elementy DOM, utkniesz z powolną indexOfimplementacją.
Crescent Fresh
@Crescent: moje zestawy zawierają liczby - przepraszam, że nie określam. @Josh: to standardowa operacja na zbiorach w matematyce ( en.wikipedia.org/wiki/Set_%28mathematics%29#Complements )
Matt Ball,
1
@MattBall Nie, widziałem to. Ale pytanie Josha było ważne i bez odpowiedzi, więc odpowiedziałem :)
Pat

Odpowiedzi:

175

jeśli nie wiesz, czy to jest najskuteczniejsze, ale może najkrótsze

A = [1, 2, 3, 4];
B = [1, 3, 4, 7];

diff = A.filter(function(x) { return B.indexOf(x) < 0 })

console.log(diff);

Zaktualizowano do ES6:

A = [1, 2, 3, 4];
B = [1, 3, 4, 7];

diff = A.filter(x => !B.includes(x) );

console.log(diff);
user187291
źródło
8
+1: nie najbardziej wydajne rozwiązanie, ale zdecydowanie krótkie i czytelne
Christoph
10
Uwaga: array.filter nie obsługuje różnych przeglądarek (np. Nie w IE). @Matt wydaje się nie mieć znaczenia, ponieważ stwierdził, że „sztuczki specyficzne dla Gecko są w porządku”, ale myślę, że warto o tym wspomnieć.
Eric Bréchemier
45
To jest bardzo powolne. O (| A | * | B |)
glebm
1
@ EricBréchemier To jest teraz obsługiwane (od IE 9). Array.prototype.filter to standardowa funkcja ECMAScript.
Quentin Roy
5
W ES6 możesz użyć !B.includes(x)zamiast B.indexOf(x) < 0:)
c24w
87

Cóż, 7 lat później, dzięki obiektowi Set z ES6 jest to dość łatwe (ale wciąż nie tak zwarte jak w Pythonie A - B ) i podobno szybsze niż w indexOfprzypadku dużych tablic:

console.clear();
let a = new Set([1, 2, 3, 4]);
let b = new Set([5, 4, 3, 2]);


let a_minus_b = new Set([...a].filter(x => !b.has(x)));
let b_minus_a = new Set([...b].filter(x => !a.has(x)));
let a_intersect_b = new Set([...a].filter(x => b.has(x))); 

console.log([...a_minus_b]) // {1}
console.log([...b_minus_a]) // {5}
console.log([...a_intersect_b]) // {2,3,4}

Mediolan
źródło
1
Również znacznie szybszy niż indexOf w przypadku dużych tablic.
Estus Flask
103
Dlaczego zestawy JavaScript nie mają wbudowanej unii / przecięcia / różnicy są poza mną ...
SwiftsNamesake
6
Całkowicie się zgadzam; powinny to być prymitywy niższego poziomu zaimplementowane w silniku js. To mnie też przerasta ...
Rafael
4
@SwiftsNamesake Jest propozycja zestawu wbudowanych metod, o której miejmy nadzieję będzie mowa w styczniu 2018 na github.com/tc39/agendas/blob/master/2018/01.md .
John
15

Możesz użyć obiektu jako mapy, aby uniknąć liniowego skanowania Bkażdego elementu, Ajak w odpowiedzi użytkownika187291 :

function setMinus(A, B) {
    var map = {}, C = [];

    for(var i = B.length; i--; )
        map[B[i].toSource()] = null; // any other value would do

    for(var i = A.length; i--; ) {
        if(!map.hasOwnProperty(A[i].toSource()))
            C.push(A[i]);
    }

    return C;
}

Do uzyskania unikalnych nazw właściwości używana jest toSource()metoda niestandardowa ; jeśli wszystkie elementy mają już unikalne reprezentacje łańcuchowe (tak jak w przypadku liczb), możesz przyspieszyć kod, porzucając toSource()wywołania.

Christoph
źródło
9

Najkrótsza, wykorzystująca jQuery, to:

var A = [1, 2, 3, 4];
var B = [1, 3, 4, 7];

var diff = $(A).not(B);

console.log(diff.toArray());
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>

perhelium
źródło
To zwraca obiekt różnicy.
Drew Baker
2
jQuery notnie działa już z obiektami ogólnymi od 3.0.0-rc1. Zobacz github.com/jquery/jquery/issues/3147
Marc-André Lafortune
2
Dodanie zależności od biblioteki innej firmy ~ 70k tylko w tym celu nie jest dobrym pomysłem , ponieważ to samo można osiągnąć w zaledwie kilku wierszach kodu, jak pokazano w innych odpowiedziach tutaj. Jeśli jednak używasz już jQuery w swoim projekcie, będzie to działać dobrze.
CBarr
Chociaż to podejście ma mniej kodu, ale nie zapewnia żadnego wyjaśnienia złożoności przestrzennej i czasowej różnych algorytmów oraz struktury danych, których używa do wykonania metody. Programiści mogą tworzyć oprogramowanie bez oceny, gdy dozwolone jest zwiększanie skali danych lub przy ograniczonej pamięci. Jeśli zastosujesz takie podejście z dużym zestawem danych, wydajność może pozostać nieznana do czasu dalszych badań nad kodem źródłowym.
Downhillski
To jest po prostu zwrócenie ilości (w tym przypadku 2) elementów A, których nie ma w B. Zamiana 2 na tablicę jest bezcelowa ...
Alex
6

Hashowałbym tablicę B, a następnie zachowałbym wartości z tablicy A nieobecne w B:

function getHash(array){
  // Hash an array into a set of properties
  //
  // params:
  //   array - (array) (!nil) the array to hash
  //
  // return: (object)
  //   hash object with one property set to true for each value in the array

  var hash = {};
  for (var i=0; i<array.length; i++){
    hash[ array[i] ] = true;
  }
  return hash;
}

function getDifference(a, b){
  // compute the difference a\b
  //
  // params:
  //   a - (array) (!nil) first array as a set of values (no duplicates)
  //   b - (array) (!nil) second array as a set of values (no duplicates)
  //
  // return: (array)
  //   the set of values (no duplicates) in array a and not in b, 
  //   listed in the same order as in array a.

  var hash = getHash(b);
  var diff = [];
  for (var i=0; i<a.length; i++){
    var value = a[i];
    if ( !hash[value]){
      diff.push(value);
    }
  }
  return diff;
}
Eric Bréchemier
źródło
to jest dokładnie ten sam algorytm, który opublikowałem pół godziny temu
Christoph
@Christoph: masz rację ... Nie zauważyłem tego. Uważam, że moja implementacja jest łatwiejsza do zrozumienia :)
Eric Bréchemier
Myślę, że lepiej jest obliczyć różnicę poza getDifference, aby można ją było wielokrotnie wykorzystać. Może być opcjonalne: getDifference(a, b, hashOfB)jeśli nie zostanie przekazane, zostanie obliczone, w przeciwnym razie zostanie ponownie użyte w takiej postaci, w jakiej jest.
Christophe Roussy,
4

Uwzględniając pomysł Christopha i zakładając kilka niestandardowych metod iteracji na tablicach i obiektach / hashach ( eachi przyjaciołach), możemy uzyskać różnicę, sumę i przecięcie w czasie liniowym w sumie w około 20 liniach:

var setOPs = {
  minusAB : function (a, b) {
    var h = {};
    b.each(function (v) { h[v] = true; });
    return a.filter(function (v) { return !h.hasOwnProperty(v); });
  },
  unionAB : function (a, b) {
    var h = {}, f = function (v) { h[v] = true; };
    a.each(f);
    b.each(f);
    return myUtils.keys(h);
  },
  intersectAB : function (a, b) {
    var h = {};
    a.each(function (v) { h[v] = 1; });
    b.each(function (v) { h[v] = (h[v] || 0) + 1; });
    var fnSel = function (v, count) { return count > 1; };
    var fnVal = function (v, c) { return v; };
    return myUtils.select(h, fnSel, fnVal);
  }
};

Zakłada się, że eachi filtersą zdefiniowane dla tablic oraz że mamy dwie metody narzędziowe:

  • myUtils.keys(hash): zwraca tablicę z kluczami z skrótu

  • myUtils.select(hash, fnSelector, fnEvaluator): zwraca tablicę z wynikami wywołania fnEvaluator par klucz / wartość, dla których fnSelectorzwraca prawdę.

select()Jest luźno inspirowany Common Lisp, a jest jedynie filter()i map()w jednym. (Lepiej byłoby mieć je zdefiniowaneObject.prototype , ale zrobienie tego wraki spustoszenie w jQuery, więc zdecydowałem się na statyczne metody narzędziowe).

Wydajność: testowanie w

var a = [], b = [];
for (var i = 100000; i--; ) {
  if (i % 2 !== 0) a.push(i);
  if (i % 3 !== 0) b.push(i);
}

daje dwa zestawy po 50 000 i 66 666 elementów. Przy tych wartościach AB trwa około 75 ms, podczas gdy suma i przecięcie trwają około 150 ms. (Mac Safari 4.0, synchronizacja z wykorzystaniem daty JavaScript).

Myślę, że to przyzwoita zapłata za 20 linii kodu.

jg-faustus
źródło
1
nadal powinieneś sprawdzać, hasOwnProperty()nawet jeśli elementy są numeryczne: w przeciwnym razie coś w rodzaju Object.prototype[42] = true;średnich 42nie może nigdy wystąpić w zestawie wyników
Christoph
Przyznano, że byłoby możliwe ustawienie 42 w ten sposób, ale czy istnieje półrealistyczny przypadek użycia, w którym ktokolwiek by to zrobił? Ale w przypadku ciągów ogólnych rozumiem - może to łatwo powodować konflikt z jakąś zmienną lub funkcją Object.prototype.
jg-faustus
3

Korzystanie z Underscore.js (biblioteka dla funkcjonalnego JS)

>>> var foo = [1,2,3]
>>> var bar = [1,2,4]
>>> _.difference(foo, bar);
[4]
chribsen
źródło
3

Kilka prostych funkcji, zapożyczonych z odpowiedzi @ milan:

const setDifference = (a, b) => new Set([...a].filter(x => !b.has(x)));
const setIntersection = (a, b) => new Set([...a].filter(x => b.has(x)));
const setUnion = (a, b) => new Set([...a, ...b]);

Stosowanie:

const a = new Set([1, 2]);
const b = new Set([2, 3]);

setDifference(a, b); // Set { 1 }
setIntersection(a, b); // Set { 2 }
setUnion(a, b); // Set { 1, 2, 3 }
Brian Burns
źródło
2

Jeśli chodzi o sposób na czczo, nie jest to zbyt eleganckie, ale dla pewności przeprowadziłem kilka testów. Ładowanie jednej tablicy jako obiektu jest znacznie szybsze w przetwarzaniu w dużych ilościach:

var t, a, b, c, objA;

    // Fill some arrays to compare
a = Array(30000).fill(0).map(function(v,i) {
    return i.toFixed();
});
b = Array(20000).fill(0).map(function(v,i) {
    return (i*2).toFixed();
});

    // Simple indexOf inside filter
t = Date.now();
c = b.filter(function(v) { return a.indexOf(v) < 0; });
console.log('completed indexOf in %j ms with result %j length', Date.now() - t, c.length);

    // Load `a` as Object `A` first to avoid indexOf in filter
t = Date.now();
objA = {};
a.forEach(function(v) { objA[v] = true; });
c = b.filter(function(v) { return !objA[v]; });
console.log('completed Object in %j ms with result %j length', Date.now() - t, c.length);

Wyniki:

completed indexOf in 1219 ms with result 5000 length
completed Object in 8 ms with result 5000 length

Jednak działa to tylko w przypadku ciągów . Jeśli planujesz porównać ponumerowane zestawy, będziesz chciał mapować wyniki za pomocą parseFloat .

SmujMaiku
źródło
1
Czy nie powinno to być c = b.filter(function(v) { return !A[v]; });w drugiej funkcji?
fabianmoronzirfas
Masz rację. Jakoś wydaje mi się, że jest jeszcze szybszy
SmujMaiku
1

To działa, ale myślę, że inny jest znacznie krótszy i też elegancki

A = [1, 'a', 'b', 12];
B = ['a', 3, 4, 'b'];

diff_set = {
    ar : {},
    diff : Array(),
    remove_set : function(a) { ar = a; return this; },
    remove: function (el) {
        if(ar.indexOf(el)<0) this.diff.push(el);
    }
}

A.forEach(diff_set.remove_set(B).remove,diff_set);
C = diff_set.diff;
Xavi Ivars
źródło