Radix Sort in Haskell

[VirX]

Hi, ich wollte mal etwas fragen. Ich muss (für die Uni :c ) in Haskell den Radix Sort Algorithmus implementieren - ich habe nur überhaupt keine Ahnung wie?

Hier ist nicht rein zufällig jemand, der die Implementierung zur Hand hat, oder?

[Crush]

Ich habe sowas ähnliches mal für einen Cruncher als Speed-up-buffer in Assembler programmiert. Damals war das der erste Schritt zur Kompressionsbeschleunigung bevor LHA und Konsorten aufkam. Allerdings war der Radix da nicht ausschlaggebend, sondern alle gleichen Vorkommnisse mußten aneinander sortiert werden um schnellstmöglichst gleiche Byte-Folgen zu finden.

Beim Radix-Sort wird halt noch beim Sortieren Rücksicht auf den Radix als Sortierkriterium genommen.

In C gibt´s hier einen Source dazu: http://www.cubic.org/~submissive/sourcerer/radix.htm#code

der Folgende ist dasselbe nur mit optimiertem Code http://www.cubic.org/~submissive/sourcerer/download/radix_ar_2001.c

Im Kurzformat kann man das so erklären:

Alles Bytes werden gezählt. Sagen wir es kommt 5x die 0xfa vor, dann wird in einem Array (nennen wir es A1) 5 Plätze für die Offsets reserviert (ab Datenstart - es muß also alles chronologisch im Speicher vorliegen).

Hier schreibt man dann die Offsets der Byte-Positionen rein.

Es gibt dann eine Einsprungstabelle (A2), bei der die Offset-Startpositionen eingefügt werden. (einfach Byte*Häufigkeit*Offsetgröße rechnen). Dann war noch ein Trick dabei das die Häufigkeiten aufeinanderaddiert werden, aber das siehst Du wohl aus dem Source genauer heraus.

Beim Radix-Sort wird dafür nicht die Vorkommnisse der Bytes alleine, sondern des Radix dafür verwendet. Als Ergebnis erhält man alle Werte in schön sortierter Reihenfolge. Eigentlich ist das aber gar kein Radix in diesem Source, sondern es wird einfach der zu sortierende Wert um x*8 bit nach rechts rotiert und dann 8 Bit ausmaskiert. Es wird also nach MSB(yte) oder LSB(yte) von lo- oder hi-word sortiert. Das hat für mich persönlich eigentlich nur Sinn bei sortieren von Daten Endian-fremder Computer. (Little/Big-Endian, alles klar?!?!) Vielleicht hat das ja noch einen anderen Sinn, doch der leuchtet mir auf den ersten Blick nicht ein. Die Sortierung ist schneller als Quicksort wenn sie richtig programmiert ist und ist deshalb vor allem für Realtime-Anwendungen ideal geeignet, wenn die Daten ein Überschaubares Volumen haben.

Da die Offsets am Ende alle bekannt sind, muß man nur noch die nach der Reihenfolge aller Offsets von A1 sortieren - fertig! Aber eigentlich braucht man das auch nicht mehr, weil man aus A1 direkt ablesen kann welche Bytes wie oft vorkommen, also könnte man A1 selber schon als sortiertes Array betrachten -> so hab ich das beim Cruncher jedenfalls gemacht. Und somit den Powerpacker und den Imploder vom Amiga damals um ein Vielfaches in der Kompressionsgeschwindigkeit und auch in der -leistung überholt - das war Rekordverdächtig.

<FONT COLOR="#a62a2a" SIZE="1">[ 18. Dezember 2001 21:57: Beitrag 8 mal editiert, zuletzt von Crush ]</font>