Dynamiczne doskonałe mieszanie

W informatyce dynamiczne doskonałe mieszanie jest techniką programistyczną służącą do rozwiązywania kolizji w strukturze danych tablicy skrótów . Technika ta, choć ^{zapytania , wstawić i usunąć duży zestaw elementów. wymaga} więcej pamięci niż jej odpowiedniki z tablicą skrótów, jest przydatna w sytuacjach, w których należy wykonać szybkie

Detale

Sprawa statyczna

Schemat FKS

Problem optymalnego mieszania statycznego został po raz pierwszy ogólnie rozwiązany przez Fredmana, Komlósa i Szemerédiego. W swoim artykule z 1984 roku szczegółowo opisują dwupoziomowy schemat tablicy mieszającej, w którym każdy segment tablicy mieszającej (pierwszego poziomu) odpowiada oddzielnej tabeli mieszającej drugiego poziomu. Klucze są haszowane dwukrotnie — pierwsza wartość skrótu jest odwzorowywana na określony segment w tabeli skrótów pierwszego poziomu; druga wartość skrótu podaje pozycję tego wpisu w tabeli skrótów drugiego poziomu tego zasobnika. Gwarantuje się, że tabela drugiego poziomu będzie wolna od kolizji (tj. doskonałego haszowania ) po zbudowaniu. W konsekwencji gwarantowany jest koszt wyszukiwania na poziomie O(1) w najgorszym przypadku .

W przypadku statycznym otrzymujemy z wyprzedzeniem zestaw zawierający w sumie $x wpisów, z których każdy ma unikalny klucz.$ Fredman, Komlós i Szemerédi wybierają tabelę skrótów pierwszego poziomu z wiaderkami o rozmiarze ${\ Displaystyle s = 2 (x-1)}$ .

Aby skonstruować, $x$ wpisów jest rozdzielanych na $s$ segmentów przez funkcję haszującą najwyższego poziomu, gdzie ${\ Displaystyle s = 2 (x-1)}$ . $,$ dla każdego zasobnika z $k$ wpisami przydzielana jest tabela drugiego poziomu ze a jej funkcja skrótu jest wybierana losowo z uniwersalnego zestawu funkcji skrótu , tak aby była bezkolizyjna (tj. doskonała funkcja skrótu ) i przechowywana obok tablicy skrótów. Jeśli losowo wybrana funkcja mieszająca tworzy tabelę z kolizjami, nowa funkcja mieszająca jest wybierana losowo, dopóki nie będzie można zagwarantować bezkolizyjnej tabeli. Wreszcie, przy bezkolizyjnym mieszaniu, $k$ wpisów jest mieszanych w tabeli drugiego poziomu.

Kwadratowy rozmiar przestrzeni zapewnia, że losowe tworzenie tabeli z kolizjami $jest$ i niezależne od rozmiaru $k$ zapewniając liniowy zamortyzowany czas budowy. Chociaż każda tabela drugiego poziomu wymaga przestrzeni $,$ skrótów pierwszego poziomu są rozmieszczone , struktura jako całość zajmuje oczekiwaną ponieważ rozmiary wiader są małe z dużym prawdopodobieństwem .

Funkcja skrótu pierwszego poziomu jest specjalnie dobrana tak, aby dla określonego zestawu $x$ unikalnych wartości kluczy całkowita przestrzeń $T$ używana przez wszystkie tabele skrótów drugiego poziomu oczekiwała miejsca ${\ displaystyle O (n)}$ , a dokładniej ${\ Displaystyle T <s + 4 \ cdot x}$ . Fredman, Komlós i Szemerédi wykazali, że biorąc pod uwagę uniwersalną rodzinę funkcji mieszających, co najmniej połowa z tych funkcji ma tę właściwość.

Przypadek dynamiczny

