Poszukuję zestawu implementacji o małym rozmiarze pamięci

Szukam implementacji ustawionego typu danych. To znaczy musimy

utrzymywać dynamiczny podzbiór $S$ (wielkościowy $n$ ) z wszechświata wielkości z $U = \{0, 1, 2, 3, \dots , u – 1\}$ $u$
operacje insert(x)(dodaj element xdo $S$ ) i find(x)(sprawdza, czy element xjest członkiem $S$ ).

Nie dbam o inne operacje. Dla orientacji, w aplikacjach, z którymi pracuję mamy $u \approx 10^{10}$ .

Znam implementacje, które zapewniają obie operacje w czasie $O(1)$ , więc martwię się głównie o wielkość struktury danych. Oczekuję miliardów wpisów, ale chcę uniknąć wymiany w jak największym stopniu.

W razie potrzeby jestem gotów poświęcić środowisko wykonawcze. Mogę przyznać, że amortyzowane środowisko wykonawcze $O(\log n)$ ; oczekiwane środowiska wykonawcze lub środowiska uruchomieniowe w $\omega(\log n)$ są niedopuszczalne.

Jednym z moich pomysłów jest to, że jeśli $S$ może być reprezentowane jako połączenie zakresów [xmin, xmax], będziemy mogli zaoszczędzić na wielkości pamięci masowej przy cenie spadku wydajności. Możliwe są również inne wzorce danych, takie jak [0, 2, 4, 6].

Czy możesz wskazać mi struktury danych, które mogą zrobić coś takiego?

— HEKTO
źródło

niech nam kontynuować tę dyskusję w czacie

— Raphael

Jak liczba elementów wchodzi w obraz? To znaczy, co się stanie, jeśli element zostanie wstawiony, a jest już ?

n

$n$

n

$n$

— vonbrand

@vonbrand - nrozmiar zestawu S. Może się zwiększać z każdym insertlub może pozostać taki sam, jeśli element xjest już w zestawie.

— HEKTO

Czy możesz zaakceptować małe prawdopodobieństwo fałszywych trafień? Jeśli tak, filtr Bloom może być idealny: en.wikipedia.org/wiki/Bloom_filter

— Joe

@AlekseyYakovlev, fałszywie dodatni współczynnik filtru Blooma nie ma nic wspólnego z rozmiarem wszechświata (tylko z liczbą funkcji skrótu , rozmiarem struktury danych i liczbą elementów ), ale jeśli naprawdę jest blisko (powiedzmy dla małej stałej ), ciężko będzie ci zrobić coś lepszego niż prosty wektor bitowy, jak sądzę, z całkowitą ilością bitów .

k

$k$

m

$m$

n

$n$

n

$n$

u

$u$

u = n \cdot c

$u = n\cdot c$

c

$c$

c n

$cn$

— Joe

Odpowiedzi:

Odpowiedź Joe jest bardzo dobra i zawiera wszystkie ważne słowa kluczowe.

Należy pamiętać, że zwięzłe badania struktury danych są wciąż na wczesnym etapie, a wiele wyników jest w dużej mierze teoretycznych. Wiele proponowanych struktur danych jest dość skomplikowanych do wdrożenia, ale większość złożoności wynika z faktu, że musisz zachować asymptotyczną złożoność zarówno w odniesieniu do wielkości wszechświata, jak i liczby przechowywanych elementów. Jeśli którykolwiek z nich jest względnie stały, wówczas znaczna część złożoności zanika.

