Różnica między zestawami obliczeniowymi między dwoma dużymi zestawami

Mam dwóch dużych zestawów liczb całkowitych i B . Każdy zestaw ma około miliona wpisów, a każdy wpis jest dodatnią liczbą całkowitą o długości co najwyżej 10 cyfr. $A$$B$

Jaki jest najlepszy algorytm do obliczania i B ∖ A ? Innymi słowy, jak mogę skutecznie obliczyć listę pozycji A , które nie są w B i odwrotnie? Jaka byłaby najlepsza struktura danych reprezentująca te dwa zestawy, aby te operacje były wydajne?$A\setminus B$$B\setminus A$$A$$B$

Najlepszym podejściem, jakie mogę wymyślić, jest przechowywanie tych dwóch zestawów jako posortowanych list i porównywanie każdego elementu z każdym elementem B w sposób liniowy. Czy możemy zrobić lepiej?$A$$B$

Jeśli chcesz przechowywać zestawy w specjalnej strukturze danych, możesz uzyskać ciekawe komplikacje.

Niech $I=\mathcal O\left(\min\left(|A|,|B|,|A\Delta B|\right)\right)$

Następnie możesz ustawić operacje i A Δ B , każda w O ( I ⋅ log | A | + | B $A\cup B, A\cap B,A\setminus B$$A\Delta B$oczekiwany czas. Zasadniczo otrzymujesz minimalny rozmiar dwóch zestawów lub rozmiar różnicy symetrycznej, w zależności od tego, która jest mniejsza. Jest to lepsze niż liniowe, jeśli różnica symetryczna jest niewielka; to znaczy. jeśli mają duże skrzyżowanie. W rzeczywistości dla dwóch żądanych operacji ustawiania różnicy jest to praktycznie zależne od wyników, ponieważ razem stanowią one wielkość różnicy symetrycznej.$\mathcal O\left(I\cdot\log\frac{|A|+|B|}{I}\right)$

Aby uzyskać więcej informacji, zobacz Zestawy i mapy o trwałej spójności autorstwa Olle Liljenzin (2013).

Skan liniowy jest najlepszym, co wiem, jak to zrobić, jeśli zestawy są reprezentowane jako posortowane listy połączone. Czas działania to .$O(|A| + |B|)$

Zauważ, że nie musisz porównywać każdego elementu z każdym elementem B , parami. Prowadziłoby to do czasu wykonania O ( | A | × | B | ) , co jest znacznie gorsze. Zamiast tego, aby obliczyć różnicę symetryczną tych dwóch zestawów, można użyć techniki podobnej do operacji „scalania” w trybie scalania, odpowiednio zmodyfikowanej w celu pominięcia wartości wspólnych dla obu zestawów.$A$$B$$O(|A| \times |B|)$

Bardziej szczegółowo, możesz zbudować algorytm rekurencyjny, taki jak poniżej, aby obliczyć , zakładając, że A i B są reprezentowane jako listy połączone z ich wartościami w uporządkowanej kolejności:$A \setminus B$$A$$B$

difference(A, B):
    if len(B)=0:
        return A # return the leftover list
    if len(A)=0:
        return B # return the leftover list
    if A[0] < B[0]:
        return [A[0]] + difference(A[1:], B)
    elsif A[0] = B[0]:
        return difference(A[1:], B[1:])  # omit the common element
    else:
        return [B[0]] + difference(A, B[1:])

Reprezentowałem to w pseudo-Pythonie. Jeśli nie czytasz Pythona, A[0]jest on głową połączonej listy A, A[1:]jest resztą listy i +reprezentuje konkatenację list. Ze względu na wydajność, jeśli pracujesz w Pythonie, prawdopodobnie nie chciałbyś go wdrożyć dokładnie tak, jak powyżej - na przykład lepiej byłoby użyć generatorów, aby uniknąć tworzenia wielu list tymczasowych - ale chciałem pokażę Ci pomysły w najprostszej możliwej formie. Celem tego pseudokodu jest jedynie zilustrowanie algorytmu, a nie zaproponowanie konkretnej implementacji.

Nie sądzę, aby można było zrobić coś lepszego, jeśli twoje zbiory są reprezentowane jako listy posortowane i chcesz, aby dane wyjściowe były dostarczane jako lista posortowana. Ci zasadniczo trzeba patrzeć na każdy element i B . Nieformalny szkic uzasadnienia: jeśli istnieje jakikolwiek element, którego nie obejrzałeś, nie możesz go wydrukować, więc jedynym przypadkiem, w którym możesz pominąć patrzenie na element, jest to, że wiesz, że jest on obecny zarówno w A, jak i B , ale skąd możesz wiedzieć, że jest obecny, jeśli nie spojrzałeś na jego wartość?$A$$B$$A$$B$

Jeśli A i B są równej wielkości, rozłączne i przeplatane (np. Liczby nieparzyste w A i liczby parzyste w B), to porównanie par elementów w czasie liniowym jest prawdopodobnie optymalne.

Jeśli A i B zawierają bloki elementów, które znajdują się dokładnie w jednym z A lub B, lub w obu, można obliczyć ustawioną różnicę, sumę i przecięcie w czasie subliniowym. Na przykład, jeśli A i B różnią się dokładnie jednym przedmiotem, różnicę można obliczyć w O (log n).

http://arxiv.org/abs/1301.3388

$n$$A-B$$a \wedge \overline b$$a,b$