Wie setze ich ein Array in O (1) auf Null?

Ja

Allerdings kein Array. Es benötigt ein Array, das dafür erstellt wurde.

Das Prinzip ist einfach:

• Wir definieren eine Epoche mit dem Attribut generation
• Wenn ein Element festgelegt ist, wird die Epoche, in der es festgelegt wurde, aufgezeichnet
• nur Elemente der aktuellen Epoche können gesehen werden
• clearing entspricht also dem Inkrementieren des epoch counters

Die Methode hat zwei Probleme:

• Speichererhöhung: Für jeden Artikel speichern wir eine Epoche
• generation counter overflow: Es gibt etwas wie eine maximale Anzahl von Epochen

Letzteres kann mit einer echten großen Ganzzahl ( uint64_t auf Kosten von mehr Speicher) verhindert werden.

Ersteres ist eine natürliche Konsequenz, eine mögliche Lösung besteht darin, Buckets zu verwenden, um das Problem herunterzuspielen, indem zum Beispiel bis zu 64 Elemente einem einzelnen Zähler zugeordnet sind und eine Bitmaske identifiziert, die innerhalb dieses Zählers gültig ist.

BEARBEITEN : Ich wollte nur auf die Eimer-Idee zurückkommen.

Die ursprüngliche Lösung hat einen Overhead von 8 Bytes (64 Bits) pro Element (wenn bereits 8 Bytes ausgerichtet sind). Abhängig von den gespeicherten Elementen kann dies eine große Rolle spielen.

Wenn es eine große Sache ist, ist die Idee, Eimer zu verwenden; Wie alle Kompromisse verlangsamt es natürlich den Zugang noch mehr.

Beachten Sie, dass dieses kleine Array mit einer festen Anzahl von Elementen (wir könnten es tatsächlich erstellen und statisch überprüfen, ob es kleiner oder gleich 64 ist) nur 16 Byte Overhead hat. Dies bedeutet, dass wir einen Overhead von 2 Bits pro Element haben.

Wir haben den Speicherplatz-Overhead um einen Faktor von ... 32 reduziert. Nun kann das Array sogar zum Speichern von char verwendet werden, während es zuvor noch unerschwinglich gewesen wäre. Die Kosten sind, dass der Zugriff langsamer wird, da wir eine Division und modulo bekommen (wenn wir eine standardisierte Operation bekommen, die beide Ergebnisse auf einmal zurückgibt?).

Sie können n Speicherorte im Speicher nicht in weniger als O(n) ändern (auch wenn Ihre Hardware, für ausreichend kleine n , möglicherweise eine konstante Zeitoperation erlaubt, bestimmte gut ausgerichtete Speicherblöcke auf Null zu setzen, wie zum Beispiel Flash-Speicher).

Wenn jedoch das Objekt der Übung ein wenig laterales Denken ist, dann können Sie eine Klasse schreiben, die ein "spärliches" Array darstellt. Die allgemeine Idee eines Sparse-Arrays ist, dass Sie eine Sammlung behalten (vielleicht ein map , obwohl abhängig von der Verwendung, die möglicherweise nicht alles ist) und wenn Sie einen Index nachschlagen, wenn er nicht in der zugrunde liegenden Sammlung ist dann gibst du 0 zurück.

Wenn Sie die zugrunde liegende Sammlung in O (1) löschen können, können Sie Ihr Sparse-Array in O (1) auf Null setzen. Das Löschen einer std::map ist normalerweise keine konstante Zeit in der Größe der Map, da alle diese Knoten freigegeben werden müssen. Sie könnten jedoch eine Sammlung erstellen, die in O(1) gelöscht werden kann, indem Sie den gesamten Baum von "den Inhalten meiner Map" zu "einer Baumstruktur von Knoten, die ich für die zukünftige Verwendung reserviert habe" verschieben. Der Nachteil wäre nur, dass dieser "reservierte" Platz immer noch reserviert ist, ein bisschen wie das, wenn ein vector kleiner wird.

Es ist sicherlich möglich, ein Array in O (1) auf Null zu setzen, solange Sie einen sehr großen konstanten Faktor akzeptieren:

Dies wird immer die gleiche Anzahl von Schritten dauern, unabhängig von der Größe des Arrays, daher ist es O (1).

Nein.

Sie können nicht jedes Mitglied einer N-Element-Sammlung in weniger als O (N) Zeit besuchen.

Sie könnten, wie Mike Kwan bemerkt hat, die Kosten von der Laufzeit zur Kompilierzeit verschieben, aber das ändert nichts an der Komplexität der Rechenoperation.

Es ist natürlich nicht möglich, ein Array beliebiger Größe in einer festen Zeitlänge zu initialisieren. Es ist jedoch durchaus möglich, einen arrayähnlichen ADT zu erstellen, der die Kosten für die Initialisierung des Arrays über seine Verwendung hinweg amortisiert. Die übliche Konstruktion dafür nimmt jedoch das 3-fache des Speichers ein. Zu Whit:

Man könnte ein clear() -Member hinzufügen, um den Inhalt eines solchen Arrays relativ einfach zu leeren, wenn T ein Typ ist, der zumindest im Konzept keine Zerstörung erfordert.

Es ist zur Laufzeit nicht möglich, ein Array in O(1) auf Null zu setzen. Dies ist intuitiv, da es keinen Sprachmechanismus gibt, der die Werteinstellung von Speicherblöcken beliebiger Größe in einer festen Zeit erlaubt. Der nächste, den Sie tun können, ist:

Damit kann die Initialisierung bei der Kompilierung erfolgen. Zur Laufzeit ist memset normalerweise am schnellsten, wäre aber O(N) . Es gibt jedoch Probleme , die mit der Verwendung verbunden sind memset für bestimmte Array-Typen.

Während noch O (N) ist, können Implementierungen, die hardwaregestützten Operationen wie dem Löschen ganzer Cachezeilen oder Speicherseiten zugeordnet sind, bei & lt; 1 Zyklus pro Wort laufen.

Sie können es tun, wenn Sie Hardware-Unterstützung haben, um beliebig viele Speicher gleichzeitig zu löschen. Setzen Sie ein beliebig großes Array, dann können Sie auch einen beliebig großen Speicher mit Hardware-Parallelität setzen, so dass ein einzelner Reset-Pin gleichzeitig jedes Register auf einmal löscht. Diese Leitung muss von einem beliebig großen Logikgatter angesteuert werden (das beliebig große Leistung ableitet), und die Leiterbahnen müssen willkürlich kurz sein (um die R / C-Verzögerung zu überwinden) (oder supraleitend), aber diese Dinge sind durchaus üblich in extradimensionalen Räumen.