3. Tausch (Assembler, Kopien auf Stack, Zeiger, Referenzen)

Tausch (Assembler, Kopien auf Stack, Zeiger, Referenzen)

  • E

    Schaut euch zu diesem Thema mal Lektion 33 - 37 bei Volkard an. Der findet sogar die swap-Funktion mit den Referenzen als Parameter nicht gut, da sich a und b verändern, nur weil man sie einer Funktion übergeben hat. Ich meine, man sollte alles zeigen, dabei für die einzelnen Methoden die Themen Portabilität und Performance diskutieren. Assembler ist bezüglich Portabilität absolut problematisch (AT&T-, Intel-Syntax).

    0
  • B

    Ich habe keine Scheu vor Assembler, und habe auch nichts bezüglich Portabilität gesagt. Ich sage, dass das Beispiel mit Assembler keinen didaktischen Wert hat: Ein Einsteiger wär gut beraten, da einfach drüberzulesen, und dann kannstes auch gleich weglassen. Mit Hardcore-C++ hat das nichts zu tun, schon allein weil das Beispiel so mies ist. Das schlimme ist, dass jemand, der in diesem Gebiet eher unbeleckt ist, glauben könnte, die Assembler-Lösung sei die schnellste und daher vorzuziehen.

    0
  • W

    EDIT: Einiges davon hatte Bashar schon erwähnt...
    Das Problem ist, dass sich Anfänger auf diese Weise von vorne herein an umständliche Sachen gewöhnen könnten. Vor 2 Jahren hätte ich Erhards Code gelesen und mir gedacht: "Geil, Assembler. Sieht ja voll kompliziert aus. Dann ist es bestimmt auch schneller als das popelige swap!". Überzeugt davon das Richtige zu tun hätte ich es in vieele vieeele Programme eingebaut und würde mich heute totärgern weil ich solch einen Mist in meinen alten Sourcen rumgammeln habe aber nicht die Zeit finde es auszubessern. Ich denke man sollte in normalen Anwendungen komplett auf Assembler verzichten. Sicher, ich hatte auch schonmal einen dieser Fälle in denen ein wenig inline-asm Wunder wirkte war mir aber auch im klaren darüber was ich machte und versuchte diese Stelle so isoliert wie möglich zu halten damit ich bei der Portierung mit ein paar ifdefs (also quasi mit blauen Flecken) davonkommen könnte. Wenn man so versessen auf "Hardcoreprogrammierung" ist sollte man bei seinem TASM bleiben und C++ den "Weicheiern" überlassen.

    0

  • die darstellung von
    call by value
    und
    call by reference

    ist ein typisches lehrbeispiel, soll übrigens nicht "std::swap" ersetzen ;), sondern muss zwischen dem erlernen von zeigern und referenzen und klassen angesiedelt werden, um zu zeigen, daß es billiger ist, mit referenzen objekte zu übergeben, als per wert.

    und natürlich auch: was passiert da. (mal wieder im speicher rumkriechen, ein wenig den überblick kriegen, zeiger festigen...)

    assembler gehört da nicht rein. ! ausrufungszeichen.
    entweder ich unterrichte c++ oder ich unterrichte assembler.

    um assemblercode einzubinden, hätte ich den anspruch, daß die leute wissen was sie tun, wäre dann was für "c++ für leute mit assemblervorkenntnissen".

    aber an der stelle vollkommen unbrauchbar.

    0
  • E

    o.k., überzeugt. Assembler bleibt weg. XCHG würde die Sache auch nicht verbessern, da man hierbei ebenfalls über die Register (die man eigentlich vorher pushen und nachher poppen müsste) gehen muss. Die STL-Methode std::swap gehört selbstverständlich dazu und ist die Methode der Wahl.

    Wäre das so akzeptabel?

    #include <iostream>
#include <conio.h>
using std::cout;
using std::endl;

//globale Variablen
int a = 1; 
int b = 2;

void ausgabe()
{
    cout << &a << ": " << a << "\t " << &b << ": " << b  << endl << endl;
}

void erfolgloser_swap(int x, int y)
{
  cout << endl << "Kopien auf dem Stack: " << endl;
  cout << &x << ": " << x << "\t " << &y << ": " << y << endl;

  int temp = x;
  x = y;
  y = temp;

  cout << &x << ": " << x << "\t " << &y << ": " << y << endl;
  cout <<  endl;
}

void zeiger_swap(int* x, int* y)
{
  int temp = *x;
  *x = *y;
  *y = temp;
}

void referenzen_swap(int& x, int& y)
{
  int temp = x;
  x = y;
  y = temp;
}

