ExtraDix

Der Sortieralgorithmus ExtraDix ist eine Erweiterung von Radixsort (Extended raDix). Er ist somit nicht-vergleichsbasiert, stabil und bietet zudem die Möglichkeit indirekt zu sortieren, also zunächst die korrekte Reihenfolge festzustellen und erst dann die Datensätze zu verschieben. Der Algorithmus ist sehr schnell, es gibt weder einen Best- noch einen Worst-Case, der Zeitaufwand für Sortierungen steigt linear mit der Anzahl der Datensätze an und er kann auf alle gängigen Datentypen angewendet werden. ExtraDix wurde 2009 von Jürgen D. Henning entwickelt; eine Pseudocode- und eine C-Version wurden unter die GPL gestellt und können von BerliOS bezogen werden.

Übrigens: Die PlusPedia ist NICHT die Wikipedia. Wir sind ein gemeinnütziger Verein, PlusPedia ist werbefrei. Wir freuen uns daher über eine kleine Spende!

1 Funktionsweise

Klassischerweise wurde Radixsort eingesetzt, um Lochkarten zu sortieren. Hierzu wurde eine Lochkartensortiermaschine zunächst so eingestellt, dass sie die Einerstellen abfragte und die Lochkarten auf zehn Schächte verteilte. Wenn der Stapel abgearbeitet war, wurden die Lochkarten bei Schacht Null beginnend eingesammelt. Dann wurde die Sortiermaschine auf die Zehnerstellen eingestellt und der Sortiervorgang wiederholt. Das Verteilen und Einsammeln wurde solange wiederholt, bis nach der höchstwertigen Stelle sortiert war und somit auch alle Lochkarten. Sollte die Sortierung nicht aufsteigend sondern absteigend sein, dann sammelte man die Lochkarten jeweils in umgekehrter Reihenfolge ein. Bei der Sortierung von Lochkarten arbeitet Radixsort mit 10 verschiedenen Symbolen, nämlich den Ziffern 0 bis 9.

ExtraDix arbeitet fest mit den 256 verschiedenen Symbolen, die man durch ein Byte darstellen kann.

Sollen etwa Zeichenketten sortiert werden, so liefert ExtraDix vernünftige Ergebnisse, weil die Interpretationen der Byte-Inhalte sinnvoll in Listen stehen wie etwa der ASCII-Tabelle. Beinhaltet ein Byte etwa die Ziffer Null, dann muss der Datensatz in den 48zigsten Eimer befördert werden, beinhaltet es ein 'A', dann kommt er in den mit der Nummer 65. Das Verfahren schaut also nicht darauf, was mit dem Inhalt gemeint ist, sondern interpretiert den Inhalt des Byte als positive Zahl zwischen Null und 255.

ExtraDix hebt also die Unterscheidung von Adressen und Daten auf, denn der Inhalt des aktuell betrachteten Byte stellt die Adresse des Zieleimers dar!

Da die Sortierschlüssel im Allgemeinen mehrere Bytes lang sind, wird folgende sprachliche Unterscheidung gemacht: Unter einem Sortierdurchgang wird die Sortierung nach einem einzigen Byte aus dem Sortierschlüssel verstanden; es wird also bei allen Datensätzen lediglich dieses eine Byte betrachtet. Unter einem Sortiervorgang wird die Sortierung der ganzen Datensätze nach einem kompletten Sortierschlüssel verstanden. Besteht der Sortierschlüssel aus einer vorzeichenlosen ganzen Zahl (normalerweise aus vier Byte bestehend), dann werden vier Sortierdurchgänge gemacht, um den Sortiervorgang durchzuführen.

2 Die simulierte Sortiermaschine

Für die Umsetzung von ExtraDix wird eine Sortiermaschine mit 256 Schächten simuliert. Da die Datensätze beim Einsammeln der Datensätze in der Reihenfolge entnommen werden müssen, in der sie in den jeweiligen Schacht einsortiert wurden, werden hierfür FIFOs benutzt.

Sollen etwa 1.000 Datensätze sortiert werden, müsste jeder FIFO so groß sein, dass im Zweifelsfalle alle Datensätze in ihm gespeichert werden könnten. Dieses Problem wird umgangen, indem eine zentrale Speicherverwaltung verwendet wird und sich die 256 FIFOs die 1.000 Speicherstellen teilen. Zu Beginn eines Sortiervorgangs wird entsprechend der Anzahl der Datensätze dynamisch entsprechend viel Speicher vom Betriebssystem angefordert.

