Speichern bei Array-Initialisierung

19

Ich habe kürzlich gelesen, dass es möglich ist, Arrays zu haben, die nicht initialisiert werden müssen, dh, es ist möglich, sie zu verwenden, ohne Zeit aufwenden zu müssen, um jedes Mitglied auf den Standardwert zu setzen. Das heißt, Sie können das Array so verwenden, als ob es mit dem Standardwert initialisiert worden wäre, ohne es initialisieren zu müssen. (Entschuldigung, ich kann mich nicht erinnern, wo ich das gelesen habe).

Zum Beispiel, warum das überraschend sein kann:

Angenommen, Sie versuchen, einen Worst- Case zu modellieren O(1) -Hashtabelle für den(für jede Einfügung / Löschung / Suche) von Ganzzahlen im Bereich.[1,n2]

Sie können ein Array mit einer Größe von Bits zuweisen und einzelne Bits verwenden, um die Existenz einer Ganzzahl in der Hashtabelle darzustellen. Hinweis: Das Zuweisen von Speicher wird als -Zeit betrachtet.n2O(1)

Wenn Sie dieses Array überhaupt nicht initialisieren mussten, ist jetzt eine beliebige Folge von Operationen für diese Hashtabelle der ungünstigste Fall .nO(n)

Tatsächlich haben Sie also eine "perfekte" Hash-Implementierung, die für eine Folge von Operationen den Raum verwendet, aber in der Zeit wird!nΘ(n2)O(n)

Normalerweise würde man erwarten, dass Ihre Laufzeit mindestens so schlecht ist wie Ihr Platzbedarf!

Hinweis: Das obige Beispiel könnte für die Implementierung einer Gruppe mit geringer Dichte oder einer Matrix mit geringer Dichte verwendet werden, daher ist es vermutlich nicht nur von theoretischem Interesse.

Die Frage ist also:

Wie ist es möglich, eine Array-ähnliche Datenstruktur zu haben, die es uns ermöglicht, den Initialisierungsschritt zu überspringen?

Aryabhata
quelle
@Aryabhata Was ist die Referenz, die Sie erwähnt haben?
uli
1
"Verwenden von Speicher" ist nicht dasselbe wie "Zuweisen von Speicher, aber Zugreifen auf Speicher", daher glaube ich, dass das motivierende "Paradoxon" nicht ganz existiert.
Raphael
1
Ich denke, der erste Absatz ist ziemlich klar: haben Sie einen Standardwert, ohne tatsächlich Zeit zu nehmen, um das Array mit dem Standardwert zu füllen. Die Antwort, falls jemand anderes Zeit hat, es zu schreiben, bevor ich es tue, ist hier. Scholar.google.co.uk/… Auf meinem Blog rgrig.blogspot.co.uk/2008/12/array
Rgrig
@uli: Dies ist eine Seeding-Frage, die ich eigentlich schon vor langer Zeit gelesen habe .
Aryabhata
@Raphael: Es ist immer noch überraschend, wenn man so etwas zum ersten Mal hört. Die meisten Paradoxe sind nicht :-)
Aryabhata

Antworten:

15

Dies ist ein sehr allgemeiner Trick, der für andere Zwecke als für das Hashing verwendet werden kann. Unten gebe ich eine Implementierung (in Pseudocode).

Es seien drei nicht initialisierte Vektoren , P und V der Größe n . Wir werden diese verwenden, um die von unserer Datenstruktur angeforderten Operationen durchzuführen. Wir halten auch eine Variable p o s . Die Operationen werden wie folgt implementiert:APVnpos

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 

Das Array speichert einfach die Werte , die durch die übergeben werden , s e t - Verfahren. Die Arrays V und P funktionieren als Zertifikate, die anzeigen, ob eine bestimmte Position in A initialisiert wurde.AsetVPA

Beachten Sie, dass die Elemente in jedem Augenblick im Bereich von 0 bis p o s - 1 initialisiert werden. Wir können diese Werte daher sicher als Zertifikat für die initialisierten Werte in A verwenden . Für jede Position i in A , die initialisiert wird, gibt es ein entsprechendes Element im Vektor P, dessen Wert gleich i ist . Dies wird durch V [ i ] gezeigt . Betrachten wir also das entsprechende Element, so ist P [ V [ i ] ] und sein Wert iP0pos1AiAPiV[i]P[V[i]]i, wir wissen, dass initialisiert wurde (da P niemals lügt, weil alle Elemente, die wir betrachten, initialisiert sind). In ähnlicher Weise kann, wenn A [ i ] nicht initialisiert ist, V [ i ] entweder auf eine Position in P außerhalb des Bereichs 0 ... p o s - 1 zeigen , wenn wir sicher sind, dass es nicht initialisiert ist, oder auf eine Position in diesem Bereich. Aber dieses besondere P [ j ] entspricht einer anderen Position in A und daherA[i]PA[i]V[i]P0..pos1P[j]A , daher wissen wir, dass A [ i ] nicht initialisiert wurde.P[j]iA[i]

Es ist leicht zu erkennen, dass all diese Vorgänge in konstanter Zeit ausgeführt werden. Außerdem verwendet der Raum ist für jeden der Vektoren und O ( 1 ) für die Variable p o s , also O ( n ) insgesamt.O(n)O(1)posO(n)

zotachidil
quelle
P[V[ich]]ichEIN[ich]
Es ist aber dann wird pos kleiner sein als V [i], nicht wahr? Denn sonst wäre es kein Zufall. Da pos höher als V [i] ist, bedeutet dies, dass wir den Wert von P am Index V [i] spezifisch auf einen spezifischen Wert eingestellt haben, den wir gewählt haben, nämlich i.
Wolfdawn
Beachten Sie, dass dies ein klassisches Beispiel für etwas ist, das in (portablem) C.
TLW