int main()
{ 
    cout << "Ausgangssituation: " << endl;
    ausgabe();

    cout << "Tausch mittels std::swap(x,y): " << endl;            
    std::swap(a,b); // Methode der Wahl aus der STL
    ausgabe();

    cout << "Tausch mittels Referenzen: " << endl;            
    referenzen_swap(a,b);
    ausgabe();

    cout << "Tausch mittels Zeiger: " << endl;            
    zeiger_swap(&a, &b);
    ausgabe();

    cout << "Erfolgloser Tausch, da nur lokale Kopien getauscht werden:" << endl;            
    erfolgloser_swap(a,b);
    ausgabe();

    getch();
}
    0
  • S

    jetzt stoeren nur noch die funktion ausgabe() und die globalen variablen.

    0
  • E

    Mir hat das mit den globalen Variablen gut gefallen, da man dann den Unterschied bezüglich Speicheradresse leichter erkennt (global/lokal).
    Aber das geht auch anders, man kann ja beides zeigen:

    #include <iostream>
#include <conio.h>
using std::cout;
using std::endl;

void ausgabe(int x, int y)
{
    cout << &x << ": " << x << "\t " << &y << ": " << y  << endl << endl;
}

void erfolgloser_swap(int x, int y)
{
  cout << endl << "Kopien auf dem Stack: " << endl;
  ausgabe(x,y);

  int temp = x;
  x = y;
  y = temp;

  ausgabe(x,y);
  cout <<  endl;
}

void zeiger_swap(int* x, int* y)
{
  int temp = *x;
  *x = *y;
  *y = temp;
}

void referenzen_swap(int& x, int& y)
{
  int temp = x;
  x = y;
  y = temp;
}

void referenzen_swap_Variante(int& x, int& y)  
{  
  x^=y;  
  y^=x;  
  x^=y;  
} 

