Hallo Besucher, der Thread wurde 46k mal aufgerufen und enthält 313 Antworten

letzter Beitrag von Hoogo am

ASM-Compo #4: Sortieren

    Zitat von enthusi

    und RTI, BRK? :)


    Ganz toll Enthusi, bekommst ein Fleißsternchen von mir, dass Du noch zwei weitere Befehle kennst, die den Stack beeinflußen und von mir nicht ausdrücklich genannt wurden.
    Tut mir leid, dass ich so doof bin und Du so schlau. Ich freue mich auf Deinen Compo-Beitrag, in dem Du diese Befehle sinnvoll verwendest - und ich wäre enttäuscht, wenn Du damit nicht am Ende gewinnst.


    Wer lieber mehrdimensionale Arrays oder 16 Bit Werte sortieren möchte, kann das gerne tun.
    Die Aufgabenstellung dieser Compo ist aber eben eine andere - und hat durchaus auch einen praktischen Nutzen: Man denke z.B. an die Sortierung von Y-Werten für einen Sprite-Multiplexer.
    Dass hier nicht unbedingt Quicksort & Co zum Einsatz kommen, sondern simplere Methoden, ist dabei durchaus beabsichtigt.
    Es wurde ja auch schon positiv angemerkt, dass hier sogar Programmieranfänger mitmachen können.
    Wem das zu popelig ist, muss ja nicht mitmachen.
    Ich denke schon, dass die Beschäftigung mit dieser Thematik (auch oder sogar gerade in dieser einfachen Form), dem ein oder anderen Spaß und vielleicht neue Erkenntnisse bringt. Immerhin gibt es jetzt nach über einem Jahr endlich mal wieder eine ASM-Compo.


    Allerdings finde ich es sehr schade, dass das von einigen hier nicht einfach akzeptiert werden kann, sondern schnell rumgemeckert wird. Da wird sich über die Wortwahl Messung vs Zyklenzählen beschwert oder eben die Primitivität der Aufgabenstellung kritisiert.


    Ich kann nachvollziehen, weshalb Roland sich das nicht antun wollte und bereue es auch schon ein bisschen, dass ich es in die Hand genommen habe. Nochmal mache ich das nicht. Viel Spaß (und ein dickeres Fell, als ich es zur Zeit habe) wünsche ich schonmal demjenigen, der die nächste ASM-Compo ausrichtet.

    Ich hab's jetzt mal mit der Bubble-Sort-Methode versucht und nach einigen Fehlschlägen auch sauber zum Laufen bekommen:


    65 Bytes; Zeiten zwischen fast nix (~1/60 Sek.) und im Worst Case 189/60 Sek., also 3:15 Sek.. Einschaltmeldung braucht 79/60, 1:32 Sek..


    Wär' schön, wenn noch jemand mal Zwischenergebnisse postet, um zu sehen, wo man sich 'hinkämpfen' muss :whistling: . Ich geh' schon mal Takte suchen...


    Ansonsten nochmal: Danke, YPS, für die interessante und lehrreiche Aufgabe :zustimm: .


    Große Hoffnung mache ich mir aber eh nicht, weil da bestimmt irgendwann 'so Leute' mit komischen Sachen aus dem Gebüsch kommen :guenni::D .



    Nebenfrage: Wie müsste denn eine Zahlenkolonne für einen "Average Case" aussehen? Gibt's da was? Einfach abwechselnd größer/kleiner?

    Zitat von Hexworx

    Nebenfrage: Wie müsste denn eine Zahlenkolonne für einen "Average Case" aussehen? Gibt's da was? Einfach abwechselnd größer/kleiner?


    Es gibt ja viele Webseiten, welche nicht nur die Algorithmen erklären, sondern auch animiert deren Funktionsweise veranschaulichen.
    Hier die eine, die ich gut finde:
    https://www.cs.usfca.edu/~gall…ation/ComparisonSort.html


    Dort sieht man auch schön, wie eine Zufallsverteilung aussehen kann. Wenn du selbst die 256 Bytes zufällig erzeugen willst (ja auch musst für Dein Tool, wenn du die 100 Testcases simulieren willst), könnte man ein Cocktail z.B. aus Rauschgenerator, Timer & co, evt. auch Joystick Abfrage als Seed nehmen.

    Zitat von syshack

    wenn du die 100 Testcases simulieren willst),

    YPS: Ich hatte 100 Durchgänge verstanden, was falsch ist, im ersten Posting steht ja "4 Durchgänge mit 256 Daten".


    Weiter unten steht aber:

    Zitat von YPS

    Jedes Sortierprogramm muss dieselben 100 verschiedene (Euch unbekannten) Datensätze als Ausgangssituation verarbeiten. Alle Durchgänge werden dabei in einer "jungfräulichen" Speicherbelegung ausgeführt, auch das Sortierprogramm wird jedes mal neu in den Speicher bei $C000 geladen, so dass es sich jedes mal wie beim ersten mal verhält.

    Jetzt bin ich verwirrt: 100 oder 256 Bytes müssen sortiert werden? :nixwiss:

    100 Durchläufe mit je 256 Bytes; damit die Auswirkungen des Zufalls auf die Algorithmen abgemildert werden.
    EDIT: Und das scheint sich alles auf Durchgang 4, also den mit Zufallsdaten, zu beziehen.

    Zitat von syshack

    Es gibt ja viele Webseiten, welche nicht nur die Algorithmen erklären


    ...die kenne ich jetzt schon fast alle... :böse . Nur :blah! und nix für unser Assembler verwertbares :argue . Gut, Abschreiben wollte ich eh' nicht.


    Zitat von syshack

    Hier die eine, die ich gut finde:
    https://www.cs.usfca.edu/~galles/visuali…arisonSort.html


    Dort sieht man auch schön, wie eine Zufallsverteilung aussehen kann.


    Danke, sys. Schöne Seite.


    Also grob gesagt: "Average Case": Durchschnittlaufzeit bei Zufallsverteilungen. Dann bau ich mir da mal was.


    Gruß :)

    Zitat von Jotta

    Noch zwei Frage zur Stack-Benutzung: Kann der gesamte Stackbereich ($0100-$01FF) als zur Verfügung stehend angenommen werden (natürlich nur unter Zuhilfenahme von PHA, PLA, etc.)? Darf der Stack-Pointer auf $01FF gesetzt werden (TXS/TSX etc.)?


    Mein Hauptprogramm ruft mit einem JSR $C000 die jeweiligen Sortierprogramme auf - die dann auch gefälligst mit einem RTS nach getaner Arbeit brav zum Hauptprogramm zurückkehren sollen.
    Insofern ist der Stack bereits durch das eine JSR beim Aufruf in Benutzung. Wer möchte, kann zwischendurch mit TXS/TSX etc. am Stack rumspielen, solange der Rücksprung ins Hauptprogramm gewährleistet bleibt. Andernfalls wird das Programm nicht gewertet.


    Zitat von Mac Bacon

    100 Durchläufe mit je 256 Bytes; damit die Auswirkungen des Zufalls auf die Algorithmen abgemildert werden.
    EDIT: Und das scheint sich alles auf Durchgang 4, also den mit Zufallsdaten, zu beziehen.


    In den 100 Datensätzen zu je 256 Bytes werden neben vielen Zufallsverteilungen auch händisch ausgewählte Zusammenstellungen enthalten sein (z.B. nach den ursprünglich bei Durchgang 1 bis 3 genannten Schemata) - auch extreme Verteilungen, die eventuell den ein oder anderen Algorithmus an seine Grenzen bringen...

    Zitat von Hexworx

    Also grob gesagt: "Average Case": Durchschnittlaufzeit bei Zufallsverteilungen. Dann bau ich mir da mal was.


    Naja, wenn du es wirklich übertreiben willst, kannst Du ja messen, wie "gut" eine Zufallsverteilung ist.
    Das kann man ja mit Statistik messen. Meine Kenntnisse sind aber ziemlich eingerostet. Wäre aber trotzdem interessant, die 100 Datensätze oder eigene entsprechend beurteilen zu können.


    Was die Erzeugung der (eigenen) 100 oder mehr Zufallsdatensätze erzeugen angeht: Sowas würde ich direkt auf dem PC mit einer Hochsprache (oder auch in BASIC V2) oder (man steinige mich jetzt) in Excel machen (siehe Beilage).
    In Excel hat man 100 Datensätze in 5 Minuten erstellt mit der Formel =GANZZAHL(ZUFALLSZAHL() * 256). Man muss sie "nur noch" speichern und mit einem Tool in den ScreenRAM des C64 pro Durchlauf einen Datensatz laden.... :whistling:


    100 Recordsets Random 0-256.zip

    Zitat von syshack


    Naja, wenn du es wirklich übertreiben willst, kannst Du ja messen, wie "gut" eine Zufallsverteilung ist.
    Das kann man ja mit Statistik messen. Meine Kenntnisse sind aber ziemlich eingerostet. Wäre aber trotzdem interessant, die 100 Datensätze oder eigene entsprechend beurteilen zu können.


    Oder http://www.wolframalpha.com/in…=100+random+numbers+0-255 füttern. :whistling:

    Zitat von syshack

    Man muss sie "nur noch" speichern und mit einem Tool in den ScreenRAM des C64 pro Durchlauf einen Datensatz laden....


    Passt doch locker ins BASIC-RAM :zustimm: . Krieg' ich schon hin ;) .


    Zitat von oobdoo

    Oder http://www.wolframalpha.com/input/?i=100…m+numbers+0-255 füttern.


    ...IS' JA KOMISCH... :picard: - ist doch alles auf ENGLISCH... :schreck!:


    Aber geil, Danke. Muss man sich aber erst anmelden zum downloaden der Daten.



    Zitat von enthusi

    Ein kleiner Test hier hat auch 41 Bytes


    :)

    Zitat von Hexworx

    Passt doch locker ins BASIC-RAM :zustimm: . Krieg' ich schon hin ;) .


    Ja, stimmt, habe mir das zu kompliziert angedacht. Ich weiss ja nicht wie gut die BASIC V2 RND() Funktion ist, aber ich habe mal einen Einzeiler gebifft:

    Code
    1. for i = 1024 to 1280 : poke i, int(256 * rnd(1)) : next


    Subjektiv erscheint mir aber, dass es eher viele invertierte Zeichen erzeugt.


    Bei genauerer Überlegung finde ich den Weg mit gespeicherten Werten doch wieder besser, weil man nur so die Verbesserungen am Sortiercode nachvollziehen/reproduzieren kann und sich sicher sein kann, dass man nicht per Zufall zu viele optimale Verteilungen erwischt hat.

    Gut, dass da noch die Tabelle mit den Ursprungsplätzen mitsortiert werden muss, sonst wäre Daybyters Lösung wohl schon das Ergebnis.


    Da gibt es noch so ne Sache beim Sortieren, wie gut die ursprüngliche Reihenfolge erhalten bleibt, weiß jetzt nicht, wie das heißt. Angenommen, man sortiert eine Liste von Namen erst nach 2. Buchstaben, dann nach erstem Buchstaben. Anschließend kann im 2. Buchstaben Kraut und Rüben sein, oder der 2. Buchstaben bleibt innerhalb des ersten sortiert.


    Sollte hier imho keine Rolle spielen.


    Konsequenz ist aber, dass es verschiedene gültige Index-Tabellen gibt

    Ich will nicht auf der Zyklen statt Stoppuhr-Idee rumreiten, aber es wäre zur Auswertung vermutlich sinnvoll, einen kurzen Code zu schreiben (oder eine genaue Anleitung), wie die Geschwindigkeit zu bestimmen ist. Wenn 2 Leute den selben Algorithmus implementieren und der eine dann noch 2 Wochen lang den letzten Zyklus daran optimiert, fände ich es unfair, wenn beide auf dem selben Platz landen, weil der Unterschied in der Messungenauigkeit untergeht. Vielleicht hat einer Bock, eine Messroutine zu schreiben, die dann die Referenz für die Auswertung der Geschwindigkeit ist?