Jeśli kolekcja jest półstatyczna (to znaczy wstawki są rzadkie lub co najmniej niewielkie), to z pewnością warto rozważyć łatwą do wdrożenia statyczną strukturę danych (sdarray Sadakane'a jest dobrym wyborem) w połączeniu z aktualizacją Pamięć podręczna. Zasadniczo rejestrujesz aktualizacje w tradycyjnej strukturze danych (np. B-drzewo, trie, tablica skrótu) i okresowo aktualizujesz zbiorczo „główną” strukturę danych. Jest to bardzo popularna technika wyszukiwania informacji, ponieważ indeksy odwrócone mają wiele zalet wyszukiwania, ale trudno je zaktualizować w miejscu. Jeśli tak jest, proszę dać mi znać w komentarzu, a ja poprawię tę odpowiedź, aby podać kilka wskazówek.

Jeśli wstawki są częstsze, sugeruję zwięzłe haszowanie. Podstawowy pomysł jest wystarczająco prosty, aby wyjaśnić tutaj, więc zrobię to.

Tak więc podstawowe informacje teoretyczne Powoduje to, że jeśli jesteś przechowywania elementów z uniwersum elementów i nie ma innych informacji (np brak korelacji między elementami), a następnie Need You bity do przechowywania. (Wszystkie logarytmy są oparte na podstawie 2, chyba że podano inaczej). Potrzebujesz tak wielu bitów. Nie można tego obejść. $n$ $u$ $\log {u \choose n} + O(1)$

Teraz trochę terminologii:

Jeśli masz strukturę danych, która może przechowywać dane i wspierać twoje operacje w bitach przestrzeni, nazywamy to niejawną strukturą danych. $\log {u \choose n} + O(1)$
Jeśli masz strukturę danych, która może przechowywać dane i wspierać twoje operacje w bitów przestrzeni, nazywamy to zwartą strukturą danych. Należy zauważyć, że w praktyce oznacza to, że względny narzut (w stosunku do teoretycznego minimum) mieści się w stałej. Może to być 5% narzutu, 10% narzutu lub 10 razy narzutu. $\log {u \choose n} + O(\log {u \choose n}) = (1 + O(1)) \log {u \choose n}$
Jeśli masz strukturę danych, która może przechowywać dane i wspierać twoje operacje w bitów przestrzeni, nazywamy to zwięzłą strukturą danych. $\log {u \choose n} + o(\log {u \choose n}) = (1 + o(1)) \log {u \choose n}$

Różnica między zwięzłą a zwartą polega na różnicy między małą a dużą. Ignorując przez chwilę rzecz o wartości bezwzględnej ...

$g(n) = O(f(n))$ oznacza, że istnieje stała i liczba taka, że dla wszystkich , . $c$ $n_0$ $n > n_0$ $g(n) < c \cdot f(n)$
$g(n) = o(f(n))$ oznacza, że dla wszystkich stałych istnieje liczba taka, że dla wszystkich , . $c$ $n_0$ $n > n_0$ $g(n) < c \cdot f(n)$

Nieoficjalnie, zarówno duże, jak i małe, są „w ramach stałego współczynnika”, ale w przypadku dużego „o” stała jest wybierana dla ciebie (przez projektanta algorytmu, producenta procesora, prawa fizyki itp.), Ale z niewielkim -oh sam wybierasz stałą i może być tak mała, jak chcesz . Innymi słowy, w zwięzłych strukturach danych względny narzut staje się arbitralnie mały wraz ze wzrostem wielkości problemu.

Oczywiście rozmiar problemu może być ogromny, aby zrozumieć względny narzut, jaki chcesz, ale nie możesz mieć wszystkiego.

OK, mając to pod naszymi paskami, podajmy numery problemu. Załóżmy, że klucze są bitowymi liczbami całkowitymi (więc rozmiar wszechświata wynosi ), i chcemy przechowywać tych liczb całkowitych. Załóżmy, że możemy magicznie zaaranżować wyidealizowany stół haszujący z pełnym obłożeniem i bez strat, tak że potrzebujemy dokładnie szczelin. $n$ $2^n$ $2^m$ $2^m$

Operacja wyszukiwania spowoduje haszowanie klawisza bit, maskowanie bitów, aby znaleźć gniazda haszowania, a następnie sprawdzenie, czy wartość w tabeli pasuje do klucza. Na razie w porządku. $n$ $m$

Taka tablica skrótów wykorzystuje bitów. Czy możemy to zrobić lepiej? $n 2^m$

Załóżmy, że funkcja skrótu jest odwracalna. Wówczas nie musimy przechowywać całego klucza w każdym polu mieszania. Lokalizacja szczeliny mieszającej daje bitów wartości skrótu, więc jeśli zachowałeś tylko pozostałe bity , możesz zrekonstruować klucz z tych dwóch informacji (lokalizacja szczeliny skrótu i przechowywana tam wartość). Tak więc potrzebujesz tylko bitów pamięci. $h$ $m$ $n-m$ $(n - m) 2^m$

Jeśli jest małe w porównaniu z , przybliżenie Stirlinga i mała arytmetyka (dowód to ćwiczenie!) Ujawniają, że: $2^m$ $2^n$

(n - m) 2^{m} = \log (\binom{2^{n}}{2^{m}}) + o (\log (\binom{2^{n}}{2^{m}}))

$(n - m) 2^m = \log {2^n \choose 2^m} + o\left(\log {2^n \choose 2^m}\right)$

Tak więc ta struktura danych jest zwięzła.

Istnieją jednak dwa połowy.

Pierwszym haczykiem jest zbudowanie „dobrych” odwracalnych funkcji skrótu. Na szczęście jest to o wiele łatwiejsze niż się wydaje; kryptografowie cały czas tworzą funkcje odwracalne, tylko nazywają je „szyframi”. Możesz na przykład oprzeć funkcję skrótu na sieci Feistel, która jest prostym sposobem na zbudowanie odwracalnych funkcji skrótu na podstawie nieodwracalnych funkcji skrótu.

Drugi haczyk polega na tym, że prawdziwe tabele skrótów nie są idealne dzięki paradoksowi urodzin. Więc chcesz użyć bardziej wyrafinowanego typu tabeli mieszającej, która zbliży Cię do pełnego obłożenia bez rozlewania. Mieszanie kukułki jest do tego idealne, ponieważ pozwala ci dowolnie zbliżyć się do ideału w teorii i całkiem blisko w praktyce.

Mieszanie kukułki wymaga wielu funkcji skrótu i wymaga, aby wartości w gniazdach mieszania były oznaczone przy użyciu funkcji skrótu. Na przykład, jeśli używasz czterech funkcji skrótu, musisz przechowywać dodatkowe dwa bity w każdym gnieździe skrótu. Jest to nadal zwięzłe, gdy rośnie, więc nie jest to problemem w praktyce i wciąż przewyższa przechowywanie całych kluczy. $m$

Och, możesz też chcieć spojrzeć na drzewa van Emde Boasa.

WIĘCEJ MYŚLI

Jeśli jest gdzieś w pobliżu , to to w przybliżeniu , więc (jeszcze raz) zakładając, że nie ma dalszej korelacji między wartościami, w zasadzie nie możesz nic zrobić lepszy niż nieco wektor. Zauważysz, że powyższe rozwiązanie haszujące skutecznie degeneruje się w tym przypadku (kończy się to zapisywaniem jednego bitu na szczelinę haszującą), ale taniej jest po prostu użyć klucza jako adresu niż funkcji haszującej. $n$ $\frac{u}{2}$ $\log {u \choose n }$ $u$

Jeśli jest bardzo bliskie , cała zwięzła literatura na temat struktur danych zaleca odwrócenie sensu słownika. Przechowuj wartości, które nie występują w zestawie. Jednak teraz musisz skutecznie wspierać operację usuwania i aby zachować zwięzłe zachowanie, musisz także być w stanie zmniejszyć strukturę danych w miarę dodawania kolejnych elementów. Rozszerzanie tabeli skrótów jest dobrze zrozumiałą operacją, ale jej nie jest. $n$ $u$

— Pseudonim
źródło

Cześć, co do drugiego akapitu twojej odpowiedzi - spodziewam się, że każdemu wezwaniu insertbędzie towarzyszyć wezwanie do findz tym samym argumentem. Więc jeśli findzwroty true, po prostu pomijamy insert. Tak więc częstotliwość findpołączeń jest większa niż częstotliwość insertpołączeń, również gdy nzbliża się u, wtedy insertpołączenia stają się bardzo rzadkie.

— HEKTO

Ale można się spodziewać zbliżyć się do ostatecznie?

u

$u$

n

$n$

— pseudonim

W prawdziwym świecie n rośnie aż do ciebie, jednak nie możemy przewidzieć, czy to się stanie, czy nie. Struktura danych powinna działać dobrze dla każdegon <= u

— HEKTO

Dobrze. Zatem można śmiało powiedzieć, że nie znamy żadnej struktury danych, która jest zwięzła (w powyższym znaczeniu) i która osiąga to w całym zakresie . Myślę, że będziesz potrzebować rzadkiej struktury danych, gdy , a następnie przełącz się na gęstą (np. Bitowy wektor), gdy jest w pobliżu , a następnie rzadką strukturę danych z odwróconą wyczuć, kiedy jest blisko .

\frac{n}{u}

$\frac{n}{u}$

n < u

$n < u$

n

$n$

\frac{u}{2}

$\frac{u}{2}$

n

$n$

u

$u$

— Pseudonim

Wygląda na to, że potrzebujesz zwięzłej struktury danych dla problemu dynamicznego członkostwa .

Przypomnijmy, że zwięzła struktura danych to taka, dla której zapotrzebowanie na miejsce jest „bliskie” teoretycznej dolnej granicy, ale w przeciwieństwie do skompresowanej struktury danych, nadal pozwala na wydajne zapytania.

Problemem członkostwa jest dokładnie to, co można opisać w swoim pytaniu:

utrzymuj podzbiór (o rozmiarze ) z wszechświata o rozmiarze pomocą operacji: $S$ $n$ $U = \{0, 1, 2, 3, \dots , u – 1\}$ $u$

find(x)(sprawdza, czy element xjest członkiem ). $S$
insert(x)(dodaj element xdo ) $S$
delete(x)(usuń element xz ) $S$

Jeśli findobsługiwana jest tylko operacja, jest to problem statycznego członkostwa. Jeżeli jedna insertlub deletesą obsługiwane, ale nie jednocześnie, nazywa się częściowo dynamiczne , a jeśli wszystkie trzy operacje są obsługiwane, to nazywa się dynamiczną problemem członków.

Technicznie rzecz biorąc, myślę, że poprosiłeś tylko o strukturę danych dla pół-dynamicznego problemu członkostwa, ale nie znam żadnych struktur danych, które wykorzystałyby to ograniczenie i spełniałyby twoje inne wymagania. Mam jednak następujące odniesienie:

W Twierdzeniu 5.1 artykułu Członkostwo w stałym czasie i prawie minimalnej przestrzeni Brodnik i Munro dają następujący wynik:

Istnieje struktura danych wymagająca bitów która obsługuje wyszukiwanie w stałym czasie oraz wstawianie i usuwanie w stałym oczekiwanym zamortyzowanym czasie. $O(B)$

gdzie to teoretyczna minimalna wymagana liczba bitów informacji. $B = \lceil \log {u \choose n} \rceil$

Podstawową ideą jest to, że rekurencyjnie dzielą wszechświat na zakres starannie dobranych rozmiarów, więc nawet brzmi to tak, jakby techniki mogły być zgodne z myślami.

Jeśli jednak szukasz czegoś, co rzeczywiście możesz wdrożyć, nie wiem, czy to będzie najlepszy wybór. Przejrzałem tylko gazetę, a próba wyjaśnienia szczegółów wykracza daleko poza zakres tej odpowiedzi. Sparametryzowali swoje rozwiązanie, stosując różne strategie w zależności od względnych rozmiarów i . A dynamiczna wersja struktury danych jest tylko naszkicowana na papierze. $u$ $n$

— Joe
źródło

Streszczenie papierowe Brodnik i Munro nie mówi nic o wkładkach. Ale ich rezultatów możemy się spodziewać, prawda? Jeśli n = u/2, to potrzebna przestrzeń jest maksymalna.

— HEKTO,

@AlekseyYakovlev W rzeczywistości nie wspominają o przypadku dynamicznym w streszczeniu, ale twierdzenie, które dotyczy przypadku dynamicznego jest cytowane w mojej odpowiedzi (z sekcji 5).

— Joe