In-Place-Algorithmus - In-place algorithm
In der Informatik ist ein In-Place-Algorithmus ein Algorithmus, der Eingaben ohne zusätzliche Datenstruktur umwandelt . Für Hilfsvariablen ist jedoch ein geringer zusätzlicher Speicherplatz zulässig. Die Eingabe wird normalerweise während der Ausführung des Algorithmus von der Ausgabe überschrieben. Ein In-Place-Algorithmus aktualisiert seine Eingabesequenz nur durch Ersetzen oder Austauschen von Elementen. Ein Algorithmus, der nicht vorhanden ist, wird manchmal als nicht vorhanden oder nicht vorhanden bezeichnet .
In-Place kann leicht unterschiedliche Bedeutungen haben. In seiner strengsten Form kann der Algorithmus nur eine konstante Menge an zusätzlichem Speicherplatz haben und alles einschließlich Funktionsaufrufe und Zeiger zählen . Diese Form ist jedoch sehr eingeschränkt, da einfach ein Index für ein Array der Länge n O (log n ) Bits erfordert . Im weiteren Sinne bedeutet an Ort und Stelle, dass der Algorithmus keinen zusätzlichen Platz zum Manipulieren der Eingabe verwendet, aber möglicherweise einen kleinen, wenn auch nicht konstanten zusätzlichen Platz für seine Operation benötigt. Normalerweise ist dieses Leerzeichen O (log n ) , obwohl manchmal alles in O ( n ) erlaubt ist. Beachten Sie, dass die Platzkomplexität auch verschiedene Auswahlmöglichkeiten hat, ob die Indexlängen als Teil des verwendeten Platzes gezählt werden sollen oder nicht. Häufig wird die Raumkomplexität in Form der Anzahl der benötigten Indizes oder Zeiger angegeben, wobei deren Länge ignoriert wird. In diesem Artikel beziehen wir uns auf die Gesamtraumkomplexität ( DSPACE ) und zählen die Zeigerlängen. Daher hat der Platzbedarf hier einen zusätzlichen log n- Faktor im Vergleich zu einer Analyse, die die Länge von Indizes und Zeigern ignoriert.
Ein Algorithmus kann die Ausgabe als Teil seines Speicherplatzverbrauchs zählen oder nicht. Da In-Place-Algorithmen normalerweise ihre Eingabe mit der Ausgabe überschreiben, wird kein zusätzlicher Platz benötigt. Beim Schreiben der Ausgabe in einen Nur-Schreib-Speicher oder einen Stream kann es sinnvoller sein, nur den Arbeitsraum des Algorithmus zu berücksichtigen. In theoretischen Anwendungen wie Log-Space-Reduzierungen ist es üblicher, den Ausgabeplatz immer zu ignorieren (in diesen Fällen ist es wichtiger, dass die Ausgabe nur schreibgeschützt ist ).
Beispiele
Angenommen, ein Array a mit n Elementen soll ein Array haben, das die gleichen Elemente in umgekehrter Reihenfolge enthält und das Original entsorgt. Eine scheinbar einfache Möglichkeit, dies zu tun, besteht darin, ein neues Array gleicher Größe zu erstellen, es mit Kopien von ain der entsprechenden Reihenfolge zu füllen und dann zu löschen a.
function reverse(a[0..n - 1])
allocate b[0..n - 1]
for i from 0 to n - 1
b[n − 1 − i] := a[i]
return b
Leider erfordert dies O ( n ) zusätzlichen Platz, um die Arrays zu haben aund bgleichzeitig verfügbar zu sein. Außerdem sind Zuweisung und Aufhebung der Zuweisung oft langsame Vorgänge. Da wir nicht mehr benötigen a, können wir es stattdessen mit seiner eigenen Umkehrung mit diesem In-Place-Algorithmus überschreiben, der nur eine konstante Anzahl (2) von ganzen Zahlen für die Hilfsvariablen iund benötigt tmp, egal wie groß das Array ist.
function reverse_in_place(a[0..n-1])
for i from 0 to floor((n-2)/2)
tmp := a[i]
a[i] := a[n − 1 − i]
a[n − 1 − i] := tmp
Als weiteres Beispiel ordnen viele Sortieralgorithmen Arrays direkt in eine sortierte Reihenfolge um, darunter: bubble sort , comb sort , selection sort , insert sort , heapsort und Shell sort . Diese Algorithmen benötigen nur wenige Zeiger, daher beträgt ihre Raumkomplexität O (log n ) .
Quicksort arbeitet direkt mit den zu sortierenden Daten. Quicksort erfordert jedoch O (log n ) Stackspace-Zeiger, um die Subarrays in seiner Divide-and-Conquer- Strategie zu verfolgen . Folglich benötigt Quicksort O (log 2 n ) zusätzlichen Speicherplatz. Obwohl dieser nicht konstante Raum Quicksort technisch aus der In-Place-Kategorie entfernt, werden Quicksort und andere Algorithmen, die nur O (log n ) zusätzliche Zeiger benötigen, normalerweise als In-Place-Algorithmen betrachtet.
Die meisten Auswahlalgorithmen sind ebenfalls vorhanden, obwohl einige das Eingabearray erheblich neu anordnen, um das endgültige Ergebnis mit konstanter Größe zu finden.
Einige Textmanipulationsalgorithmen wie Trimmen und Reverse können an Ort und Stelle durchgeführt werden.
In rechnerischer Komplexität
In der Berechnungskomplexitätstheorie umfasst die strikte Definition von In-Place-Algorithmen alle Algorithmen mit O (1) Raumkomplexität, die Klasse DSPACE (1). Diese Klasse ist sehr begrenzt; es entspricht den regulären Sprachen . Tatsächlich enthält es nicht einmal eines der oben aufgeführten Beispiele.
Normalerweise betrachten wir Algorithmen in L , der Klasse von Problemen, die O (log n ) zusätzlichen Platz benötigen , als vorhanden. Diese Klasse entspricht eher der praktischen Definition, da sie Zahlen der Größe n als Zeiger oder Indizes zulässt . Diese erweiterte Definition schließt Quicksort jedoch aufgrund seiner rekursiven Aufrufe immer noch aus.
Die Identifizierung der In-Place-Algorithmen mit L hat einige interessante Implikationen; Zum Beispiel bedeutet dies, dass es einen (ziemlich komplexen) In-Place-Algorithmus gibt, um zu bestimmen, ob ein Pfad zwischen zwei Knoten in einem ungerichteten Graphen existiert , ein Problem, das O ( n ) zusätzlichen Platz benötigt, wenn typische Algorithmen wie die Tiefensuche verwendet werden (ein besuchtes Bit für jeden Knoten). Dies wiederum Ausbeuten in-place - Algorithmen für Probleme , wie beispielsweise Bestimmen , ob ein Graph ist bipartite oder testen , ob zwei Graphen haben die gleiche Anzahl von verbundenen Komponenten . Weitere Informationen finden Sie unter SL .
Rolle des Zufalls
In vielen Fällen kann der Platzbedarf eines Algorithmus drastisch reduziert werden, indem ein randomisierter Algorithmus verwendet wird . Angenommen, wir möchten wissen, ob zwei Knoten in einem Graphen von n Knoten in derselben Zusammenhangskomponente des Graphen liegen. Es gibt keinen bekannten einfachen, deterministischen In-Place-Algorithmus, um dies zu bestimmen, aber wenn wir einfach an einer Ecke beginnen und einen Random Walk von etwa 20 n 3 Schritten ausführen , besteht die Chance, dass wir über die andere Ecke stolpern, vorausgesetzt, es ist in der gleichen Komponente ist sehr hoch. In ähnlicher Weise gibt es einfache randomisierte In-Place-Algorithmen für Primalitätstests wie den Miller-Rabin-Primalitätstest , und es gibt auch einfache In-Place-Randomized-Faktorisierungsalgorithmen wie den Rho-Algorithmus von Pollard . Siehe RL und BPL für weitere Diskussionen zu diesem Phänomen.
In der funktionalen Programmierung
Funktionale Programmiersprachen raten häufig von expliziten In-Place-Algorithmen ab, die Daten überschreiben, oder unterstützen sie nicht, da dies eine Art Nebeneffekt ist ; stattdessen erlauben sie nur die Konstruktion neuer Daten. Gute Compiler für funktionale Sprachen erkennen jedoch oft, wenn ein Objekt erstellt wird, das einem bestehenden sehr ähnlich ist, und dann das alte weggeworfen wird, und optimieren dies zu einer einfachen Mutation "unter der Haube".
Beachten Sie, dass es im Prinzip möglich ist, In-Place-Algorithmen sorgfältig zu konstruieren, die Daten nicht verändern (es sei denn, die Daten werden nicht mehr verwendet), dies wird jedoch in der Praxis selten getan. Siehe rein funktionale Datenstrukturen .
Siehe auch
Verweise
- ^ Der Bitplatzbedarf eines Zeigers ist O (log n ) , aber die Zeigergröße kann in den meisten Sortieranwendungen als Konstante angesehen werden.
- ^ Maciej Liśkiewicz und Rüdiger Reischuk. Die Komplexitätswelt unter dem logarithmischen Raum . Structure in Complexity Theory Conference , S. 64-78. 1994. Online: p. 3, Satz 2.
- ^ Reingold, Omer (2008), "Ungerichtete Konnektivität im Log-Raum", Journal of the ACM , 55 (4): 1–24, doi : 10.1145/1391289.1391291 , MR 2445014 , ECCC TR04-094
