Musterlösungen

Um die Erklärung der Algorithmen zu vereinfachen, werde ich davon ausgehen, dass n > 0 ist. Für n == 0 ist die Implementierung trivial, für n < 0 ist sie symmetrisch, bzw. identisch mit der Lösung für n = M-n. Die Algrithmen sind hier in "sowas wie C ohne Typen" beschrieben. Es geht mir hier nicht darum, Quelltext eines kompilierbaren Programmes zu präsentieren, sondern um möglichst lesbare Vorstellung des Algorithmus.

Die naive Implementierung 1

Wir benutzen einen Zwischenspeicher B der Größe n:

// Zwischenspeicher füllen for (i = 0; i < n; ++i) B[i] = A[i]; // A verschieben for (i = 0; i + n < M; ++i) A[i] = A[i+n]; // den Rest von A aus dem Zwischenspeicher auffüllen for (i = 0; i < n; ++i) A[M - n + i] = B[i];

Diese Implementierung ist nicht gerade speichereffizient. Sie braucht n zusätzliche Speicherzellen ("Parkplätze") für die Zwischenspeicherung der Elemente von A. Die zeitliche Komplexität ist O(M+n) = O(n). Insgesammt muss der Fahrer M+n mal ein Auto starten.

Die naive Implementierung 2

Wir machen es ähnlich wie in der naiven Implementierung 1, aber statt n Elemente zwischenzuspeichern, speichern wir nur eins und rotieren n-mal um ein Element:

for (i = 0; i < n; ++i) { B = A[0]; for (j = 0; j + 1 < M; ++j) A[j] = A[j+1]; A[M-1] = A[0]; }

Diese Methode ist sehr speichereffizient, allerdings ist die Performance sehr schlecht, denn jedes Element wird n- oder (n+1)-mal verschoben. Bei der naiven Implementierung 1 war es höchstens 2-mal.

Die trickreiche Flip-Flop Lösung

Diese Implementierung gefällt mir sehr, den sie ist sehr kompakt, effizient und elegant. Zuerst lösen wir aber eine andere Aufgabe: Die Reihenfolge der Elemente eines Arrays zwischen den Indizes g und h umkehren (h nicht eingeschlossen):

revert(A, g, h) { for (i = g, j = h-1; i < j; ++i, --j) { B = A[i]; A[i] = A[j]; A[j] = B } }

Die Prozedur revert braucht eine zusätzliche Speicherzelle und 3/2-Verschiebungen pro Element zwischen g und h.

Dann sieht unsere Implementierung der Rotation folgendermaßen aus:

// Beispieleingabe: A = {0, 1, 2, 3, 4, 5}; M also = 6; n = 2; revert(A, 0, M); // 5, 4, 3, 2, 1, 0 revert(A, 0, n); // 4, 5, 3, 2, 1, 0 revert(A, n, M); // 4, 5, 0, 1, 2, 3

Diese Implementierung ist genau so speichereffizient wie die naive Implementierung 2 (nur eine zusätzliche Speicherzelle), dafür aber viel effizienter. Sie braucht 3/2 * (M + n + M - n) also 3*M verschiebungen der Elemente. Sollte ich im realem Leben vor der Aufgabe stehen, eine Rotate-Prozedur zu implementieren, würde vieles für diese Variante sprechen - drei simple Aufrufe einer anderen Methode - was will man mehr? OK, jedes Auto muss hier 3x gestartet werden. Unter der Voraussetzung, dass eine Optimierung angebrauch wäre, wäre dies die Schraube, an der drehen könnte. Die nächste Lösung zeigt, wie:

Die effizienteste Lösung

Der folgende Algoritmus ist der effizienteste, wenn man die Performance an der Anzahl der Verschiebungen der Autos misst. (Natürlich sind auch die andren Operationen alle O(M)).

Bei den meisten derobenbeschriebenen Lösungen haben wir eine Tatsache nicht genutzt: Wir wissen von vorne herein, wohin welches Element der Arrays gehört. Wir könnten also jedes Element (Auto), sofort auf seine richtige Postion umparken. Natürlich muss zuerst das Auto, das an der Stelle parkt, zuerst weggefahren werden. (In der naiven Implementierung 1 haben wir eigentlich genau das gemacht, aber hier wollen wir uns auf einen zusätzlichen Parkplatz beschränken)

Hier haben sich die Ansätze, wohin das störende Auto zwichengeparkt wird, etwas unterschieden. Die Denksportler, die Elemente immer vertauscht haben, sind mit dem störenden Auto zweimal zuviel gefahren - einmal auf den Pufferparkplatz, dann auf den Parkplatz, wo das andere Auto stand - und dieser Parkplatz ist im allgemeinen nicht der richtige. Besser ist es, jedes Auto möglichst sofort auf den richtigen Platz zu verschieben.

