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

Shade Of Mine

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?

HumeSikkins

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

Erhard Henkes

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)

davie

std::iter_swap nicht vergessen

elise

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?

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

Helium

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

HumeSikkins

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.

PeterTheMaster

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?

HumeSikkins

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.

Erhard Henkes

@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.

Erhard Henkes

@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.

Daniel E.

PeterTheMaster schrieb:

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

Würde mich auch mal interessieren. Von Assemblerprogrammierern kenne ich die Technik, verkettete Listen mit einem Zeiger auf Zeiger auf 'Node' und einem Zeiger auf 'Node' zu erstellen. Das hat schon fast was von einer DVL, man kann allerdings die Liste nicht rückwärts traversieren und das ist es ja gerade, was eine DVL auszeichnet. -- Wir können jetzt ein lustiges Ratespiel aus der Kategorie 'Was ist passiert?' machen:
»Remember that old bitwise trick to swap two integers without a temporary? (Of course you do ? it's Common Knowledge). With a little imagination you can use that technique to craft iterators that don't know which way to go.«

HumeSikkins

Daniel E. schrieb:

PeterTheMaster schrieb:

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

Würde mich auch mal interessieren.

Daniel E. schrieb:

»Remember that old bitwise trick to swap two integers without a temporary? (Of course you do ? it's Common Knowledge). With a little imagination you can use that technique to craft iterators that don't know which way to go.«

Scheinbar kennst du ja den Artikel. Den Source-Code gibt es hier:
http://www.semantics.org/code.html

Deinem Beitrag entnehme ich aber, dass es sich hier um etwas anderes handelt als ich dachte. Verwundert mich aber auch nicht so sehr, da ich den Artikel sowieso nie verstanden habe.

@Hume: warum so arrogant?

Wieso bitte arrogant? Ich bin doch nicht derjenige, der hier behauptet alles schon zu können. Ich bin nur der dumme Trottel, der noch auf Sachen hinweist, die alle anderen schon mit 15 konnten.
Zu meiner Verteidigung bleibt mir nur zu sagen, dass ich das mit 15 nicht konnte und dass mich solche Techniken mit 24 und nach 8 Semestern Informatik-Studium nach wie vor verblüfft und staunend zurück lassen.

PeterTheMaster

HumeSikkins schrieb:

Ich bin doch nicht derjenige, der hier behauptet alles schon zu können.

und wo tu ich das?

Helium

Ich glaube, das liegt eher an der Art zu programmieren. Vielleicht kenn ich mich ja tatsächlich besser mit der Bool'schen Algebra aus, dafür haust du mich mit komplexen Template-Metaprogrammierungstricks in die Pfanne. Das ist doch vollkommen egal.

Mir geht es immer um alles gleichzeitig. Performance ist ein wichtiges Ziel, denn damit hebt sich C++ ab.

IMHO hat C++ soviel mehr zu beiten, als pure Geschwindigkeit, um sich von anderen Sprachen abzuheben. Aber wenn man Assembler verwenden, um die Geschwindigkeit zu steigern hat das nichts mehr mit C++ zu tun. Das kann ich auch in vielen anderen Sprachen.

HumeSikkins

Ich glaube, das liegt eher an der Art zu programmieren. Vielleicht kenn ich mich ja tatsächlich besser mit der Bool'schen Algebra aus, dafür haust du mich mit komplexen Template-Metaprogrammierungstricks in die Pfanne. Das ist doch vollkommen egal.

Mir war gar nicht bewusst, dass es hier um einen Wettstreit geht.
Nur mal für die Bücher: Ich bin fest davon überzeugt, dass 72,4% der Forumuser hier besser programmieren können als ich. Nur darum geht es doch überhaupt nicht. Ich habe ein Thema vorgeschlagen, dass man meiner Meinung nach einem Programmieranfänger nahe bringen sollte (gleich an einem schönen Beispiel). Wenn jetzt 72,4% der User hier sowas sagen wie: "Nette Idee, Hume. Nur sind wir hier längst auf einem ganz anderen Level. Das unterfordert die Leute doch und treibt sie in den Langeweile-Tod", dann habe ich damit überhaupt kein Problem. Vielleicht wäre ich erstaunt, nur angefressen sicher nicht.
Dieses "Hallo? Da habe ich schon mit 15 drüber gelacht und damals hatte ich noch eine Hirnhälfte für wohltätige Zwecke verschenkt." ist hingegen eine Arroganz mit der ich nicht umgehen kann. Deshalb meine Reaktion.

PeterTheMaster schrieb:

HumeSikkins schrieb:

Ich bin doch nicht derjenige, der hier behauptet alles schon zu können.

und wo tu ich das?

Keine Ahnung. In diesem Thread wohl nicht. Aber das solltest du doch auch schon rausgefunden haben.
Oder muss ich jetzt hier jeden namentlich aufzählen, der das ebenfalls nicht tut? Das wird schwer, da ich leider nicht alle 9542 Login-Namen kenne.

Helium

Natürlich ist es kein Wettstreit. Meine letzte Antwort zielte mehr in die Richtung, dass jeder seine Stärken und Schwächen hat.

Und hiermit entschuldige ich mich offiziell für meine Aroganz.

Heutzutage wird die Bool'sche Algebra kaum noch verwendet. Als ich angefangen habe zu programmieren (tut mir leid ich war da eben noch sehr jung), hat man sich eben mit so 'nem Kram beschäftigt und daher kann ich's noch und für mich ist das nichts cooles, sondern normal. Heute beschäftigt man sich mich anderen Dingen. Deshalb verblüffen mich andere Techniken, die ich hier im Forum, vor allem von dir, zu sehen bekomme, die du täglich einsetzt, ohne weiter darüber nachzudenken.

Daniel E.

HumeSikkins schrieb:

Daniel E. schrieb:

»Remember that old bitwise trick to swap two integers without a temporary? (Of course you do ? it's Common Knowledge). With a little imagination you can use that technique to craft iterators that don't know which way to go.«

Scheinbar kennst du ja den Artikel. Den Source-Code gibt es hier:
http://www.semantics.org/code.html

Scheinbar ist das passende Wort. Ich hatte deine Infos in eine Gugle-Recherche eingebaut und raus kam http://www.cuj.com/articles/2002/0206/. Danke für den Link.