Niech A
i B
będą dwoma zbiorami. Szukam naprawdę szybkich lub eleganckich sposobów na obliczenie różnicy zestawów ( A - B
lub 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.
javascript
arrays
set-difference
Matt Ball
źródło
źródło
indexOf
implementacją.Odpowiedzi:
jeśli nie wiesz, czy to jest najskuteczniejsze, ale może najkrótsze
Zaktualizowano do ES6:
źródło
!B.includes(x)
zamiastB.indexOf(x) < 0
:)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ż windexOf
przypadku dużych tablic:źródło
Możesz użyć obiektu jako mapy, aby uniknąć liniowego skanowania
B
każdego elementu,A
jak w odpowiedzi użytkownika187291 :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ąctoSource()
wywołania.źródło
Najkrótsza, wykorzystująca jQuery, to:
źródło
not
nie działa już z obiektami ogólnymi od 3.0.0-rc1. Zobacz github.com/jquery/jquery/issues/3147Hashowałbym tablicę B, a następnie zachowałbym wartości z tablicy A nieobecne w B:
źródło
getDifference(a, b, hashOfB)
jeśli nie zostanie przekazane, zostanie obliczone, w przeciwnym razie zostanie ponownie użyte w takiej postaci, w jakiej jest.Uwzględniając pomysł Christopha i zakładając kilka niestandardowych metod iteracji na tablicach i obiektach / hashach (
each
i przyjaciołach), możemy uzyskać różnicę, sumę i przecięcie w czasie liniowym w sumie w około 20 liniach:Zakłada się, że
each
ifilter
są zdefiniowane dla tablic oraz że mamy dwie metody narzędziowe:myUtils.keys(hash)
: zwraca tablicę z kluczami z skrótumyUtils.select(hash, fnSelector, fnEvaluator)
: zwraca tablicę z wynikami wywołaniafnEvaluator
par klucz / wartość, dla którychfnSelector
zwraca prawdę.select()
Jest luźno inspirowany Common Lisp, a jest jedyniefilter()
imap()
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
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.
źródło
hasOwnProperty()
nawet jeśli elementy są numeryczne: w przeciwnym razie coś w rodzajuObject.prototype[42] = true;
średnich42
nie może nigdy wystąpić w zestawie wynikówKorzystanie z Underscore.js (biblioteka dla funkcjonalnego JS)
źródło
Kilka prostych funkcji, zapożyczonych z odpowiedzi @ milan:
Stosowanie:
źródło
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:
Wyniki:
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 .
źródło
b.filter(function(v) { return !A[v]; });
w drugiej funkcji?To działa, ale myślę, że inny jest znacznie krótszy i też elegancki
źródło