Bei Radixsort wird für jedes Byte des Schlüssels jeweils der ganze Datensatz (Lochkarte) bewegt. Wenn man wahlfreien Zugriff auf die Eingabedatensätze hat, ist dies nicht notwendig. Es genügt, wenn man in dem FIFO lediglich die Datensatznummer einträgt. Und in welches FIFO die Datensatznummer eingetragen werden soll, ergibt sich jeweils ganz einfach aus dem Wert, den das aktuell betrachtete Byte des Sortierschlüssels hat.

Intern sind die FIFOs als verkettete Liste angelegt, und die Verwaltung dieser Liste erfolgt über ein Array, in dem jeweils auf das erste und auf das letzte Element eines FIFOs verwiesen wird; in den Elementen des FIFO findet man die Datensatznummern der Eingabedatensätze. Hierdurch lässt sich ein einfacher und sehr schneller Zugriff realisieren.

Klassischerweise werden bei Radixsort nach einem Sortierdurchgang die einzelnen Datensätze eingesammelt, um sie anschließend dem nächsten Sortierdurchgang zuzuführen. Da eine per Software realisierte Sortiermaschine nur etwas Speicherplatz kostet, arbeitet ExtraDix mit zwei FIFO-Registern und sortiert die Daten beim Einsammeln gleich in den anderen Satz von FIFOs. Diese Register werden abwechselnd als Ziel benutzt.

3 Sortierung nach natürlichen Zahlen

Auf PCs wird eine natürliche Zahl durch vier Byte repräsentiert, wobei das erste Byte das niederwertigste ist und das vierte Byte das höchstwertigste. Die Sortierung beginnt beim niederwertigsten Byte, also dem ersten.

Zu Beginn eines Sortiervorgangs werden alle Datensätze in das erste FIFO des zweiten Registers eingetragen, wodurch sie in der Originalreihenfolge für den ersten Sortierdurchgang verfügbar werden.

Im ersten Sortierdurchgang wird jeweils das niederwertigste Byte des Sortierschlüssels betrachtet. Bei jedem Sortierdurchgang werden der Reihe nach die FIFOs des anderen Registers ausgelesen, in diesem Fall stehen alle Referenzen im ersten FIFO. Es wird die Originalposition des Datensatzes in den Eingabedaten aus dem FIFO ausgelesen, ein Zeiger auf diesen Datensatz berechnet und das niederwertigste Byte des Schlüssels gelesen. Der Inhalt des Bytes gibt die Nummer des Ziel-FIFO an, wohin die Datensatznummer geschrieben wird.

Es folgen noch drei weitere Sortierdurchgänge. Abschließend werden die FIFOs der Reihe nach ausgelesen, und man bekommt die Datensatznummern in der Reihenfolge, wie sie einer korrekten Sortierung entsprechend anzuordnen wären. Die Datensätze können entweder in dieser Reihenfolge in ein Zielarray eingetragen werden, oder mit ein wenig Mehraufwand (zwei Integerhilfsarrays um sich zu merken, wohin ein Datensatz verschoben wurde, weil sein Platz für das Ergebnis benötigt wurde) kann man die Datensätze auch innerhalb des Eingabearrays umkopieren.

Es ist einsichtig, dass der Zeitzuwachs linear ist, denn jedes Byte der Sortierschlüssel wird exakt nur ein einziges Mal betrachtet / bearbeitet und die Anzahl der Bytes steigt linear mit der Anzahl der Datensätze.

Die Sortierung von natürlichen Zahlen, die aus einem, zwei oder acht Bytes bestehen, erfolgt sinngemäß.

4 Sortierung von vorzeichenbehafteten ganzen Zahlen

Für ganze Zahlen, die in einem Byte gespeichert werden können, wurde folgende Definition festgelegt: Man zeichne einen Kreis und unterteile diesen in 256 Sektoren, wobei ein Sektor nach oben zeigt und die Null repräsentiert. Nun nummeriert man die Sektoren fortlaufend binär. Anschließend trägt man die Bedeutung der Sektoren ein. Die binäre 00000001 entspricht dann der dezimalen 1, und die binäre 11111111 entspricht der dezimalen -1; die binäre 00000010 entspricht der dezimalen 2, und die binäre 11111110 entspricht der -2 und so weiter. Auf der einen Seite des Kreises hat man anschließend die positiven Zahlen von 0 bis 127 und auf der anderen Seite die -1 bis zur -128. Das System für 2-, 4- oder 8-bytige ganze Zahlen ist entsprechend aufgebaut. Für alle diese Zahlen gilt, ist das höchstwertige Bit eine Eins, dann ist die Zahl negativ.

