Ich bin neulich über einen Artikel gestolpert der erklärte, wie man in Programmen die Werte zweier Variablen vertauschen kann, ohne dazu eine extra Variable zur Zwischenspeicherung zu benötigen.

Ich habe in der Vergangenheit bereits über interessante, in der Numerik begründete Abkürzungen in Programmen und den Einfluss verschiedener Programmieransätze auf die Komplexität entstehenden Codes berichtet.

Daher hat mich diese Idee intereressiert. Die naive und intuitive Herangehensweise zum Tausch der Werte zweier Variablen a und b ist das bekannte

latch=a;
a=b;
b=latch;

Dazu benötigt man neben den zwei Variablen, deren Werte man tauschen möchte noch eine weitere als Zwischenspeicher. Möchte man die Nutzung einer solchen zusätzlichen Variable verhindern, kann man das erreichen - vorausgesetzt, die beiden Variablen enthalten ganzzahlige Werte und sind in der Lage, die Summe und die Differenz der beiden Werte abzubilden, ohne dass es zu einem numerischen Überlauf kommt. Dazu geht man wie folgt vor:

Setzt man ein erkennt man, dass der Tausch tatsächlich stattgefunden hat - zunächst 1 in 2:

Und nun mit 5 und 1 in 3:

Man sieht, dass die beiden Variablen a und b tatsächlich ihre Werte getauscht haben! Nachdem nun demonstriert wurde, dass es tatsächlich möglich ist - wie sinnvoll ist das? Abgesehen von der Tatsache, dass ich nur eine Notwendigkeit in der Maschinenprogrammierung sehe (Dort kann es ja vorkommen, dass manche Operationen nur auf bestimmte Register angewendet werden können und man daher Daten zwischen Registern austauschen muss), sehe ich in Hochsprachen dafür absolut keine Notwendigkeit mehr - was die ganze Sache in den Bereich des pur akademischen Interesses verlagert.

Darüber hinaus ist es so, dass die Rechenzeit dadurch nicht verringert wird, denn die Anzahl der Operationen ist immer noch dieselbe - und ob die verbrauchte Rechenzeit bei Load/Store-Instructions und bei Arithmetik-Instructions sich in aktuellen Prozessoren wirklich so sehr unterscheidet, möchte ich bezweifeln.

Dazu kommt noch, dass sich auf Maschinensprach-Ebene die beiden Varianten unter Umständen nicht mehr so sehr unterscheiden: Oft ist es ja so, dass Arithmetik mit einem Spezial-Register - dem sogenannten Akkumulator durchgeführt werden muss. Und in diesem Fall bräuchten wir wieder drei "Variablen": Die zwei Register, deren Inhalte getauscht werden sollen und den Akkumulator. Man hätte also in einer solchen Architektur nichts gewonnen. In einer Architektur mit echten General-Purpose-Registern wie der Motorola 68xxx-Serie würde die Einsparung tatsächlich wie theoretisch erklärt funktionieren - die entsprechenden Maschinenbefehle zum Tausch der Werte in den Registern d1 (a) und d2 (b) würden wie folgt aussehen:

	add	d2,d1
	sub	d2,d1
	sub d2,d1

Aber auch hier erkennt man: es werden genau wie beim Tausch mit Zwischenvariable drei Operationen gebraucht. Dazu kommt in dieser Architektur (wie wahrscheinlich in vielen anderen auch): Bedingt durch die Tatsache, dass manche Operationen nur auf bestimmten Registern funktionieren existiert ein dedizierter Maschinenbefehl EXG zum Tausch der Werte zweier Register. Das ist ein weiterer Grund, warum man solche wie die oben beschriebene Varianten nicht benutzen sollte: Den traditionellen Tausch mit Zwischenvariable kann ein Compiler erkennen und durch Benutzung solch optimierter Maschinenbefehle ersetzen. Die Variante mit der Arithmetik dagegen würde nicht davon profitieren.

Zum Abschluss nun noch eine Einsicht betreffend einer speziellen Sprache: Java. Hier zeigt sich, dass die "traditionelle" Variante deutlich schneller ist - weil der erzeugte Bytecode deutlich kürzer ist:

	public void a()
	{
		int a=10;
		int b=5;
		int c=a;
		a=b;
		b=c;
	}

ergibt:

public void a();
   Code:
      0: bipush        10
      2: istore_1
      3: iconst_5
      4: istore_2
      5: iload_1
      6: istore_3
      7: iload_2
      8: istore_1
      9: iload_3
     10: istore_2
     11: return

während

	public void b()
	{
		int a=10;
		int b=5;
		a=a+b;
		b=a-b;
		a=a-b;
	}

in folgenden Bytecode transformiert wird:

public void b();
   Code:
      0: bipush        10
      2: istore_1
      3: iconst_5
      4: istore_2
      5: iload_1
      6: iload_2
      7: iadd
      8: istore_1
      9: iload_1
     10: iload_2
     11: isub
     12: istore_2
     13: iload_1
     14: iload_2
     15: isub
     16: istore_1
     17: return

Kommentar hinzufügen (via ) Kommentare ansehen (via )

Kommentar hinzufügen (via ) Kommentare ansehen (via )