Ustaw strukturę danych w celu wydajnego powtarzania wstawień

Szukam struktury danych zajmującej mało miejsca, która przechowuje zestawy (bez powtórzeń) elementów wordize i obsługuje szybkie wstawianie (amortyzowane O (1)). Przez „oszczędny przestrzennie” rozumiem idealnie, słów do przechowywania elementów. $n + o(n)$ $n$

Bycie zestawem jest ważną częścią pytania: jeśli każdy element zostanie dodany, razy wykorzystana przestrzeń nie może być . $\log n$ $n\log n$

Struktura powinna również wspierać wyliczanie jej elementów (rozsądnie i skutecznie); każda zdrowa struktura nie powinna mieć tutaj problemów. (Szybkie zapytania o członkostwo to plus.)

ds.data-structures

— Charles
źródło

Czy istnieje powód, dla którego tablica haszująca nie zadziała?

— Dave

@Dave: Nie uważam tego za spełnienie wymagań dotyczących miejsca, ale przypuszczam, że wystarczająco ścisły harmonogram dynamicznej zmiany rozmiaru mógłby sprawić, że zadziała. Ale ogólnie chciałbym zobaczyć, co tam jest, zanim zacznę pisać kod.

— Charles,

Aby uzyskać amortyzację

z dynamicznym zmienianiem rozmiaru, musisz zwiększyć rozmiar o stały ułamek, co nie wydaje mi się, że spełnia wymagania dotyczące miejsca, jeśli chcesz ściśle spełnić

O (1)

$O(1)$

n + o (n)

$n+o(n)$

— Dave

O (1)

$O(1)$

@Magnus: Wydaje mi się, że oznacza to, że rzeczywiste funkcje stojące za notacjami O i O w pytaniu nie zależą od wielkości słowa.

— Tsuyoshi Ito

Odpowiedzi:

Myślę, że „Zwięzłe słowniki dynamiczne i drzewa” Ramana i Rao spełniają określone przez ciebie granice. Z streszczenia:

$S \subseteq U = \{0, \dots , m − 1\}, |S| = n$ $O(1)$ $S$ $O(1)$ $B + o(B)$ $B = \lceil lg \binom{m}{n} \rceil$ $S$

— jbapple
źródło

To wygląda fantastycznie. (Zrozumiesz, jeśli przeczytam gazetę przed zaakceptowaniem, prawda?)

— Charles

Jeśli twoja aplikacja może tolerować fałszywe alarmy, powinieneś rozważyć użycie filtra Bloom .

Parafraza Wikipedii: Filtr Blooma to zajmująca mało miejsca probabilistyczna struktura danych, która służy do testowania, czy element należy do zbioru. Fałszywie pozytywne są możliwe, ale fałszywe negatywne nie są. Elementy można dodawać do zestawu, ale nie można ich usuwać. Im więcej elementów zostanie dodanych do zbioru, tym większe prawdopodobieństwo fałszywych trafień.

— Tyson Williams
źródło

Mój nie może, ale daje +1 za świetną strukturę danych.

— Charles