[1] Weil das Ordnen wie auch das Sortieren Bestandteile der besprochenen alten wie neuen Verfahren sind, wird imText mit „Ordnungs-/Sortieralgorithmen“ darauf verwiesen.
8
APPENDICES I AND II:
A
COMPARISON OF
ORDERING AND SORTING ALGORITHMS
1 INHALTSVERZEICHNIS...............................................................................................................................................
2 EINLEITUNG....................................................................................................................................................................
3 „HURRYORDER“, EIN NEUER ANSATZ..................................................................................................................
3.1 Sortieren mit einem SORTIER-Algorithmus...........................................................................................
3.2 Ordnen mit einem ORDNUNGS-Algorithmus...........................................................................................
4 BEWERTUNG VON ORDNUNGSALGORITHMEN................................................................................................
5 DIE ZWEI TYPEN VON HURRYORDER....................................................................................................................
6 „HURRYORDER“ IM VERGLEICH MIT HERKÖMMLICHEN ALGORITHMEN.............................................
6.1 Testresultate.........................................................................................................................................................
6.2 Auswertung.............................................................................................................................................................
7 KURZE ZUSAMMENFASSUNG ÜBER „HURRYORDER“....................................................................................
7.1 Einsatzbereich von „Hurryorder“..............................................................................................................
7.2 Stärken von „Hurryorder“.............................................................................................................................
7.3 Schwächen von „Hurryorder“......................................................................................................................
8 anhang i und ii, ordnungs-/sortieralgorithmen im vergleich
In der Informatik gibt es kaum einen Bereich, der so grundlegend analysiert worden ist, wie das Sortieren und Bestimmen von Objekten aus Datenbanken.
Die rasante Entwicklung der Hardware ermöglicht den Bau immer schnellerer Computer. Letztlich entscheidet aber die Software darüber, wie rationell ein Computer arbeitet. Ein guter Algorithmus mit einem langsamen Computer ist oft leistungsfähiger als ein schneller Computer mit einem schlechteren Algorithmus.
Im Umgang mit grossen Datenmengen ist es von
entscheidender Bedeutung, in möglichst kurzer Zeit die Daten sortieren, ordnen,
oder nach beliebigen Kriterien auswerten zu können. Deshalb hat das Ordnen und
Suchen in Datenbanken nach wie vor eine zentrale Bedeutung in der Informatik.
Ich möchte Ihnen mit dieser kleinen Schrift meinen neuentwickelten Ordnungsalgorithmus vorstellen: „Hurryorder“.
Die Vorzüge von „Hurryorder“ sind folgendermassen zusammenzufassen:
· Schnelle, leistungsfähige und damit kostengünstige Verarbeitung grosser Datenmengen (Sortieren, Ordnen, Auswerten) - zehnmal schneller als herkömmliche Algorithmen!
· Flexibles Gestalten des Ordnungsschlüssels.
· Stabiles Sortieren.
Im folgenden wird dargelegt, was „Hurryorder“ genau ist und was seine unvergleichliche Effizienz ausmacht.
„Hurryorder“ ist ein Algorithmus, mit welchem Daten geordnet werden können. Obwohl die meisten Ordnungs-/Sortieralgorithmen[1] das Wort "SORT" in ihrem Namen enthalten, wurde für „Hurryorder“ bewusst das Wort "ORDER" gewählt.
Ich möchte an dieser Stelle kurz erklären, welcher Unterschied zwischen einem SORTIER- und einem ORDNUNGS-Algorithmus zu machen ist:
Unter „Sortieren“ versteht man allgemein den Prozess des Anordnens einer Menge von gegebenen Objekten in auf- oder absteigender Reihenfolge bezüglich der Wertigkeit der Objekte.
Unter „Ordnen“ versteht man den Prozess des Anordnens einer Menge von Objekten in einer <<wählbaren>> Reihenfolge bezüglich der Wertigkeit der Objekte. In diesem Sinne ist ein Sortieralgorithmus Bestandteil jedes Ordnungsalgorithmus.
Die angewandte Methodik kann allgemein in zwei Kategorien eingeteilt werden. Die eine Kategorie beinhaltet das Anordnen von ‘arrays’ mit wahlfreiem Zugriff, die andere das Anordnen von sequentiellen Dateien. „Hurryorder“ gehört der ersten Kategorie an. „Hurryorder“ ordnet Objekte in ‘arrays’ mit wahlfreiem Zugriff (RAM, Harddisk, Floppydisk)
Für „Hurryorder“ ist also das Anordnen in auf- oder absteigender Reihenfolge, wie es die üblichen Ordnungs-/Sortieralgorithmen praktizieren, absolut nicht zwingend. Die gewünschte Datenordnung lässt sich mit „Hurryorder“ ohne Effizienzeinbusse sehr flexibel gestalten.
Die zwei wichtigsten Kriterien zur Bewertung eines Ordnungs-/Sortieralgorithmus lauten:
· Wie schnell kann der Algorithmus ordnen ?
· Ist der Algorithmus stabil oder nicht stabil ?
Wie schnell ein Ordnungs-/Sortieralgorithmus arbeitet, ist zweifellos von grösster Bedeutung.
Von „Hurryorder“ gibt es zwei Typen. Der Unterschied zwischen den beiden Typen ist, dass der eine stabil ist, der andere nicht.
Der nicht-stabile Hurryorder wird „Hurryorder n.s.“ genannt. Der stabile Hurryorder wird „Hurryorder s.“ genannt.
Da die Arbeitsweise beider Typen im Kern identisch ist, ist auch ihre Leistungskurve nahezu gleich.
Obwohl ein stabiler Algorithmus gegenüber einem nicht-stabilen Algorithmus eigentlich keine Nachteile hat, sind aus folgendem Grund doch beide Typen implementiert worden: Der stabile Algorithmus („Hurryorder s.“) braucht temporär Speicherplatz für jedes zu sortierende Objekt. Das kann ein Problem sein, wenn wenig Arbeitsspeicher vorhanden ist. Wenn es also nicht nötig ist, dass die Objekte stabil sortiert sein müssen, und wenn wenig Speicherplatz vorhanden ist, dann eignet sich der nicht-stabile Algorithmus „Hurryorder n.s.“ besser.
Unter den aufgeführten Testprogrammen der gebräuchlichen Ordnungs-/Sortieralgorithmen liefert „Quicksort“ mit Abstand die besten Resultate.
Der Sortieralgorithmus „Quicksort“ wird allgemein als der Beste zur Zeit verfügbare Sortieralgorithmus betrachtet.
Es ist zu erwähnen, dass „Quicksort“ nicht stabil sortieren kann.
Testcomputer:
Computer 80486 DX2 66Mhz. (internal cache enabled).
Testprogramme:
|
HURRYNS1 |
EXE |
„Hurryorder“ nicht stabil |
16-Bit Comp |
|
32HUNS1 |
EXE |
„Hurryorder“ ident. mit HURRYNS1 aber |
32-Bit Comp |
|
HURRYNS2 |
EXE |
„Hurryorder“ nicht stabil (Adr.far) |
16-Bit Comp |
|
HURRYS1 |
EXE |
„Hurryorder“ stabil |
16-Bit Comp |
|
32HUS1 |
EXE |
„Hurryorder“ ident. mit HURRYS1 aber |
32-Bit Comp |
|
HURRYS2 |
EXE |
„Hurryorder“ stabil (Adr.far) |
16-Bit Comp |
|
QUICK1 |
EXE |
Quicksort |
16-Bit Comp |
|
32QUICK1 |
EXE |
Quicksort ident. mit QUICK1 aber |
32-Bit Comp |
|
QUICK2 |
EXE |
Quicksort (Adr.far) |
16-Bit Comp |
|
BUBBLE1 |
EXE |
Bubblesort |
16-Bit Comp |
|
HEAP1 |
EXE |
Heapsort |
16-Bit Comp |
|
SHELL1 |
EXE |
Shellsort |
16-Bit Comp |
|
AUSTAUS1 |
EXE |
Austauschsort |
16-Bit Comp |
|
EINFUEG1 |
EXE |
Einfügesort |
16-Bit Comp |
Im folgenden sind einige wichtige Punkte zur Ergänzung der Tabelle aufgeführt:
· Die Algorithmen sind in der Programmiersprache „C“ implementiert.
· Alle aufgeführten Programme lösen die selbe Aufgabe.
· Die Programme sortieren Integerwerte.
· Der Bereich der Werte liegt zwischen -2147483647 und +2147483647
· Die Datenbank mit den Sortierobjekten (Integerwerten) befindet sich auf der Harddisk. Die Datenbank wird beim Sortieren nicht verändert. Sortiert werden die Indizes. Jeder Datensatz braucht einen Index der Grösse von 4 Byte. Die Indizes werden im RAM verwaltet.
· Für Hurryns1.exe und Hurryns2.exe werden pro Datensatz zwei Byte Zwischenspeicher benötigt (Freigabe nach beendetem Sortiervorgang).
· Für Hurrys1.exe und Hurrys2.exe werden pro Datensatz sechs Byte Zwischenspeicher benötigt (Freigabe nach beendetem Sortiervorgang).
· Anzahl Zugriffe auf die Datenbank.
· Anzahl Tauschvorgänge der Objekte.
· Die benötigte Sortierzeit in Sekunden.
Die Testresultate zeigen die einmalige Effizienz von „Hurryorder“. Bei den herkömmlichen Ordnungs-/Sortieralgorithmen zeigt - wie zu erwarten war - „Quicksort“ die besten Resultate.
Unter gleichen Bedingungen arbeitet „Hurryorder“ um ein vielfaches effizienter als „Quicksort“. Zudem kann der eine „Hurryorder“-Typ stabil sortieren, wozu „Quicksort“ nicht in der Lage ist.
Der Algorithmus „Hurryorder“ benötigt zum Ordnen sehr wenig Objektzugriffe, wie auch verhältnismässig wenige Tauschvorgänge.
Die Diagramme im Anhang (Anhang I, ‘Ordnungs-/Sortieralgorithmen im Vergleich’,) veranschaulichen die einmalige Effizienz von „Hurryorder“.
Die Datenbank besteht aus gleichmässig verteilten Zufallszahlen. Bereich der Werte: - 2147483640 bis 2147483640
|
ALGORITHMUS |
OBJEKTE |
ZUGRIFFE |
TAUSCH- VORGÄNGE |
SORTIER- ZEIT |
PRÜFUNG |
PRO-GRAMM |
|
BUBBLESORT
n.s. AUSTAUSCHSORT EINFUEGESORT SHELLSORT HEAPSORT QUICKSORT HURRYORDER n.s. HURRYORDER
s. |
1600 1600 1600 1600 1600 1600 1600 1600 |
2557140 1290043 676793 63226 51567 24319 3245 3245 |
638515 1593 674448 18015 18197 4372 2553 3245 |
2175.0 1271.0 135.0 65.0 50.0 21.0 1.0 1.0 |
OK OK OK OK OK OK OK OK |
bubble1 austaus1 einfueg1 shell1 heap1 quick1 hurryns1 hurrys1 |
|
EINFUEGESORT SHELLSORT HEAPSORT QUICKSORT HURRYORDER
n.s. HURRYORDER
s. |
5000 5000 5000 5000 5000 5000 |
6488128 226204 185172 86933 10364 10364 |
6480685 60728 64780 15599 9126 10364 |
1300.0 467.0 348.0 156.0 12.0 10.0 |
OK OK OK OK OK OK |
quick2 hurryns2 hurrys1 |
|
QUICKSORT HURRYORDER n.s. HURRYORDER s. |
10000 10000 10000 |
182280 21402 21402 |
33833 19147 21402 |
396.0 34.0 27.0 |
OK OK OK |
quick2 hurryns2 hurrys2 |
|
QUICKSORT HURRYORDER n.s. HURRYORDER s. |
16000 16000 16000 |
305000 35460 35460 |
56600 31494 35460 |
688.0 65.0 50.0 |
OK OK OK |
quick2 hurryns2 hurrys2 |
|
QUICKSORT HURRYORDER n.s. HURRYORDER s. |
40000 40000 40000 |
908418 98386 98386 |
149844 83290 98386 |
4021.0 313.0 237.0 |
OK OK OK |
32quick1 32huns1 32hus1 |
|
QUICKSORT HURRYORDER n.s. HURRYORDER s. |
80000 80000 80000 |
1848276 217636 217636 |
322076 176217 217636 |
8697.0 605.0 630.0 |
OK OK OK |
32quick1 32huns1 32hus1 |
|
QUICKSORT HURRYORDER n.s. HURRYORDER s. |
120000 120000 120000 |
2948401 360309 360309 |
502142 244791 360309 |
14483.0 1193.0 559.0 |
OK OK OK |
32quick1 32huns1 32hus1 |
|
QUICKSORT HURRYORDER n.s. HURRYORDER s. |
160000 160000 160000 |
3860624 471762 471762 |
684902 377852 471762 |
20691.0 1977.0 1537.0 |
OK OK OK |
32quick1 32huns1 32hus1 |
|
QUICKSORT HURRYORDER n.s. HURRYORDER s. |
200000 200000 200000 |
5151688 599532 599532 |
863227 483586 599532 |
27695.0 2652.0 1967.0 |
OK OK OK |
32quick1 32huns1 32hus1 |
Aus den Testresultaten ist ersichtlich, dass der Algorithmus „Hurryorder“ die Objekte sehr effizient ordnet. Es ist kein Ordnungs-/Sortieralgorithmus bekannt, welcher Objekte, gespeichert auf einer RAM-Disk, Floppydisk, Harddisk, etc., auch nur annähernd so schnell zu ordnen/sortieren vermag wie „Hurryorder“.
Wie bereits erwähnt, ist es eine der grössten Stärken von „Hurryorder“, die Objekte nicht nur zu sortieren, sondern auch zu ordnen. Die Effizienz ist auch beim Ordnen vergleichbar derer beim Sortieren. Das Sortieren, wie es in den Testprogrammen angewendet wurde, ist ja auch nur eine bestimmte Variante des Ordnens.
Der mögliche Einsatzbereich von „Hurryorder“ ist gross. Sinnvoll eingesetzt wird „Hurryorder“, wenn grosse Datenmengen nach verschiedensten Kriterien sortiert, geordnet oder ausgewertet werden sollen.
· Einmalige Effizienz beim Ordnen von Daten, gespeichert auf peripheren Datenträgern mit wahlfreiem Zugriff. (Harddisk, Floppydisk, optische Disk, etc.) Das Ordnen erfolgt im Durchschnitt zehnmal schneller als mit „Quicksort“.
· Die Fähigkeit Objekte zu ordnen.
· Sehr flexible Gestaltung der Datenordnung.
· Ein Typ von „Hurryorder“ kann stabil sortieren.
· Minimale Anzahl Zugriffe auf die Datenbank.
· Mässige Effizienz bei geringer Anzahl zu ordnender Objekte (Anzahl < 100).
· „Hurryorder stabil“ braucht temporär sechs Byte Speicher pro Objekt.
· „Hurryorder nicht-stabil“ braucht temporär zwei Byte Speicher pro Objekt.
[1] Weil das Ordnen wie auch das Sortieren Bestandteile der besprochenen alten wie neuen Verfahren sind, wird imText mit „Ordnungs-/Sortieralgorithmen“ darauf verwiesen.
8
A
COMPARISON OF
ORDERING AND SORTING ALGORITHMS