Zapisywanie przy inicjalizacji tablicy

Niedawno przeczytałem, że można mieć tablice, które nie muszą być inicjowane, tzn. Można z nich korzystać bez konieczności poświęcania czasu na ustawianie wartości domyślnej dla każdego elementu. tzn. możesz zacząć używać tablicy tak, jakby została ona zainicjowana wartością domyślną, bez konieczności jej inicjowania. (Przepraszam, nie pamiętam, gdzie to przeczytałem).

Na przykład, dlaczego może to być zaskakujące:

Załóżmy, że próbujesz wymodelować najgorszy przypadek hashtable (dla każdego wstawiania / usuwania / wyszukiwania) liczb całkowitych z zakresu .[ 1 , n 2$\mathcal{O}(1)$$[1, n^2]$

Możesz przydzielić tablicę o rozmiarze bitów i użyć pojedynczych bitów do przedstawienia istnienia liczby całkowitej w tablicy mieszającej. Uwaga: przydzielanie pamięci jest traktowane jako czas .O ( 1 $n^2$$\mathcal{O}(1)$

Teraz, jeśli wcale nie musiałeś inicjować tej tablicy, każda kolejna operacja powiedzenia na tej tablicy hasht jest teraz najgorszym przypadkiem .O ( n $n$$\mathcal{O}(n)$

W efekcie masz „idealną” implementację skrótu, która dla sekwencji operacji wykorzystuje przestrzeń , ale działa w czasie !Θ ( n 2 ) O ( n $n$$\Theta(n^2)$$\mathcal{O}(n)$

Zwykle można oczekiwać, że środowisko wykonawcze będzie co najmniej tak samo złe, jak wykorzystanie miejsca!

Uwaga: Powyższy przykład może być wykorzystany do implementacji rzadkiego zestawu lub rzadkiej macierzy, więc przypuszczam, że nie jest to tylko przedmiot teoretyczny.

Pytanie brzmi:

Jak można mieć strukturę podobną do tablicy, która pozwala nam pominąć krok inicjalizacji?

Jest to bardzo ogólna sztuczka, której można użyć do innych celów niż mieszanie. Poniżej podaję implementację (w pseudo-kodzie).

Niech trzy niezainicjowane wektory , P i V o rozmiarze n każdy. Wykorzystamy je do wykonania operacji wymaganych przez naszą strukturę danych. Mamy również utrzymywać zmienną p o, s . Operacje są realizowane w następujący sposób:$A$$P$$V$$n$$pos$

init:
  pos <- 0

set(i,x):
if not(V[i] < pos and P[V[i]] = i) 
  V[i] <- pos, P[pos] <- i, pos <- pos + 1
A[i] <- x

get(i):
if (V[i] < pos and P[V[i]] = i) 
  return A[i] 
else 
  return empty 

Tablica po prostu przechowuje wartości, które są przekazywane przez procedurę s e t . Tablice V i P działają jako certyfikaty, które pozwalają stwierdzić, czy dana pozycja w A została zainicjowana.$A$$set$$V$$P$$A$

Zauważ, że w każdym momencie inicjowane są elementy w od 0 do p o s - 1 . Możemy zatem bezpiecznie korzystać z tych wartości jako certyfikat dla zainicjowanych wartości w A . Dla każdej inicjowanej pozycji i w A znajduje się odpowiadający element w wektorze P, którego wartość jest równa i . Wskazuje na to V [ i ] . Dlatego jeśli spojrzymy na odpowiedni element, P [ V [ i ] ] i jego wartość to $P$$0$$pos-1$$A$$i$$A$$P$$i$$V[i]$$P[V[i]]$$i$wiemy, że zostało zainicjowane (ponieważ P nigdy nie kłamie, ponieważ wszystkie rozważane elementy są inicjowane). Podobnie, jeśli A [ i ] nie zostanie zainicjowane, wówczas V [ i ] może wskazywać albo pozycję w P poza zakresem 0 .. p o s - 1 , gdy wiemy na pewno, że nie jest zainicjowana, lub może wskazywać pozycja w tym zakresie. Ale ten konkretny P [ j ] odpowiada innej pozycji w A , a zatem$A[i]$$P$$A[i]$$V[i]$$P$$0..pos-1$$P[j]$$A$ , więc wiemy, że A [ i ] nie zostało zainicjowane.$P[j] \neq i$$A[i]$

Łatwo zauważyć, że wszystkie te operacje są wykonywane w stałym czasie. Również zastosowana przestrzeń to dla każdego z wektorów i O ( 1 ) dla zmiennej p o, a zatem łącznie O ( n ) .$O(n)$$O(1)$$pos$$O(n)$