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 . $\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 . $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 . $n$ $\mathcal{O}(n)$

W efekcie masz „idealną” implementację skrótu, która dla sekwencji operacji wykorzystuje przestrzeń , ale działa w czasie ! $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?

data-structures arrays

— Aryabhata
źródło

@Aryabhata Jakie jest odniesienie wspomniane?

— uli

„korzystanie z pamięci” nie jest tym samym, co „przydzielanie pamięci, ale nigdy do niej nie uzyskiwano”, dlatego myślę, że motywujący „paradoks” nie istnieje całkiem.

— Raphael

Myślę, że pierwszy akapit jest dość jasny: mieć wartość domyślną, bez faktycznego zajmowania czasu na wypełnienie tablicy wartością domyślną. Odpowiedź, na wypadek, gdyby ktoś miał czas na napisanie tego przed mną, znajduje się tutaj scholar.google.co.uk/... Na moim blogu znajduje się również krótkie wyjaśnienie rgrig.blogspot.co.uk/2008/12/array -puzzle-solution.html

— rgrig

@uli: To jest zalążkowe pytanie, właściwie czytam to już dawno temu.

— Aryabhata,

@Raphael: Nadal zaskakuje Cię, gdy słyszysz o takiej rzeczy za pierwszym razem. Większość paradoksów to :-)

— Aryabhata,

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 , i o rozmiarze każdy. Wykorzystamy je do wykonania operacji wymaganych przez naszą strukturę danych. Mamy również utrzymywać zmienną . 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ę . Tablice i działają jako certyfikaty, które pozwalają stwierdzić, czy dana pozycja w została zainicjowana. $A$ $set$ $V$ $P$ $A$

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

— zotachidil
źródło

P [V [i]]

$P[V[i]]$

i

$i$

A [i]

$A[i]$

Jest, ale wtedy pozycja będzie mniejsza niż V [i], prawda? Bo inaczej nie byłoby przypadkiem. Ponieważ posiadając pos wyższe niż V [i], oznacza to, że konkretnie ustawiliśmy wartość P przy indeksie V [i] na wybraną przez nas konkretną wartość, mianowicie i.

— wolfdawn

Zauważ, że jest to klasyczny przykład czegoś, czego nie można zrobić w (przenośnym) C.

— TLW