Hello, Guest the thread was viewed22k times and contains 150 replies

last post from BlackJack at the

Sortieren in V2 BASIC

    Hallo,


    "nebenan" läuft ja ein Sortierwettbwerb in der Assembler-Ecke mit 256 Bytes. Bei der letzten Assembler-Compo ging es ums Buchstaben-Umdrehen und es gab einen funktionierenden Basic-Code dazu (an dem ich mir dann auch das Hirn zerbrochen habe).


    Diesmal ist kein Basic-Beispiel aufgeführt also dachte ich, ich schreibe eins. Sortieren braucht man doch, vor allem für Highscore-Tabellen.


    Mein Code geht, aber es ist eine Pein, weil er so langsam ist. Kann das jemand schneller?


    Morgen zusammen! ^^


    Bytebreaker,


    die meisten naiven Sortierverfahren haben ja quadratisches Laufzeitverhalten (d.h. brauchen in etwa die vierfache Zeit bei der doppelten Menge an zu sortierenden Zahlen, die 9-fache Zeit bei der 3-fache Menge, etc.) was kurz mit O(n²) notiert wird. Deins geht mit O(n³), da drei Schleifen über die volle Anzahl ineinander geschachtelt sind.


    Üblicherweise setzt sich ein Sortieralgorithmus aus zwei relevanten Teilen zusammen: es werden zwei Elemente (nicht notwendig benachbart!) miteinander verglichen, und wenn sie verkehrtherum angeordnet sind, werden sie getauscht.


    Macht man das z.B. systematisch wiederholend mit allen Feldpaaren von vorne nach hinten, und hört erst dann auf, wenn alle Elemente richtig sortiert sind, dann erhält man den Bubblesort:


    Code
    1. 10 N=10:DIMX(N):FORT=1TON:X(T)=RND(1):NEXT
    2. 11 :
    3. 12 P=0:FORT=1TON-1:IFX(T)>X(T+1)THENX=X(T):X(T)=X(T+1):X(T+1)=X:P=-1
    4. 13 NEXT:IFPTHEN12
    5. 14 :
    6. 15 FORT=1TON:PRINTX(T):NEXT


    Der Algorithmus hat seinen Namen daher, daß die Zahlen wie Blasen im Feld aufsteigen. Eine Zahl steigt so lange, bis sie von einer größeren Zahl aufgehalten wird, dann steigt letztere dafür dann weiter auf. Falls denn mindestens eine Vertauschung stattgefunden hat, wird erneut die FOR-Schleife ausgeführt.


    Nach dem ersten Durchlauf der FOR-Schleife steht somit auf jeden Fall die größte Zahl im letzten Feldelement. Nach dem zweiten Durchlauf (sofern er denn nötig war), die zweitgrößte Zahl im vorletzten Feldelement. Und so weiter. Das heißt, die FOR-Schleife selbst wird maximal N mal ausgeführt, und darum ist die Laufzeit im Mittel und auch im ungünstigsten Fall quadratisch. Im günstigsten Fall läuft die FOR-Schleife nur einmal durch und stellt dabei fest, daß alle Zahlen richtig sortiert sind und ist dann fertig.


    Es gibt bessere Algorithmen, die dann auch nicht nur unbedingt benachbarte Feldelemente vertauschen und die Auswahl der zu vergleichenden und tauschenden Elemente auch an Hand der zuvor getauschten Elemente festlegen, doch die sind programmtechnisch komplizierter: Quicksort z.B. hat die notorische Eigenschaft, daß er bei kleinsten Änderungen im Code auch schon mal "kaputtgeht", den muß man also besonders vorsichtig implementieren.


    Für kleine Elementanzahlen bis etwa 20 ist ein Bubblesort völlig unproblematisch verwendbar, und meistens genauso schnell wie die etwas intelligenteren Sortierverfahren.

    Sehr schöne Beschreibung!


    Das schöne am Bubblesort - er ist intuitiv und bietet auch noch Platz für Optimierungen. Statt immer zu N-1 durchzuiterieren, kann man hier abkürzen und nur bis zur letzten Tauschstelle des vorherigen Durchlaufs iterieren. Mir ist auch noch dunkel so, als ob auch am Anfang abgekürzt werden kann, nur dazu müsste ich bei Wikipedia spicken ;)


    Kleine Anmerkung zu O(...)-Notation: nicht blind danach gehen. Gibt Algorithmen, die einen gleichen/besseren O-Wert als Quicksort haben (namentlich Heapsort, Smoothsort), aber durch den Overhead letztendlich langsamer sind oder ihren Vorteil nur unter bestimmten Voraussetzungen erzielen. Und auch Quicksort kann gegen O(n²) gehen, wenn er naiv implementiert ist und auf ungünstige Wertekombinationen trifft.

    Mike's Algorithmus ist etwa 7x schneller als meiner gemessen auf 10 Werte.


    Bei mir sind es ca. 11 Sekunden, bei Mike etwa 1,5. Also eine Steigerung um 733%. Ich habe es extra mit Fließkommawerten <1 probiert, wobei meine nur zwischen 1 und 4 Stellen nach dem Komma hatten. Mike's haben alle mehr.


    Man müsste mal schauen wie Bubblesort sich verhält bei gleichen Werten in der Sortiermenge. Bei mir wird es abgefangen, egal wieviele Gleiche und an welcher Stelle. Heute hat mir ein Entwickler aus meiner Firma erzählt, Bubblesort wird irgendwann korrupt bei bestimmten Sortiermengen. Ich glaube, mein Code erzeugt keine korrupten Sortierungen, wird >10 bloß unbrauchbar langsam, z.B. in Spielen für Highscore-Listen (wobei man per Compiler sicher noch was machen könnte, so dass der Spieler nicht stutzt warum das Programm scheinbar einfriert).


    Da bis 20 aber Bubblesort kein Stress macht, sollte man diesen Algorithmus nehmen für eigene Highscore-Listen.


    Edit


    @ Oobdoo


    Ich habe meinen Sortieralgo vorhin 1:1 in WinCPC ausgeführt per Autotype. Ich war beeindruckt, der Basic-Parser des CPC übernimmt die Syntax ohne Murren und es klappt tatsächlich. Mit dem Unterschied, dass der CPC meinen Code um etwa die Hälfte schneller ausführt als der Cevi wie Du schon sagtest.

    Quote from Bytebreaker


    ...
    Man müsste mal schauen wie Bubblesort sich verhält bei gleichen Werten in der Sortiermenge. Bei mir wird es abgefangen, egal wieviele Gleiche und an welcher Stelle. Heute hat mir ein Entwickler aus meiner Firma erzählt, Bubblesort wird irgendwann korrupt bei bestimmten Sortiermengen. Ich glaube, mein Code erzeugt keine korrupten Sortierungen, wird >10 bloß unbrauchbar langsam, z.B. in Spielen für Highscore-Listen (wobei man per Compiler sicher noch was machen könnte, so dass der Spieler nicht stutzt warum das Programm scheinbar einfriert).
    ...

    Steht doch in Mikes Code, wie er sich bei gleichen Werten verhält - genauso wie bei bereits richtig sortierten Werten - er geht weiter in der Schleife. Das Sortieren von gleichen Werten ist so genauso schnell wie bei einer bereits sortierten Liste (und ich wage zu behaupten: hier schlägt Bubblesort sogar Quicksort).


    Korrupte Sortierung? Nö, wenn er bei größeren Mengen Mist baut, dann weil der Rechner/das Betriebssystem/die Programmiersprache da Grenzen setzt. Aber nicht Bubblesort.

    Quote from Tale-X

    Korrupte Sortierung? Nö, wenn er bei größeren Mengen Mist baut, dann weil der Rechner/das Betriebssystem/die Programmiersprache da Grenzen setzt. Aber nicht Bubblesort.


    Wie soll durch Rechner/das Betriebssystem/die Programmiersprache eine korrupte Sortierung entstehen? :gruebel

    Quote from Tale-X

    Wenn die Liste >32767 Einträge enthält, aber die Zeigervariable einen Wertebereich von -32768 bis 32767 hat (16Bit mit Vorzeichen). Wenn das nicht sauber abgefangen wird, gibt's Murks.


    Ach sowas meinst Du. Ich hatte sonstwas vermutet.

    Quote

    Steht doch in Mikes Code, wie er sich bei gleichen Werten verhält - genauso wie bei bereits richtig sortierten Werten - er geht weiter in der Schleife. Das Sortieren von gleichen Werten ist so genauso schnell wie bei einer bereits sortierten Liste (und ich wage zu behaupten: hier schlägt Bubblesort sogar Quicksort).


    Korrupte Sortierung? Nö, wenn er bei größeren Mengen Mist baut, dann weil der Rechner/das Betriebssystem/die Programmiersprache da Grenzen setzt. Aber nicht Bubblesort.


    Das mit der korrupten Sortierung war eine falsche Wiedergabe von meiner Seite. Ich habe aus "funktioniert nicht" in einer Eigeninterpretation "falsch sortiert" gemacht.


    Bzgl. Gleiche sortieren: Ich sehe jetzt, dass ein reiner Größer-Vergleich im Bubblesort reicht - logisch. Ich war gedanklich auf >= gepolt weil ohne diesen Operator mein sequenzieller Sortierer (so heißt das wohl, hab ich erfahren) gar nicht funktionieren würde. Das war einfach nur zu kurz gedacht.

    Quote from Tale-X

    Das Sortieren von gleichen Werten ist so genauso schnell wie bei einer bereits sortierten Liste (und ich wage zu behaupten: hier schlägt Bubblesort sogar Quicksort).


    Stimmt! Ich habe mich mal intensiver mit dem Bubblesort auseinandergesetzt und hab ihn in mehrerer Hinsicht verbessert. Nichts, was nicht jeder andere auch machen könnte - der Bubblesort lässt ja einiges an Spielraum für Verbesserungen. Danach habe ich dann einige Testläufe gegen einen Quicksort gemacht. Zu den Ergebnissen muss ich sagen, dass ich die Basic-Programme nicht auf BASIC V2 Besonderheiten optimiert habe. Ich habe also nicht kontrolliert, ob FOR-NEXT oder eine selbstgebastelte Schleife schneller sind und auch nicht, ob es kontraproduktiv ist Integer-Variablen zu benutzen, usw. . Ob einer der beiden Sorter damals mehr oder weniger davon profitiert hat, kann ich heute nicht mehr sagen.
    Bei sortierten Listen und nur leicht unsortierten Listen war mein Bubblesort im Schnitt doppelt so schnell wie der Quicksort. Das hört sich spontan ja gut an aber das war nur die eine Seite der Medaille. Bei kpl. unsortierten Listen war der Quicksort um den Faktor 100 schneller. Da ist die Freude über den selbst optimierten Bubblesort schnell verflogen.
    Als Ergebnis: Für eine Highscoreliste bietet sich also der Bubblesort an. Er ist deutlich einfacher zu verstehen und wird in diesem Fall auch schneller sein (wobei die Highscoreliste schon echt lang sein muss, um es zu merken). Wenn man aber Situationen hat, wo man vorher schon weiß, dass die Listen sehr lang und kpl. durcheinander sind, sollte man einen schnelleren Sorter wählen (oder am besten gleich Abstand von BASIC nehmen). ;)


    Wen es interessiert:
    Mein Bubblesort geht die Liste nur ein Mal durch und schiebt jeweils die Werte bis zur richtigen Position, dazu wird ein großer und nicht viele Kleine Ringtausche gemacht und nach dem Verschieben macht er bei der Ursprungsposition weiter. Für eine Highscoreliste mit immer nur einem neuen Wert, der einmal mehr oder weniger weit nach oben geschoben wird, ist der original Bubblesort aber trotzdem schneller. Man sollte sich aber vorher die Richtung des Bubblesort klar machen und wo der neue Wert zur Liste hinzugefügt wird. Wenn man das nicht beachtet, kann man sich in BASIC schnell mal ein paar längere Pausen einbauen!

    Die Basic-Optimierungen sehe ich eher als optional an (und hinsichtlich der Wartbarkeit als kontraproduktiv). Das meiste Potenzial zum Beschleunigen liegt in den Algorithmen und im Konzept (alternativ: im Kopf des Programmierers). Wenn das ausgeschöpft ist, kann immer noch ein Compiler (oder Maschinensprache) hinzugezogen werden.


    Ansonsten grübel ich gerade, ob das Quicksortprogramm in Basic ein Bubblesortprogramm in Maschinensprache schlagen kann (Faktor 100 ist ja ein ziemliches Handicap). Wäre doch ein gutes Thema für ne Basic-Combo: schlage mit einem Basicprogramm das Maschinenspracheprogramm. Je länger ich drüber nachdenke, desto mehr gefällt mir die Idee!


    Deep4: neugierige Frage: warum setzt Du p nicht auf 0 in Zeile 2? Wegen n-1, steht ja im Code :whistling:

    Quote from Bytebreaker

    Heute hat mir ein Entwickler aus meiner Firma erzählt, Bubblesort wird irgendwann [irgendwas] bei bestimmten Sortiermengen.


    Das fällt wohl eher unter die Kategorie Ammenmärchen.


    Cyberdyne,


    am Bubblesort kannst Du noch ewig rumoptimieren, von der Idee kommt man aber schnell ab, wenn man mal einen laufenden Quicksort zur Hand hat und die beiden gegeneinander antreten läßt.


    Die Version von Quicksort hier nimmt einfach das mittlere Element eines Sortierbereiches als Pivot her und fällt darum nicht gerade bei bereits vorsortierten Feldern mit quadratischer Laufzeit auf die Nase. Weiterhin wird immer das kleinere Unterfeld als erstes sortiert, auf diese Weise minimiert man den nötigen Stapelspeicher. DIMS(31) reicht für 65535 Elemente. In Zeile 11 kann N geändert und in Zeile 13 mit GOSUB20 oder GOSUB50 zwischen Bubble- und Quicksort gewechselt werden:



    Bis N=10 liegen die beiden etwa gleichauf, Bubblesort ist vielleicht sogar schneller, aber schau mal was für größere N passiert:


    Dies sind die Laufzeiten in 1/60 Sekunden (Jiffies):



    Das einzig Gute am Bubblesort ist, daß man ihn wirklich schnell hingeschrieben bekommt, wenn man die "Optimierungen" wegläßt. Und wie Deep4 ja schon vorgeführt hat, ist ein Sortier-Algo schnell mal verbockt - einwandfreie Funktion ist hier aber das höchste Gut!

    Quote from Mike

    Cyberdyne,


    am Bubblesort kannst Du noch ewig rumoptimieren, von der Idee kommt man aber schnell ab, wenn man mal einen laufenden Quicksort zur Hand hat und die beiden gegeneinander antreten läßt.


    Hallo? Hast du eigentlich gelesen, was ich geschrieben habe? Das habe ich alles schon hinter mir! Ich habe jedoch mit Listen von 1000 Werten getestet, beide Sorter immer mit exakt den gleichen Listen sortieren lassen und speziell mit unterschiedlich stark unsortierten Listen gearbeitet. Da waren:
    - kpl. sortierte Liste
    - kpl. falsch herum sortierte liste
    - kleinste Zahl an höchster Stelle
    - größte Zahl an niedrigster Stelle
    - kpl. zufällig erzeugte Liste
    - an 100 zufälligen stellen Zufallszahlen in eine sortierte Liste ausgetauscht (10% unsortiert)
    - das gleiche mit 20%
    - das gleiche mit 50%
    Die Listen erzeugen hat länger gedauert als die Sorter zu schreiben! ;)


    Ergebnisse hab ich ja oben schon erwähnt.

    Quote from Cyberdyne

    Hallo? Hast du eigentlich gelesen, was ich geschrieben habe?


    Klar hab' ich das.


    Es ist ja schön, daß Bubblesort bei (nahezu) korrekt sortierten Listen in die Nähe der linearen Laufzeitordnung kommt, das kriegt meine einfache Version aber auch schon hin und ist bei einer tatsächlich korrekt sortierten Liste optimal. Jede weitere Optimierung an Bubblesort halte ich für Zeitverschwendung.

    Quote from Mike

    Klar hab' ich das.


    Sicher?


    Quote from Cyberdyne

    Danach habe ich dann einige Testläufe gegen einen Quicksort gemacht.


    Quote from Mike

    von der Idee kommt man aber schnell ab, wenn man mal einen laufenden Quicksort zur Hand hat und die beiden gegeneinander antreten läßt.
    ...


    Quote from Cyberdyne

    Als Ergebnis: Für eine Highscoreliste bietet sich also der Bubblesort an.


    Wie geschrieben, hatte ich das alles schon gemacht. Ich habe auch nie behauptet, dass man für die Highscoreliste einen besseren Bubblesort braucht. Es ging nur um die Vor- und Nachteile der Sorter und da stellt sich halt raus, dass der Quicksort in einigen Bereichen viel schneller ist aber in einigen Bereichen auch deutlich langsamer. Und genau in den Bereichen kann man den Bubblesort auch noch ganz einfach und schnell deutlich optimieren. Für die Highscoreliste würde ich den originalen Bubblesort auch anpassen, weil man bei einem neuen Score auch nur ein Durchlauf nötig ist. Ein weiterer Durchlauf wäre einfach Zeitverschwendung.


    Apropos "Zeitverschwendung"? Das war es nicht - es war Spaß an der Sache! Bei meinem eigentlichen Programm wurde eine Messwerttabelle immer wieder um neue Werte erweitert und dann wieder neu sortiert. Von Messungen zu Messungen wurde der Anteil der unsortierten Werte also prozentual immer kleiner. Da war mein angepasster Bubblesort die "beste" Lösung (von denen, die ich getestet habe). Am Anfang wäre der Quicksort vielleicht noch schneller gewesen aber was spart man bei der Sortierung von 10 Werten. Bei 500 oder 1000 oder noch mehr wird es in Basic schon interessanter und da war der Quicksort halt unterlegen (und der normale Bubblesort auch). Dazu war das ganze nur eine private Spielerei/Zeitvertreib und es hat Spaß gemacht den Sorter für das gegebene Problem zu optimieren. Bei den Ladezeiten einer 1541 kann man zwar fragen, ob es sinnvoll ist, Zeit zu investieren, um bei jeder Sortierung ein paar Sekunden zu sparen. Eine ähnliche Frage wäre: Ist es sinnvoll heute noch am C64 zu "arbeiten"? Aus meiner Sicht war das optimieren des Sorters und das erstellen des Testprogramms eine größere Herausforderung als das eigentliche Messprogramm und hat mir viel mehr Spaß gemacht.

    Quote from Cyberdyne

    Von Messungen zu Messungen wurde der Anteil der unsortierten Werte also prozentual immer kleiner. Da war mein angepasster Bubblesort die "beste" Lösung (von denen, die ich getestet habe). Am Anfang wäre der Quicksort vielleicht noch schneller gewesen aber was spart man bei der Sortierung von 10 Werten. Bei 500 oder 1000 oder noch mehr wird es in Basic schon interessanter und da war der Quicksort halt unterlegen (und der normale Bubblesort auch).


    Möglicherweise hättest du einfach nur eine bessere Wahl des Pivot-Elements in deinen Quicksort einbauen müssen, um dessen Worst-Case-Verhalten aus dem Weg zu gehen? Alternativ könnte man sich auch an den Implementierungen von Sortieralgorithmen in modernen Libraries und Programmiersprachen orientieren, da findet man gerne mal eine Mischung aus Quicksort und einem anderen Algorithmus (oft Heapsort): Zunächst wird die übliche Quicksort-Rekursion angewendet, aber wenn die Grösse der aktuellen Partition ein bestimmtes Limit unterschreitet wird diese mit dem zweiten Algorithmus sortiert.