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

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.

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

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}

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.

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>

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

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.

Korzystanie z Underscore.js (biblioteka dla funkcjonalnego JS)

>>> var foo = [1,2,3]
>>> var bar = [1,2,4]
>>> _.difference(foo, bar);
[4]

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 }

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 .

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;