Wydajna struktura danych obsługująca wstawianie, usuwanie i większość częstotliwości

Załóżmy, że mamy zestaw a każdy element jest parą danych i kluczy. Chcemy struktury danych, która obsługiwałaby następujące operacje:$D$$D$

• Wstaw do ,$(d,k)$$D$
• Usuń członka , (nie trzeba szukać, aby znaleźć , np. wskazuje na członka w ),$e$$e$$e$$D$
• MostFrequent, który zwraca element członkowski dzięki czemu jest jednym z najczęstszych kluczy w (należy pamiętać, że najczęściej używany klucz nie musi być unikalny).$e \in D$$e.key$$D$

Jaka byłaby efektywna implementacja tej struktury danych?

Moim rozwiązaniem jest sterta kluczy i ich częstotliwości, dla których priorytetem są częstotliwości oraz tabela skrótów, w której funkcja skrótu odwzorowuje elementy z tym samym kluczem do tego samego miejsca w tablicy skrótów (ze wskaźnikami od każdej części do drugiej).

Może to dać dla pierwszych dwóch operacji i dla trzeciego (najgorszy czas działania).$\Theta(\lg n)$$\Theta(1)$

Zastanawiam się, czy istnieje bardziej wydajne rozwiązanie? (lub prostsze rozwiązanie o tej samej wydajności?)

W modelu obliczeń opartym na porównaniu można zaimplementować kolejkę priorytetową za pomocą sterty Fibonacciego zamiast zwykłej sterty. To da ci następujące granice: zamortyzowany czas wstawiania i zamortyzowany czas operacji usuwania.$\mathcal{O}(1)$$\mathcal{O}(\log n)$

Jeśli odejdziesz od modelu opartego na porównaniu i przyjmiesz model pamięci RAM, w którym klucze są traktowane jako ciągi binarne, z których każdy zawiera jedno lub więcej słów maszynowych, możesz zaimplementować swoją kolejkę priorytetową w . Rzeczywiście, możesz osiągnąć zarówno operacje wstawiania, jak i usuwania i czas na operację findMin. Thorup to udowodnił$o(\log n)$$\mathcal{O}(\sqrt{\log \log n})$$\mathcal{O}(1)$

Jeśli potrafimy posortować kluczy według czasu według klucza, możemy zaimplementować kolejkę priorytetową obsługującą find-min w stałym czasie oraz aktualizacje (wstawianie i usuwanie) w czasie .$n$$S(n)$$S(n)$

Zobacz M. Thorup. Równoważność między kolejkami priorytetowymi a sortowaniem, 2002. w Proc. FOCS 2002

Ponieważ możemy sortować w oczekiwany czas i przestrzeń liniową, jak pokazano za pomocą$\mathcal{O}(n \sqrt{\log \log n})$

Y. Han i M. Thorup. Sortowanie liczb całkowitych w oczekiwany czas i przestrzeń liniowa. w Proc. FOCS 2002$\mathcal{O}(n \sqrt{\log \log n})$

granica jest udowodniona.

Możesz to zrobić w oczekiwanym zamortyzowanym czasie. Podstawową sztuczką jest to, że nie potrzebujemy pełnej mocy kolejki priorytetowej, ponieważ częstotliwość klawiszy zmienia się tylko o 1 podczas każdego wstawiania lub usuwania.$O(1)$

Moje rozwiązanie poniżej to tak naprawdę twoje rozwiązanie z „nieefektywną” kolejką priorytetową, która akurat działa dobrze w tym przypadku: kolejka maksimum priorytetu zaimplementowana jako podwójnie połączone listy segmentów kluczy ma O (1) insertMin, deleteMax, removeFromBucket i wzrostKlucz.