Will man nach ganzen Zahlen sortieren, muss man den Algorithmus etwas abwandeln. Es wird bei jeder Betrachtung eines Schlüssels das Vorzeichenbit bestimmt, und bei negativen Zahlen wird die FIFO-Nummerierung umgekehrt. Die Daten werden also entsprechend dem Abstand, den sie von Null haben, in die FIFOs einsortiert. Dieser Effekt, dass anscheinend nicht zusammengehörige Referenzen im gleichen FIFO gespeichert werden, wird bei der Bearbeitung des höchstwertigen Byte beseitigt, wenn nach dem Vorzeichen sortiert wird.

Entsprechend der Bytezahl des Schlüssels erfolgen jetzt gegebenenfalls mehrere Sortierdurchgänge. Wenn nach dem höchstwertigsten Byte sortiert wird, wird die Sortierung aufgespalten. Im ersten Teildurchgang wird das Vorzeichenbit ausmaskiert, aber sein Wert wie zuvor auch bei der FIFO-Nummerierung berücksichtigt. Und abschließend wird nach dem Vorzeichen sortiert, wodurch man die Datensätze trennt, die zuvor nicht in die gleichen FIFOs zu gehören schienen.

Der Zeitbedarf zur Sortierung von vorzeichenbehafteten ganzen Zahlen ist etwas höher als der für natürliche Zahlen, aber auch hier steigt der Zeitbedarf linear.

5 Sortierung von Bytefolgen

Bei Bytefolgen / Zeichenketten ist die Konvention, dass das erste Byte das höchstwertige Zeichen enthält. ExtraDix fordert, dass alle Bytefolgen nominell gleich lang sind, und beginnt die Sortierung mit dem letzten Byte.

In C gilt die Konvention, dass Strings immer mit einem Nullbyte abgeschlossen werden; es darf also beliebiger Datenmüll hinter diesem Nullbyte stehen. Da Extradix Bytefolgen sortiert und nicht Strings, kann hier scheinbar der Effekt auftreten, dass die Sortierung nicht stabil erscheint; dies liegt daran, dass hinter dem Nullbyte nach zufälligem Datenschrott sortiert wurde, der für den Nutzer nicht direkt sichtbar ist.

Ein praktischer Nebeneffekt ergibt sich dadurch, dass das Leerzeichen in der ASCII-Tabelle vor den Ziffern und Buchstaben steht. Werden nämlich Strings mit Wortfolgen sortiert, steht „Der artige“ vor „Derartige“, was der normalen lexikalischen Betrachtung entspricht.

Da jedes Byte aus jeder Bytefolge nur ein einziges Mal betrachtet wird, ergibt sich wieder die sehr hohe Sortiergeschwindigkeit zusammen mit einem linearen Zeitzuwachs.

6 Sortierung nach Gleitkommazahlen

Gleitkommazahlen (float und double in C) umfassen die Mantisse und ihr Vorzeichen sowie den Exponenten und sein Vorzeichen. Je nach gewählter Genauigkeit ist die Anzahl der Bits, die zur Mantisse bzw. zum Exponenten gehören, unterschiedlich. Hieraus ergibt sich, dass sich die Sortierdurchgänge teilweise unterscheiden (Maskierung von Bits, Vorzeichenbehandlung). Auf die Einzelheiten soll hier nicht eingegangen werden, diese kann man dem kommentierten Pseudo-Code bzw. dem C-Programm entnehmen.

7 Speicherplatzbedarf

Für die Sortierung werden zwei FIFO-Verwaltungen benötigt. Jede FIFO-Verwaltung hat 256 Einträge, die jeweils aus zwei Integerzahlen bestehen, nämlich das erste Element des FIFOs und das letzte Element. Eine normale Integerzahl hat 4 Bytes, also benötigt eine FIFO-Verwaltung 2 kBytes. Für beide FIFO-Verwaltungen werden insgesamt 4 kByte benötigt, egal wie viele Datensätze sortiert werden sollen.

Jeder FIFO-Eintrag besteht aus der Originalposition des Datensatzes und der Verkettung zum nächsten Element des gleichen FIFO. Ein einzelner Eintrag hat 8 Bytes; da zwei FIFO-Register verwaltet werden, ergibt sich der dynamisch benötigte Speicherplatz bei n Datensätzen zu S = n * 8.

Soll die Sortierung nicht in ein Zielarray hinein erfolgen, sondern innerhalb des Arrays, werden zwei Hilfsarrays der Länge n benötigt, in denen gespeichert wird, wohin ein Datensatz umkopiert wurde, als sein Speicherplatz zum Schreiben des Ergebnisses benötigt wurde.