Am effizientestem ist es also, einen Speicherzelle im Array zu nehmen, das falschplatzierte Element in einen Zwischenspeicher zu verschieben, das richtige Element auf die Stelle platzieren, und mit der "leergewordenen" Stelle weiterzumachen. Das machen wir solange bis, bis wir aus der ursprünglichen Zelle verschieben würden. Da sie jetzt aber schon richtig gefüllt ist, nehmen wir das Element aus dem Zwischenspeicher. Das ganze wiederholen wir solange, bis es Zellen mit falschen Inhalt gibt.

Übrigens, diese Methode kann man nicht nur bei einer Rotation, sonder bei jeder Umsortierung benutzen, bei der sich die Originalposition des Elementes von dessen Zielposition direkt ableiten lässt.

Hier die "Implementierung":

misplaced = M; // Anzahl der falsch platzierten Elemente buffered = 0; // Index der Zelle, dessen Originalwert sich im Zwischenspeicher befindet while (misplaced > 0) { B = A[buffered]; empty = buffered; while (true) { next = empty + n; if (next > M) next -= M; if (next == buffered) break; A[i] = A[next] --misplaced; empty = next; } A[empty] = B; --misplaced; ++buffered; }

Beispiel für den einfachen Fall M = 7, n = 3 ("leere" Zellen mit * markiert, die next ist rot)

B = 0 // Index = 0

* 1 2 3 4 5 6

3 1 2 * 4 5 6

3 1 2 6 4 5 *

3 1 * 6 4 5 2

3 1 5 6 4 * 2

3 * 5 6 4 1 2

3 4 5 6 * 1 2

jetzt aus dem Zwischenspeicher verschieben:

3 4 5 6 0 1 2

Beispiel für Zahlen mit ggT > 1; M = 10, n = 4;

B = 0 // Index = 0

* 1 2 3 4 5 6 7 8 9

4 1 2 3 * 5 6 7 8 9

4 1 2 3 8 5 6 7 * 9

4 1 * 3 8 5 6 7 2 9

4 1 6 3 8 5 * 7 2 9

jetzt aus B:

4 1 6 3 8 5 0 7 2 9

misplaced == 5 also > 0 B = 1 // Index = 1

4 * 6 3 8 5 0 7 2 9

4 5 6 3 8 * 0 7 2 9

4 5 6 3 8 9 0 7 2 *

4 5 6 * 8 9 0 7 2 3

4 5 6 7 8 9 0 * 2 3

jeztz aus B:

4 5 6 7 8 9 0 1 2 3

Da jedes Element einmal auf seine richtige Stelle verschoben wird, und ggT(M,n) in den Zwischenspeicher, ist die zeitliche Komplexität des Algorithmus M + ggT(M,n). Kleine Bemerkung für Optimierer, man braucht nicht zu dividieren.

Die Umgehung der Lösung

Diese Lösung kommt von MichaelKnaup. In ihr wird nichts vorschoben, statt dessen wird der Zugriffsoperator auf das Array so geändert, dass A[i] dass i+n-ste Element liefert. (Natürlich mit der richtigen Behandlung der Unter- bzw. Überlaufes)

Auswertung

Ich bin mir nicht ganz sicher, wie hier dir Zylinder verteilt werden, also nehmt meine Bewertung nur als einen Vorschlag. Nach den offziellen Regeln sollte jeder Teilnehmer einen goldenen Zylinder bekommen, aber das wäre irgendwie komisch. Deswegen:

Den goldenen Zylinder für die effizienteste Lösung teilen sich AndreasBühmann - der sofort auf den Trick mit der Verschiebung auf die richtige Stelle gekommen ist. RalfWildenhues?, MichaelKnaup - zwar mit Swaps, aber durch den 3x XOR Trick, der, wenn anwendbar, den zusätzlichen Speicher einspart. Michael hat noch zusätzlich eine leicht abweiweichende Lösung angeboten, in der M-n Elemente sofort ihren richtigen Platz finden, und die n restlichen Elemente eventuell noch rekursiv rotiert werden müssen.

Den silbernen Zylinder teilen sich HelmutLeitner mit VolkerGlave für die Flip-Flop Lösung.

Ich nehme den Zylinder nicht an, da ich die Lösung hier geklaut habe, danke. (Gibt es eigtl. gar keinen Zylinder für die kürzeste Lösung? ;-) -- vgl

Neben den drei offziellen Zylindern möchte ich noch diese ausserordentliche Auszeichnungen vergeben.

MichaelKnaup bekommt für sein Array mit Offset beim Index den von IljaPreuß gestifteten bunten Zylinder für Querdenker.

