Swap (Computerprogrammierung) - Swap (computer programming)
In der Computerprogrammierung , der Vorgang des Swapping zwei Variablen bezieht sich die Werte der Variablen gegenseitig ausgetauscht werden . Normalerweise geschieht dies mit den Daten im Speicher . Zum Beispiel können in einem Programm zwei Variablen so definiert werden (in Pseudocode ):
data_item x := 1 data_item y := 0 swap (x, y);
Nachdem swap() ausgeführt wurde, enthält x den Wert 0 und y enthält 1; ihre Werte wurden ausgetauscht. Dieser Vorgang kann auf andere Arten von Werten verallgemeinert werden, z. B. Zeichenfolgen und aggregierte Datentypen . Vergleichssortierungen verwenden Swaps, um die Positionen von Daten zu ändern.
In vielen Programmiersprachen ist die Swap- Funktion integriert. In C++ werden Überladungen bereitgestellt, die es std::swap ermöglichen, einige große Strukturen in O(1)-Zeit auszutauschen.
Verwenden einer temporären Variablen
Die einfachste und wahrscheinlich am weitesten verbreitete Methode, um zwei Variablen auszutauschen, besteht darin, eine dritte temporäre Variable zu verwenden :
define swap (x, y)
temp := x
x := y
y := temp
Obwohl dies konzeptionell einfach und in vielen Fällen die einzige bequeme Möglichkeit ist, zwei Variablen auszutauschen, wird zusätzlicher Speicher benötigt. Obwohl dies in den meisten Anwendungen kein Problem darstellen sollte, kann die Größe der auszutauschenden Werte sehr groß sein (was bedeutet, dass die temporäre Variable auch viel Speicher belegen kann) oder der Auslagerungsvorgang muss möglicherweise viele Male ausgeführt werden, da bei Sortieralgorithmen.
Darüber hinaus tauscht zwei Variablen in objektorientierten Sprachen wie C ++ kann einen Aufruf an den beinhalten Klasse Konstruktor und Destruktor für die temporäre Variable und drei Anrufe an den Kopierkonstruktor . Einige Klassen weisen möglicherweise Speicher im Konstruktor zu und geben ihn im Destruktor wieder frei, wodurch teure Aufrufe an das System erzeugt werden. Kopierkonstruktoren für Klassen, die viele Daten enthalten, zB in einem Array , müssen die Daten möglicherweise sogar manuell kopieren.
XOR-Swap
XOR-Swap verwendet die XOR- Operation, um zwei numerische Variablen auszutauschen. Es wird allgemein angepriesen, schneller zu sein als die oben erwähnte naive Methode; jedoch hat es Nachteile . XOR-Swap wird im Allgemeinen verwendet, um Low-Level-Datentypen wie Integer auszutauschen . Theoretisch ist es jedoch in der Lage, zwei beliebige Werte auszutauschen , die durch Bitfolgen fester Länge dargestellt werden können .
Vertauschen durch Addition und Subtraktion
Diese Methode vertauscht zwei Variablen, indem ihre Werte addiert und subtrahiert werden. Dies wird in praktischen Anwendungen selten verwendet, hauptsächlich weil:
- Es kann nur numerische Variablen austauschen; Es ist möglicherweise nicht möglich oder logisch, komplexe Datentypen wie Container hinzuzufügen oder zu entfernen .
- Beim Austausch von Variablen fester Größe wird ein arithmetischer Überlauf zum Problem.
- Es funktioniert im Allgemeinen nicht für Gleitkommawerte, da Gleitkommaarithmetik nicht assoziativ ist .
Behälter tauschen
Container, die unter Verwendung von Zeigern Speicher aus dem Heap zuweisen, können in einer einzigen Operation ausgetauscht werden, indem nur die Zeiger ausgetauscht werden. Dies findet man normalerweise in Programmiersprachen, die Zeiger unterstützen, wie C oder C++ . Die Standard Template Library überlädt ihre eingebaute Swap-Funktion, um auf diese Weise den Inhalt von Containern effizient auszutauschen.
Da Zeigervariablen normalerweise eine feste Größe haben (z. B. haben die meisten Desktop-Computer 64 Bit lange Zeiger ) und numerisch sind, können sie mit XOR swap schnell ausgetauscht werden .
Parallele Zuordnung
Einige Sprachen, wie Ruby oder Python, unterstützen parallele Zuweisungen , was die Notation für den Austausch zweier Variablen vereinfacht:
a, b = b, a
Dies ist eine Abkürzung für eine Operation, die eine Zwischendatenstruktur beinhaltet: in Python ein Tupel; in Ruby ein Array.
Javascript 6+ unterstützt Destrukturierungsoperatoren, die dasselbe tun:
[a, b] = [b, a];
Funktionstausch
Hier werden zwei Variablen mit globalem Gültigkeitsbereich nach Wert durch eine Funktion übergeben, wodurch die Notwendigkeit einer temporären Speichervariablen entfällt.
x = 1;
y = 2;
console.log(x + " " + y); // outputs 1 2
function swap(a, b) {
x = b;
y = a;
}
swap(x, y);
console.log(x + " " + y); // outputs 2 1
Erleichterung des Austauschs in modernen Computern
Dedizierte Anweisungen
Aufgrund der vielen Anwendungen des Austauschens von Daten in Computern bieten die meisten Prozessoren jetzt die Möglichkeit, Variablen direkt durch eingebaute Befehle auszutauschen. x86- Prozessoren enthalten beispielsweise einen XCHG- Befehl, um zwei Register direkt auszutauschen , ohne dass ein drittes temporäres Register verwendet werden muss. In einigen Prozessorarchitekturen ist sogar ein Vergleichs-und-Austausch- Befehl vorgesehen, der zwei Register vergleicht und bedingt tauscht. Dies wird verwendet, um Techniken des gegenseitigen Ausschlusses zu unterstützen .
XCHG ist möglicherweise nicht so effizient, wie es scheint. In x86- Prozessoren wird XCHG beispielsweise den Zugriff auf alle Operanden im Speicher implizit sperren, um sicherzustellen, dass die Operation atomar ist , und kann daher beim Auslagern des Speichers nicht effizient sein. Eine solche Sperrung ist wichtig, wenn sie verwendet wird, um eine threadsichere Synchronisation zu implementieren, wie in Mutexes . Ein XCHG ist jedoch normalerweise der schnellste Weg, um zwei maschinengroße Wörter, die sich in Registern befinden , auszutauschen . Das Umbenennen von Registern kann auch verwendet werden, um Register effizient auszutauschen.
Parallele Ausführung
Mit dem Aufkommen von Instruction Pipelining in modernen Computern und Mehrkernprozessoren, die paralleles Rechnen erleichtern , können zwei oder mehr Operationen gleichzeitig ausgeführt werden. Dies kann den Austausch mit temporären Variablen beschleunigen und ihm einen Vorteil gegenüber anderen Algorithmen verschaffen. Beispielsweise erfordert der XOR-Swap-Algorithmus die sequentielle Ausführung von drei Befehlen. Mit zwei temporären Registern können jedoch zwei parallel ausgeführte Prozessoren zwei Variablen in zwei Taktzyklen austauschen:
Step 1 Processor 1: temp_1 := X Processor 2: temp_2 := Y Step 2 Processor 1: X := temp_2 Processor 2: Y := temp_1
Dies verwendet weniger Anweisungen; es können jedoch andere temporäre Register verwendet werden, und es werden vier Befehle anstelle von drei benötigt. Dies ließe sich in der Praxis jedenfalls nicht in separaten Prozessoren realisieren, da es gegen Bernsteins Bedingungen für paralleles Rechnen verstößt. Es wäre unmöglich, die Prozessoren ausreichend synchron zu halten, damit dieser Austausch einen signifikanten Vorteil gegenüber herkömmlichen Versionen hätte. Es kann jedoch verwendet werden, um das Swapping für einen einzelnen Prozessor mit mehreren Lade-/Speichereinheiten zu optimieren.