ASM-Compo #4: Sortieren

YPS · Oct 8th 2015

Quote from 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.

enthusi · Oct 8th 2015

Oh, dann verzeih.
Es war nicht boese gemeint
Tatsaechlich finde ich, dass so eine Compo 'unter uns' viel weniger Erklaerungen braucht.
Was gemeint ist, sollte ja klar sein.

daybyter · Oct 8th 2015

Tut mir leid, wenn Du Dich über die Vorschläge ärgerst. Es war gut gemeint. Ich freue mich über Aktionen, welche die Grundlagen der Softwareentwicklung beleuchten und weiss Deine Bemühungen zu schätzen.

spider-j · Oct 8th 2015

YPS: Jo, danke für die Erläuterung. Ich bin dabei

syshack · Oct 8th 2015

Einfach einschicken bis zur Deadline genügt, oder?
Also sich nicht vorab anmelden, oder?

YPS · Oct 8th 2015

Quote from syshack

Einfach einschicken bis zur Deadline genügt, oder?
Also sich nicht vorab anmelden, oder?

Ja, Einsenden reicht. Es gibt keinen Anmeldeprozess.

Hexworx · Oct 8th 2015

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 . Ich geh' schon mal Takte suchen...

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

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

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

syshack · Oct 8th 2015

Quote from 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.

Jotta · Oct 8th 2015

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.)?

syshack · Oct 8th 2015

Quote from 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:

Quote from 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?

Mac Bacon · Oct 8th 2015

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.

Hexworx · Oct 8th 2015

Quote from syshack

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

...die kenne ich jetzt schon fast alle... . Nur und nix für unser Assembler verwertbares . Gut, Abschreiben wollte ich eh' nicht.

Quote from 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ß

YPS · Oct 8th 2015

Quote from 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.

Quote from 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...

syshack · Oct 8th 2015

Quote from 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....

100 Recordsets Random 0-256.zip

oobdoo · Oct 8th 2015

Quote from 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.

enthusi · Oct 8th 2015

Ein kleiner Test hier hat auch 41 Bytes

Hexworx · Oct 9th 2015

Quote from 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 . Krieg' ich schon hin .

Quote from oobdoo

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

...IS' JA KOMISCH... - ist doch alles auf ENGLISCH...

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

Quote from enthusi

Ein kleiner Test hier hat auch 41 Bytes

syshack · Oct 9th 2015

Quote from Hexworx

Passt doch locker ins BASIC-RAM . 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

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.

Hoogo · Oct 9th 2015

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

Claus · Oct 9th 2015

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?