int main()
{ 
    //lokale Variablen
    int a = 1; 
    int b = 2;

    cout << "Ausgangssituation: " << endl;
    ausgabe(a,b);

    cout << "Tausch mittels std::swap(x,y): " << endl;            
    std::swap(a,b); // Methode der Wahl aus der STL
    ausgabe(a,b);

    cout << "Tausch mittels Referenzen: " << endl;            
    referenzen_swap(a,b);
    ausgabe(a,b);

    cout << "Tausch mittels Referenzen (Variante): " << endl;            
    referenzen_swap_Variante(a,b);
    ausgabe(a,b);

    cout << "Tausch mittels Zeiger: " << endl;            
    zeiger_swap(&a, &b);
    ausgabe(a,b);

    cout << "Erfolgloser Tausch, da nur lokale Kopien getauscht werden:" << endl;            
    erfolgloser_swap(a,b);
    ausgabe(a,b);

    getch();
}

    referenzen_swap_Variante(...) ist ein Vorschlag von HumeSikkins (s.u.).

    0
  • H

    Hallo,
    warum zeigt man Anfängern eigentlich nur den Dreieckstausch? Eine so schöne Situation würde ich nicht verstreichen lassen und gleich boolesche Logik (oder heißt das dann Algebra?) motivieren. Schließlich muss das sowieso *jeder* Programmierer können.

    0
  • S

    HumeSikkins schrieb:

    Eine so schöne Situation würde ich nicht verstreichen lassen und gleich boolesche Logik (oder heißt das dann Algebra?) motivieren. Schließlich muss das sowieso *jeder* Programmierer können.

    aeh... was meinst du?

    0
  • H
     

    void swap(int& a, int& b)
{
a^=b;
b^=a;
a^=b;
}
    0
  • E

    Danke! 🙂 Sehr gute Idee. Ich habe es gleich oben in den Code editiert. Da kann es gleich jeder ausprobieren.
    Jetzt fehlt eigentlich nur noch ein Geschwindigkeitsvergleich aller Methoden (da nehmen wir Assembler testweise wieder mit ins Boot!), z.B. jeweils x Mio. Tauschoperationen. Frage: was sollte bei Massenanwendung der schnellste Algo sein? Setzt ihr auf std::swap(x,y) ?

    Verloren! std::swap(x,y) ist hinter meiner "ach so miesen" Assemblervariante. Mit xchg war es deutlich langsamer, mov ist besser. Zur Zeitmessung bin ich wegen der Assembler-Variante auf globale Variablen umgestiegen. HumeSikkins boolsche-Tauschvariante ist leider langsamer als der Dreieckstausch. Sieht man von Assembler ab, so ist std::swap(...) vergleichbar schnell wie die eigene Zeiger- oder Referenz-Variante.

    Ergebnis: (60000000 Aufrufe)
    1. Assembler (die obige mov-Variante) 2.6 sec
    2. std::swap(...) 2.9 sec
    3. ref und zeiger (fast gleich) 2.9 sec
    4. ref (boolsche Variante) // Schönheit siegt nicht immer. 3.2 sec

    (gerundete Mittelwerte aus Messungen)

    0
  • D

    std::iter_swap nicht vergessen 😉

    0

  • Erhard Henkes schrieb:

    Verloren! std::swap(x,y) ist hinter meiner "ach so miesen" Assemblervariante. Mit xchg war es deutlich langsamer, mov ist besser. Zur Zeitmessung bin ich wegen der Assembler-Variante auf globale Variablen umgestiegen. HumeSikkins boolsche-Tauschvariante ist leider langsamer als der Dreieckstausch. Sieht man von Assembler ab, so ist std::swap(...) vergleichbar schnell wie die eigene Zeiger- oder Referenz-Variante.

    Ergebnis: (60000000 Aufrufe)
    1. Assembler (die obige mov-Variante) 2.6 sec
    2. std::swap(...) 2.9 sec
    3. ref und zeiger (fast gleich) 2.9 sec
    4. ref (boolsche Variante) // Schönheit siegt nicht immer. 3.2 sec

    (gerundete Mittelwerte aus Messungen)

    hallo??

    ich dachte, dir geht es hier darum, deinen schülerInnen didaktisch aufbereitet c++ zu unterrichten, und nicht, um geschwindigkeitshöchstgrenzen zu überschreiten.
    dann nimm gleich assembler pur, und lass c++ oder code in maschinensprache.

    die einheit call by value, call by reference soll was erklären. eigentlich die wichtige einheit, die funktionsweise von referencen (und zeigern) zu erläutern.

    humes idee finde ich darüber hinaus witzig, da schlägt man zwei fliegen mit einer klappe und zeigt mal eine nette anwendungsmöglichkeit von xor.

    hat didaktischen, nicht real life progger sinn.

    beim unterrichten muss man manchmal schritte gehen, hinführen.. bis man dann wo angelangt ist, und da sind auch oft nicht ganz optimierte lösungen dabei, aber es geht ums lernen.
    in der schule fängt man ja auch nicht gleich mit integralrechnung in der ersten klasse an, oder hat einer von euch das äpfel rechnen übersprungen?

    0
  • ?

    der XOR swap kommt ohne temp-variable aus und deswegen ist er so "cool"

    0
  • H

    Ich fand den auch mal "Cool", aber da war ich 15 und hab in Basic programmiert. Na egal.

    0
  • H

    Helium schrieb:

    Ich fand den auch mal "Cool", aber da war ich 15 und hab in Basic programmiert. Na egal.

    Großartig. Nur weil der Große Held es mit 15 schon konnte, und sich die Gang of two wahrscheinlich gerade totlacht, befreit das imo den Durchschnittsprogrammierer nicht davon, sich ein wenig mit boolescher Logik und solchen Zusammenhängen zu beschäftigen.
    Ob man gerade diese Tauschtechnik dann in einem Programm tatsächlich anwendet, oder jemals eine doppeltverkettete Liste mit nur einem Link-Pointer implementiert, steht doch auf einem ganz anderen Blatt.

    Ich verstehe ehrlich gesagt aber auch nicht, was das mit "cool" zu tun hat. Sowas ist Handwerk (und ich wünschte, ich würde es beherrschen). Solche kleinen Tricks könnne den Unterschied zwischen realisierbar und nicht realisierbar ausmachen.

    0
  • P

    und conio

    edit: oops, das war die antwort auf das letzte posting der ersten seite.

    wie macht man eine doppelt verkettete liste mit nur einem pointer pro node?

    0
  • H

    wie macht man eine doppelt verkettete liste mit nur einem pointer pro node?

    Na das wisst ihr Helden doch sicher am Besten. Irgendeiner hier wird das doch bestimmt mit drei das erste mal in Brainfuck implementiert haben.
    Ansonsten mal die Juni 2002 Ausgabe von Steve Dewhursts "common knowledge"-Serie lesen.
    Ach die gibt's ja gar nicht online. Na so ein pech.

    0
  • E

    @Hume: warum so arrogant? 😃
    @Shade: Poste bitte mal die XCHG-Variante, die so schnell sein soll. Ich finde sie nicht. 😉

    EDIT: siehe http://www.c-plusplus.net/forum/viewtopic.php?t=47131

    conio.h mit getch() ist einfach klasse. Da es mit MSVC++ als auch mit Dev-C++ läuft, spricht nichts gegen die Verwendung, selbst der Standard verbietet nicht, andere Header/Bibliotheken einzubinden.

    0
  • E

    @Elise: Mir geht es immer um alles gleichzeitig. Performance ist ein wichtiges Ziel, denn damit hebt sich C++ ab. Jeder Lernende hat das Recht (und die Pflicht) selbst nachzumessen:

    clock_t t1,t2;
double ts;
const unsigned N = ...;
t1=clock();
for(int i=0; i<N; ++i) function(...);
t2=clock();
ts=(t2-t1)/static_cast<float>(CLOCKS_PER_SEC);
std::cout << "\tZeit: " << ts <<" sec " << " function(...)" << std::endl;

    Da wird alles sofort rein gestopft, auch wenn's von HumeSikkins kommt. 😃

    0
Anmelden zum Antworten