Dietzfelbinger i in. przedstawić algorytm dynamicznego słownika $, gdy zestaw n elementów$ dodawany przyrostowo do słownika, zapytania o członkostwo zawsze działają w stałym czasie, a zatem w najgorszym przypadku całkowity wymagany O $O (n)} ($ ${ \$ liniowy i oczekiwany zamortyzowany czas wstawiania i usuwania ( stały czas

W dynamicznym przypadku, gdy klucz jest wstawiany do tablicy skrótów, jeśli jego wpis w odpowiedniej podtabeli jest zajęty, wówczas mówi się, że zachodzi kolizja i podtabela jest odbudowywana na podstawie nowej całkowitej liczby wpisów i losowo wybranej funkcji skrótu. Ponieważ współczynnik obciążenia tabeli drugiego poziomu jest utrzymywany na niskim poziomie $}$ rzadka, a oczekiwany zamortyzowany koszt wstawiania wynosi ${\ Displaystyle O (1)$ . Podobnie, zamortyzowany oczekiwany koszt usunięcia wynosi ${\ Displaystyle O (1)}$ .

Ponadto ostateczne rozmiary tabeli najwyższego poziomu lub którejkolwiek z podtabel są niepoznawalne w przypadku dynamicznym. Jedną z metod zachowania oczekiwanej $i$ w tabeli jest wywołanie pełnej rekonstrukcji, gdy nastąpi wystarczająca liczba Zgodnie z wynikami Dietzfelbingera i in., o ile całkowita liczba wstawień lub usunięć przekracza liczbę elementów w czasie ostatniej konstrukcji, zamortyzowany oczekiwany koszt wstawiania i usuwania pozostaje O ( 1 ) { $1 )}$ z uwzględnieniem pełnego ponownego mieszania.

Implementacja dynamicznego doskonałego mieszania przez Dietzfelbingera i in. używa tych koncepcji, a także leniwego usuwania i jest pokazany w pseudokodzie poniżej.

Implementacja pseudokodu

Znajdź

    
     
        
 funkcja  Locate(  x  )  to  j  := h(  x  )  jeśli  (pozycja h _j (  x  ) podtabeli  T _j zawiera  x  (nie usunięte))  return  (  x  jest w  S  )  koniec jeśli  inaczej  return  (  x  nie jest w  S  )  koniec inny  koniec

Wstawić

Podczas wstawiania nowego wpisu x w punkcie j następuje zwiększenie globalnego licznika operacji count .

Jeśli x istnieje w j , ale jest oznaczone jako usunięte, to znak jest usuwany.

Jeśli x istnieje w j lub odbudowywana _w podtabeli Tj i nie _mieszającą hj _jest oznaczone jako usunięte, to mówi się, że zachodzi kolizja, a tabela drugiego poziomu Tj zasobnika j ^jest z inną losowo wybraną funkcją .

    
    
        
        
        
            
                 
                         
                
            
            
                 
                         
                
                
            
        
    
 funkcja  Insert(  x  )  to  liczba  =  liczba  + 1;  if  (  count  >  M  ) FullRehash(  x  );  koniec jeśli  jeszcze  j  = h(  x  );  if  (Pozycja h _j (x) podtabeli  T _j zawiera  x  )  if  (  x  jest zaznaczone jako usunięte) usuń znacznik usuwania;  koniec, jeśli  koniec, jeśli  inaczej  b _j =  b _j + 1;  if  (  b _j <=  m _j )  jeśli  pozycja h _j (  x  ) z  T _j jest pusta przechowuj  x  na pozycji h _j (  x  ) z  T _j ;  end if  else  Umieść wszystkie niezaznaczone elementy  T _j na liście  L _j ; Dołącz   x  do listy  L _j ;  b _j = długość  L _j ;  powtórz  h _j = losowo wybrana funkcja w  H _sj ;  dopóki  h _j nie jest iniekcyjne na elementach  L _j ;  dla  wszystkich  y  na liście  L _j zapisz  y  na pozycji h _j (  y  ) z  T _j ;  koniec dla  końca else  koniec, jeśli  jeszcze  m _j = 2 * max{1,  m _j };  s _jot = 2 *  m _jot * (  m _jot - 1);  jeśli  suma wszystkich s _j ≤ 32 *  M ² /  s  (  M  ) + 4 *  M  Przydziel  s _j komórek dla  T _j ; Umieść wszystkie niezaznaczone elementy   T _j na liście  L _j ; Dołącz   x  do listy  L _j ;  b _j = długość  L _j ;  powtórz  h _j = losowo wybrana funkcja w  H _sj ;  dopóki  h _j nie jest iniekcyjne na elementach  L _j ;  dla  wszystkich  y  na liście  L _j zapisz  y  na pozycji h _j (  y  ) z  T _j ;  koniec za  koniec, jeśli  jeszcze  FullRehash(  x  );  koniec inny  koniec inny  koniec inny  koniec inny  koniec

Usuwać

Usunięcie x oznacza po prostu flagę x jako usuniętą bez usuwania i zwiększa liczbę przyrostów . W przypadku zarówno wstawiania, jak i usuwania, jeśli liczba osiągnie próg M , cała tablica jest odbudowywana, gdzie M jest pewną stałą wielokrotnością rozmiaru S na początku nowej fazy . Tutaj faza odnosi się do czasu między pełnymi przebudowami. Zauważ, że tutaj -1 w „Delete( x )” jest reprezentacją elementu, który nie znajduje się w zbiorze wszystkich możliwych elementów U .

    
     
        
    
 funkcja  Usuń(  x  )  to  liczba  =  liczba  + 1;  j  = godz(  x  );  jeżeli  pozycja h _j (  x  ) podtabeli  Tj  zawiera  x  oznaczamy  x  jako usunięte;  zakończ, jeśli  w przeciwnym razie  wróć  (x nie jest członkiem S);  koniec else  if  (  count  >=  M  ) FullRehash(-1);  koniec, jeśli  koniec

Pełna przebudowa

Pełne przebudowanie tablicy S rozpoczyna się najpierw od usunięcia wszystkich elementów oznaczonych jako usunięte, a następnie ustawienia następnej wartości progowej M na pewną stałą wielokrotność rozmiaru S . Funkcja mieszająca, która dzieli S na podzbiory s ( M ), gdzie rozmiar podzbioru j wynosi s _j , jest wybierana losowo, dopóki:

${\ Displaystyle \ suma _ {0 \ równoważnik j \ równoważnik s (M)} s_ {j} \ równoważnik {\ Frac {32M ^ {2}} {s (M)}} + 4M.}$

Wreszcie, dla każdej podtabeli Tj _Tj funkcja _, mieszająca hj _hj jest _{wstrzyknięta} wielokrotnie losowo wybierana spośród Hsj _aż zostanie na elementy . Oczekiwany czas pełnej przebudowy tablicy S o rozmiarze n to O( n ).

    
    
     
             
    
 funkcja  FullRehash(  x  )  to  Umieść wszystkie niezaznaczone elementy  T  na liście  L  ;  jeśli  (  x  jest w  U  ) dołącz  x  do  L  ;  koniec if  liczba  = długość listy  L  ;  M  = (1 +  do  ) * max {  liczba  , 4};  powtórz  h = losowo wybrana funkcja w  Hs _(M) ;  dla  wszystkich  j  <  s  (  M  ) utwórz listę  L _j dla h (  x  ) =  j  ;  b _j = długość  L _j ;  m _jot = 2 *  b _jot ;  s _jot = 2 *  m _jot * (  m _jot - 1);  koniec  aż  suma wszystkich s _j ≤ 32 *  M ² /  s  (  M  ) + 4 *  M  dla  wszystkich  j  <  s  (  M  ) Przydziel miejsce  s _j dla podtabeli  T _j ;  powtórz  h _j = losowo wybrana funkcja w  H _sj ;  dopóki  h _j nie jest iniekcyjne na elementach listy  L _j ;  koniec dla  wszystkich  x  na  liście  L _j przechowuj  x  na pozycji h _j (  x  ) z  T _j ;  koniec za  koniec

Zobacz też

Idealne haszowanie