Gerson Kurz für seine erfrischende Lösung in obfuscated Python die Tarnkappe der Ritter der Softwaregnosis :-)

Sollte ich was vergessen oder durcheinander gebracht haben, bitte korrigiert mich. Ich tausche in den nächsten zwei Wochen den Anzug gegen eine Badehose und den Computer gegen ein Cocktailglas um und werde online nicht erreichbar sein.

Ich hoffe, Euch hat diese Aufgabe Spaß gemacht, und ich freue mich auf die nächste Runde von SoftwareDenkSport.

--GregorRayman

Diskussion

Gregor, Danke für die Idee und die Abwicklung dieser Runde, du müsstest auch einen Preis bekommen. SoftwareDenkSport 2 hat glaube ich allen Freude gemacht und war die erste Seite, die jemals im DseWiki RecentChanges überholt hat. -- HelmutLeitner

Problem: Ich hab ein Problem mit der Preisvergabe, die vorher nicht abgesprochen war (Gregor ist jetzt 2 Wochen unterwegs). Bisher waren die Zylinder ziemlich schwer zu erlangen (bisher nur 2 Preisträger). IljaPreuß hat einen silbernen Zylinder als Sieger der 1. Runde (für eine aufwendige, aber nicht optimale Lösung einer ziemlich schweren Aufgabe), HelmutSchellong hat einen goldenen Zylinder für den größten Gesamtbeitrag zum DseWiki im 1. Jahr. Wenn wir bei der alten Vergabephilosphie bleiben, dann würde nur ein goldener Zylinder vergeben, entweder ungeteilt an AndreasBühmann oder geteilt an ihn gemeinsam mit RalfWildenhues? und MichaelKnaup. Hält sich bei den anderen die Enttäuschung in Grenzen? Andernfalls haben wir eine inflationäre Entwicklung bei den Preisen und frustrieren die bisherigen Preisträger. Was meint Ihr dazu? -- HelmutLeitner

Kein Problem. Ein Zylinder, an Andreas. -- vgl

Ich hätte persönlich kein Problem damit, mehr Zylinder zu vergeben. Hauptsache ich schließlich, das ganze macht Spaß... :-) -- IljaPreuß

Wenn's jetzt keinen Zylinder gibt, dann freu ich mich umso mehr, wenn ich denn mal einen bekomme :-) Und Spaß macht es unabhängig von der Farbe der Kopfbedeckung. Von mir aus geht das klar: ein Goldener an Andreas. --bs

Keine Enwände, und wunderbar erfrischend der Denksport :-) MichaelSchikora

Ich wollte keineswegs eine Zylinderinflation verursachen, leider hatte ich aber keine Zeit die Zylinderverteilung zu besprechen, ich war zwei Wochen offline. Ich stand also vor dem Problem, wie die Lösungen zu bewerten sind. Sie waren sehr nah aneinander, und mir erschien es nicht sehr gerecht, einen Zylinder nur für Andreas vorzuschlagen. Da ich nicht anders konnte, habe ich dieses Problem der Wikischaft überlassen. Hätte ich es mir besser überlegt, dann hätte ich statt der Zylinder lieber Fingerhüte vorgeschlagen. Die Aufgabe war ja recht einfach. --GregorRayman

:-)--hs

Helmut, ich denke Gregor wird das zu begründen versuchen, wenn er wieder zurück ist (als es um die Terminisierung ging, hat er mir gesagt, dass er ab 13. für 2 Wochen wegfährt). Ich seh das so - ohne mich intensiv damit beschäftigt zu haben - dass einige Methoden ohne wesentlichen Zwischenspeicher auskommen und dass damit quasi automatisch die übrige Eleganz bzw. Effizienz den Ausschlag gibt. Mein Tipp: das nächste Mal sicherheitshalber auf jeden Fall mitmachen :-). Liebe Grüße -- HelmutLeitner

Von SoftwareDenkSport 2, ganz unten:

"Na ja, wir haben hier schon Lösungen, die im Speicherbedarf optimal sind (ich zähle hier nur Platz für die Elemente des Arrays, nicht die Variablen für Indizes und auch nicht die Stackgröße.*) Also bleibt bei der Bewertung der Algorithmen Eleganz, Einfachkeit und Performance ein Kriterium. Aber hier geht es, zumindest ich sehe es so, nicht umbedingt um den Gewinner, sondern um den Spaß an Algorithmen :-)"

Ich wollte vor allem Streit bei der Bewertung der Lösungen vermeiden und deswegen habe ich ein Primärkriterium definiert. Es hat sich gezeigt, dass die Optimierung des Speicherverbrauchs und die der Performance bei single-thread Umsetzungen nicht miteinander konkurieren. Mit mehreren Prozessoren sieht es aber schon anders aus. --GregorRayman