Struktura danych dla skrzyżowania zestawu?

21

Czy jest jakaś struktura danych, która utrzymuje kolekcję zbioru (zbioru skończonego) obsługującą następujące operacje? Czy doceniony zostanie jakikolwiek podliniowy czas pracy?

Zainicjuj pusty zestaw.
Dodaj element do zestawu.
Biorąc pod uwagę dwa zestawy, zgłoś, czy się przecinają.

data-structures sets

— Dawei Huang
źródło

1

To jest bardzo ogólne pytanie, ponieważ każda struktura danych może obsługiwać te operacje ze skończoną domeną. Czy możesz być trochę bardziej szczegółowy? Na przykład. Jakiej złożoności potrzebujesz, co chcesz poświęcić, aby rozpocząć operacje itp.

— Bartosz Przybylski

13

Jeśli każdy zestaw zachowuje zapis istniejących zestawów i masz w sumie $s > 0$ zestawów, możesz łatwo przekształcić dowolną strukturę danych dla kolekcji ( np. Drzewa wyszukiwania binarnego itp. ) W jedną, w której możesz pobrać element przecięcia dwóch zbiorów w czasie $O(\log s)$ .

Każdy zestaw powinien mieć unikalny identyfikator z całkowicie uporządkowanego zestawu. Jeśli wyraźnie określisz swoje zestawy $S_1, S_2, \ldots$ identyfikatorem może być po prostu indeks.
Powinieneś wdrożyć „rejestr” zestawów; struktura danych, która utrzymuje kolekcję wszystkich zestawów, które zdefiniowałeś. Rejestr powinien zostać zaimplementowany jako struktura danych drzewa wyszukiwania, aby umożliwić łatwe wyszukiwanie ( np. Jeśli chcesz usunąć zestaw) i przechodzenie zestawów w czasie liniowym.
Każdy zestaw utrzymuje również „indeks” z każdym z pozostałych zestawów - nie kopiowanie z nich, ale raczej strukturę danych, która jest indeksowana przez etykietach innych zestawach. Wskaźnik ten zostanie wykorzystany do utrzymania, dla każdego zestawu , wyszukiwanie binarne drzewo wszystkich elementów $S_j$ $S_k$ . (Dwa zestawy i współużytkują jedną kopię tego drzewa wyszukiwania.) $S_j \cap S_k$ $S_j$ $S_k$

Inicjalizacja

Inicjalizacja zestawu składa się z operacje zainicjować drzewo jej elementów, operacje jak zainicjować (kopiowanie z rejestru) wskaźnik dla zbioru i podczas przechodzenia przez rejestr, aby dodać do indeksów każdego z pozostałych zestawów . W indeksie tworzymy drzewa wyszukiwania reprezentujące $T = \varnothing$ $O(1)$ $O(s)$ $T$ $O(s \log s)$ $T$ $S_j$ $T$ $T \cap S_j = \varnothing$ Dla innych zestawów ; kopiujemy ten sam wskaźnik dla indeksu . $S_j$ $S_j$

Dodanie elementu do zestawu $T$

Dodanie pewnej do zbioru zajmuje jak zwykle czas , gdzie . Testujemy również członkostwo w każdym innym zestawie , co zajmuje czas $x \in V$ $T$ $O(\log n_T)$ $n_T = |T|$ $x$ $S_1, S_2, \ldots$ gdzie

O (\log n_{S_{1}} + \log n_{S_{2}} + \dots) \subseteq O (s \log n),

$O(\log n_{S_1} + \log n_{S_2} + \cdots) \subseteq O(s \log n) ,$

n = | V |

$n = |V|$ jest wielkość wszechświata (lub największy zbiór

) i

oznacza liczbę zestawów w rejestrze. Dla każdego zestawu

takie, że

także wkładka

do indeksu do zbioru

. Dla każdego zestawu takiego

ma to

czasu, aby wyszukać

S_{j}

$S_j$

s

$s$

S_{j}

$S_j$

x \in S_{j}

$x \in S_j$

x

$x$

S_{j} \cap T

$S_j \cap T$

S_{j}

$S_j$

O (\log s + \log n_{T})

$O(\log s + \log n_T)$

S_{j}

$S_j$ indeks

i wstaw

w

; we wszystkich zestawach

T

$T$

x

$x$

S_{j} \cap T

$S_j \cap T$

S_{1}, S_{2}, \dots

$S_1, S_2, \ldots$ zajmuje to czas

. Jeśli założymy, że liczba zestawów

jest znacznie mniejszy niż rozmiar wszechświata

(to znaczy, jeżeli założymy,

) Całkowity czas wkładka jest wówczas

O (s \log s + s \log n_{T})

$O(s \log s + s \log n_T)$

S_{j}

$S_j$

V

$V$

s ≪ n

$s \ll n$

O (s \log n)

$O(s \log n)$ .

Jeśli nie dopuszczać duplikaty w zestawach, możemy zaoszczędzić czas w przypadku, gdy już o rezygnacji test członkostwa i wstawki dla innych zestawów . „Wstawienie” w przypadku, gdy jest już obecny, zajmuje tylko czas . $x \in S$ $T$ $x$ $O(\log n_T)$

Testowanie skrzyżowań