Zusammenfassend kann man sagen, dass der Speicherplatzbedarf recht moderat ausfällt.

8 Verarbeitungsgeschwindigkeit

Bei jedem Sortierdurchgang müssen die 256 FIFOs des aktuellen Registers zurückgesetzt werden, und am Ende des Sortierdurchgangs müssen die 256 FIFOs des aktuellen Registers ausgelesen werden. Dieser Aufwand muss unabhängig von der Anzahl der zu sortierenden Datensätze betrieben werden.

Unabhängig vom Datentyp des Sortierschlüssel gilt, dass jedes Byte vom Sortierschlüssel eines jeden Datensatzes nur ein einziges Mal betrachtet wird; Ausnahmen bilden nur Datentypen mit Vorzeichen. Beim Eintragen in ein FIFO und beim Auslesen wird jeweils eine if-Abfrage gemacht sowie einige triviale Berechnungen. Der Aufwand pro Byte des Sortierschlüssels ist also extrem gering, und der zeitliche Zuwachs beim Sortieren ist linear. Aus dem Ablauf des Algorithmus ergibt sich zudem, dass der zeitliche Aufwand für eine Sortierung völlig unabhängig von einer Vorsortierung ist. Es gibt also weder einen Worts-Case noch einen Best-Case, und bei der Sortierung nach einem bestimmten Datentyp dauert die Abarbeitung von jedem Schlüssel exakt gleich lange.

Um einen Vergleich mit Quicksort durchführen zu können, wurde eine Datei mit einer Million Datensätzen erzeugt; die Datensätze hatten eine Länge von 54 Byte und enthielten quasi zufällige Daten in den gängigen Grundtypen. Als Testrechner wurde ein PC mit 1,8 GHz verwendet, und die Tabelle mit den Testdaten wurde vor jedem Sortiervorgang in den Arbeitsspeicher geladen.

Die Implementierung von Quicksort wurde entsprechend diesem Pseudocode in C realisiert. Da die Sortierzeit bei Quicksort von einer Vorsortierung abhängt, haben diese Kurven keinen gleichförmigen Verlauf; Ausreißer wurden gelöscht und zugunsten von Quicksort interpoliert. Da die benötigte Zeit bei ExtraDix linear mit der Anzahl ansteigt und bei Quicksort mit n*ln(n), wird der zeitliche Vorteil von ExtraDix bei steigenden Anzahlen immer größer.

Es bleibt noch die Frage zu beantworten, ab welcher Anzahl von Datensätzen der Einsatz von ExtraDix lohnend erscheint. Für die beiden folgenden Diagramme wurden in Hunderter-Schritten bis zu 2.000 Datensätze sortiert und die Zeiten in Mikrosekunden gemessen. Schon ab ein paar hundert Datensätzen spielt der Überhang, der für die FIFO-Verwaltung notwendig ist, keine wesentliche Rolle mehr. Von Ausnahmesituationen abgesehen kann ExtraDix generell als Sortieralgorithmus der Wahl angesehen werden.

9 Aufruf der ExtraDix Funktion

Die Sortierfunktion ExtraDix ist reentrant-fähig. Sie hat nur einen Aufruf-Parameter und zwar einem Zeiger auf eine Struktur des Typs ED_SortInfo.

Die Struktur hat folgende Komponenten:

 int   SortOrder;                      // Sortierrichtung
 int   ColWidth;                       // Breite des Schlüssels
 int   ColType;                        // Typ des Schlüssels
 int   ColStart;                       // Byteposition, wo der Schlüssel beginnt
 int   ColEnd;                         // Bytepositon, letztes Byte des Schlüssel
 int   NumLines;                       // Anzahl der zu sortierenden Datensätze
 int   LineSize;                       // Länge eines Datensatzes
 char* Source;                         // Zeiger auf die Eingabedatensätze
 char* Dest;                           // Zeiger auf Speicherplatz für das Ergebnis

Wird ExtraDix etwa Teil einer dynamischen Library, dann wird der Sourcecode übersetzt, bevor bekannt sein kann, wie die zu sortierenden Datensätze aufgebaut sind. Der Aufruf musste also so gestaltet werden, dass er für jede Sortieraufgabe geeignet ist.

Die zu sortierenden Daten befinden sich im Arbeitsspeicher an der durch Source angegebenen Position. Da Datensätze im Allgemeinen eigene Struktur-Definitionen haben, die ExtraDix natürlich nicht kennen kann, wird als neutrale Lösung ein Zeiger auf Bytes verwendet. Jeder Datensatz hat die Länge LineSize, und es sind insgesamt NumLines Zeilen, die sortiert werden sollen.

