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:
|
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:
|
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):
|
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:
|
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":
|
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.
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.
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
:-)--hs