Indeks każdego zestawu jest utrzymywana właśnie w celu umożliwienia szybkiej oceny, czy dwa zestawy i przecinać. Przez zestaw , po prostu przez sprawdzenie jego indeks dla zestaw , nie możemy określić tylko w czasie czy przecina , ale możemy także pobierać binarne drzewo zawierającą cały zestaw . $S_j$ $S_k$ $S_j$ $S_k$ $O(\log s)$ $S_j$ $S_k$ $S_j \cap S_k$

Usuwanie elementu

Aby usunąć element ze zbioru , usuwamy go nie tylko z drzewa wyszukiwania samego , ale z każdego przecięcia dla zbiorów w jego indeksie. Wymaga to czasu , gdzie $x$ $T$ $T$ $S_j \cap T$ $S_j$ $O(s \log n_T)$ . $n_T = |T|$

Ustaw usuwanie

Ze względu na narzut związany z przeszukiwaniem rejestru, jeśli masz wiele zestawów, pożądane może być ich usunięcie, gdy nie będą już potrzebne. Przez przejeżdżające cały rejestr, możemy usuwania z wykaz wszystkich innych zestawów w czasie , zdominowany przez koszt usuwania drzewa wyszukiwania odpowiadający dla każdego z innych zestawów , gdzie . $S$ $S_j$ $O(sn_T)$ $S_j \cap T$ $S_j$ $n_T = |T|$

Uwagi

Jeśli spodziewasz się zaimplementować tylko stałą liczbę zestawów, powyższe czasy działania zmniejszają się do:

inicjalizacja: $O(1)$
wstawienie elementu: $O(\log n)$
testowanie skrzyżowania (i odzyskanie skrzyżowania): $O(1)$
usunięcie elementu: $O(\log n_T)$
usunięcie zestawu: $O(n_S)$

gdzie jest rozmiarem największego zestawu w rejestrze, a dla zestawu którym pracujesz. $n$ $n_T = |T|$ $T$

Jeśli spodziewasz się mieć zestawów , gdzie jest twoim wszechświatem, możesz potrzebować innej struktury danych, jeśli chcesz, aby operacje te działały w czasie sublinearnym. Jeśli jednak masz pary zestawów, o których przecięciu wiesz, że nigdy nie będziesz testować, możesz być w stanie zmniejszyć rozmiar indeksu dla tych zestawów (nie włączając żadnych zestawów, których przecięcie przetestujesz) lub użyć więcej niż jednego rejestru ( jeden dla każdej kolekcji zestawów, których przecięcie można przetestować). W rzeczywistości rejestr jest przydatny tylko wtedy, gdy chcesz scentralizowanej kontroli, aby upewnić się, że każda para zestawów ma zapisy w indeksie: w niektórych przypadkach może być praktyczne, przy inicjalizacji zestawu , po prostu rejestrować $O(|V|)$ $V$ $S$ ad hoc każdy nowy zestaw do indeksów innych zbiorów których przecięciem z jesteś zainteresowany. $T$ $S$

— Niel de Beaudrap
źródło

6

Istnieją struktury danych, które pozwalają to zrobić w czasie krótszym niż liniowy, nawet w przypadku najgorszych danych wejściowych. Zobacz http://research.microsoft.com/pubs/173795/vldb11intersection.pdf (i odnośniki do dokumentów w nim zawarte).

Jeśli twoje dwa zestawy S i T mają duże przecięcie i masz słownik dla S, wyszukiwanie elementów T w losowej kolejności powinno szybko dać ci wspólny element. Najtrudniejszy jest przypadek, gdy rozmiar przecięcia wynosi 0 lub 1.

— Rasmus Pagh
źródło

3

Zwykle wybrany język programowania obsługuje strukturę danych z unikalnymi elementami. Zasadniczo istnieją trzy popularne podejścia: drzewa, skróty i maski bitowe. Elementy drzewa muszą być porównywalne, elementy skrótu muszą być mieszalne, a elementy maski bitowej muszą mieć jakiś sposób konwersji na liczby całkowite.

Zestaw drzew będzie obsługiwał wstawianie do O (log n) i testowanie skrzyżowań w najgorszym przypadku O (n log n).

Zestaw skrótów będzie obsługiwał wstawianie do amortyzacji O (1 * h), gdzie „h” oznacza czas działania algorytmu haszującego, oraz test przecięcia w najgorszym przypadku O (n).

Zestawy bitmask zwykle nie są używane jak zestawy drzewiaste i mieszające.

— Karl Damgaard Asmussen
źródło

2

To byłaby przyzwoita odpowiedź na przepełnienie stosu , ale tutaj chcielibyśmy trochę szczegółów na temat tego, jak i dlaczego to działa.

— Raphael

3

Jeśli twoja sprawa pozwala na fałszywie pozytywne odpowiedzi, użyłbym filtra Bloom z pojedynczą funkcją skrótu.

Możesz to zaimplementować w następujący sposób:

Zainicjuj pusty zestaw

$B$ = tablica bitów $n$ bitów, wszystkie ustawione na 0. ( $n$ należy wybrać zgodnie z liczbą możliwych elementów)

Dodaj element do zestawu.

$B[hash(element)]=1$

Biorąc pod uwagę dwa zestawy (B1, B2), podaj, czy się przecinają.

sprawdź czy $B1$ $AND$ $B2$ $=$ $0$

Complexity

If $n$ is not too big, all operations are $O(1)$ .

— Grisha Weintraub
źródło