Da sich ExtraDix nicht um die Inhalte der Datensätze kümmert, genügt es zu wissen, wo sich der Sortierschlüssel innerhalb des Datensatzes befindet und mit welcher Variante des Algorithmus gearbeitet werden soll. Die Variante wird mittels ColType ausgewählt. Als Typen sind Strings möglich, vorzeichenlose ganze Zahlen, vorzeichenbehaftete ganze Zahlen und Gleitkomma-Zahlen mit zwei verschiedenen Genauigkeiten. Da sich auf verschiedenen Rechnern, Compilern und Programmiersprachen die Interpretationen unterscheiden, muss zusätzlich angegeben werden, wie viele Bytes der Schlüssel umfasst, an welcher Stelle im Datensatz der Schlüssel beginnt und an welcher Stelle das letzte Byte des Schlüssels steht.

Über SortOrder, das die Werte ED_ASCEND oder ED_DESCEND annehmen kann, wird eingestellt, ob das kleinste Element am Anfang der Ergebnisliste stehen soll oder ob absteigend sortiert werden soll.

Die letzte Komponente in der Struktur ist Dest, der Zeiger auf die Position im Arbeitsspeicher, wo das Ergebnis gespeichert werden soll. Hat dieser Zeiger den Inhalt NULL, dann werden die Datensätze innerhalb der Eingabedaten umgestellt. Hat Dest einen hiervon abweichenden Wert, wird das Ergebnis ab der angegebenen Adresse abgespeichert. Es liegt in der Verantwortung des Nutzers, dass hierdurch keine Konflikte entstehen.

Die Angaben, wo sich der Schlüssel innerhalb des Datensatzes befindet, sind etwas kompliziert. Der Grund hierfür ist, dass die Prozessoren nicht jeden Datentyp an beliebiger Adresse erlauben. Beispielsweise müssen Integerwerte mit vier Byte Länge immer an einer Adresse anfangen, die ohne Rest durch vier teilbar ist; liegt die Adresse an einer anderen Stelle, wird das Programm abgebrochen. Damit dies nicht passiert, fügt der Compiler Füllbytes in den Strukturen ein und jeder Compiler macht dies gegebenenfalls anders. Dieses Einfügen von Bytes wird Padding genannt. Damit Programme, die ExtraDix nutzen, ohne Änderungen auf unterschiedlichen Plattformen laufen können, sollte man die Komponenten der Struktur soweit möglich vom Compiler bestimmen lassen. Beispiele hierfür finden sich in der Testsuite.

10 duale Lizenz

Die Wirkungsweise des Algorithmus wurde mittels Pseudocode beschrieben und in ein C-Programm umgesetzt. Beides wurde unter die GPL gestellt. Möchte jemand ExtraDix nutzen und auch an Dritte weitergeben, ohne sein eigenes Programm unter die GPL zu stellen, so kann er mit dem Autor einen individuellen Lizenzvertrag abschließen.

So, wie der Autor eines Romanes sein geistiges Eigentum nicht dadurch verliert, dass jemand sein Werk kopiert, den Darstellern andere Namen gibt oder das Werk in eine andere Sprache übersetzt, so wird auch das geistige Eigentum an diesem Code von ExtraDix betrachtet: Jede Übersetzung des Pseudocodes in eine natürliche Sprache oder in eine Programmiersprache, inklusive ihrer Kompilate, muss selbst wieder unter die GPL gestellt werden.

Werden Programme mit ExtraDix verbunden, durch Einbindung von Quelltext, Verlinkung mittels einer statischen oder dynamischen Library oder durch Einsatz in einem Server-Prozess oder einem Betriebssystem, die die Funktionalität von ExtraDix zur Verfügung stellen, so muss dieses Programm gleichfalls unter die GPL gestellt werden, falls Kopien an Dritte weitergegeben werden.

11 Weblinks

• Radixsort auf linux-related.de
• Radixsort Implementierung von Pierre Terdiman (engl.)
• C++ Implementierung von Radixsort für Gleitkommazahlen (engl.)

13 Andere Lexika

• Dieser Artikel wurde in der Wikipedia gelöscht.

---

---

• Löschdiskussion bei Wikipedia

Erster Autor: JDHenning angelegt am 12.01.2010 um 13:13, weitere Autoren: Erdbeerquetscher, Levin, SPKirsch, Crazy1880, Mushushu, WOBE3333, Papa1234