Zachowaj podwójnie połączoną listę segmentów, gdzie każdy segment ma niepusty zestaw kluczy mieszających (które nazywam kohortą) i dodatnią liczbę całkowitą (które nazywam ValCount). W segmencie b każdy klucz k w kohorcie b ma taką samą liczbę unikalnych wartości związanych z nim w zestawie, który utrzymujesz. Na przykład, jeśli twój zestaw zawiera pary (a, jabłko), (a, awokado), (b, banan), (c, ogórek), (d, owoc smoka), gdzie pojedyncze litery to klucze, a owoce to wartości, wtedy miałbyś dwa Wiadra: Jeden Wiadro miałby ValCount 2 i Kohortę składającą się tylko z jednego klucza: a. Drugi segment miałby wartość ValCount równą 1 i kohortę złożoną z trzech kluczy b, c i d.

ValCount powinna przechowywać uporządkowaną podwójnie listę Bucket. Ważne będzie, abyśmy mogli znaleźć głowę i ogon listy w czasie i abyśmy mogli podzielić na nowy segment Wiadra w czasie jeśli znamy jego sąsiadów. Niewyobrażalnie nazywam listę Buckets listą BucketList.$O(1)$$O(1)$

Oprócz BucketList potrzebujemy SetMap, który jest kluczem mapującym mapę skrótów do ValueBuckets. ValueBucket to para składająca się z ValueSet (niepustego zestawu wartości skrótu) i niepustego wskaźnika do segmentu. ValueSet powiązany z kluczem k zawiera wszystkie unikalne wartości związane z k. Wskaźnik segmentu skojarzony z ValueSet ma kohortę równą wielkości ValueSet. Wiadro powiązane z kluczem k w SetMap jest również powiązane z kluczem k w BucketList.

W C ++:

struct Bucket {
    unsigned ValCount;
    unordered_set<Key> Cohort;
    Bucket * heavier;
    Bucket * lighter;
};
Bucket * BucketListHead;
Bucket * BucketListTail;

struct ValueBucket {
  unordered_set<Value> ValueSet;
  Bucket * bucket;
};
unordered_map<Key, ValueBucket> SetMap;

Aby znaleźć parę klucz-wartość o maksymalnej częstotliwości, wystarczy spojrzeć na nagłówek BucketList, znaleźć klucz w kohorcie, wyszukać ten klucz w SetMap i znaleźć wartość w ValueSet jego ValueBucket. (uff!)

Wstawianie i usuwanie par klucz-wartość jest trudniejsze.

Aby wstawić lub usunąć parę klucz-wartość, najpierw wstawiamy lub usuwamy ją w SetMap. Spowoduje to zmianę rozmiaru ValueSet, dlatego musimy zmodyfikować segment powiązany z kluczem. Jedynymi wiadrami, na które musimy spojrzeć, aby dokonać tej zmiany, będą najbliżsi sąsiedzi wiadra, w którym kiedyś był klucz. Jest tu kilka przypadków i prawdopodobnie nie warto ich w pełni opisywać, chociaż byłbym szczęśliwy rozwinąć, jeśli nadal masz problemy.

Złożoność najgorszego przypadku

$\mathcal{O}(1)$

$\mathcal{O}(1)$

$\mathcal{O}(1)$

$\mathcal{O}(\log \log n)$

$\mathcal{O}(n)$

Dowód

$[0 , N )$ $\mathrm{\mathcal{O}(log\ log\ min \{n, N\})}$

Który ustalono za pomocą kombinacji:

$\tau(n, N)$ $n$$[0 , N)$ $\tau ( n, N ) \le τ ( N, N)$$\tau$

i:

$n$$[0 , N)$$\mathrm{\mathcal{O}(1 + log\ log\ n − log\ log\ q)}$$q$

Odniesienie

Thorup, Mikkel. „Kolejki całkowite z malejącym kluczem w stałym czasie i problem z najkrótszymi ścieżkami z jednego źródła”. W materiałach z trzydziestego piątego dorocznego sympozjum ACM na temat teorii obliczeń, 149–158. STOC '03. Nowy Jork, NY, USA: ACM, 2003.