Homepage von Boris Haase




Funkrechnen • Internet und Co • Programmieren mit Stair • Sortieren und Suchen  (Vorherige | Nächste)



Sortieren und Suchen

Sortieren und Suchen

Ist Sortieren von n Werten in \(\mathcal{O}\)(1) möglich? Ja, in zwei Schritten.

Nehmen wir an, wir hätten keine Hardwarebeschränkungen: Der Speicher sei in Form eines Baums vom Grad k organisiert und habe km+1 Speicherplätze mit km+1 = 2h mit natürlichem h. Jeder Speicherplatz kann jeden zu sortierenden Wert komplett aufnehmen. Kommen Werte mehrfach vor, werde jedem Wert ein fortlaufender Index angehängt, der mit dem alten Wert zusammen den neuen Wert bildet. Jeder Wert sei im k-System kodiert und es seien o. B. d. A. maximal km Werte zu sortieren.

Von der Wurzel gehen km Datenleitungen ab, von den beiden Nachfolgern je km-1, von deren Nachfolgern je km-2 usf. Jeder z-te Zwischenknoten korrespondiert hierarchisch mit der z-ten Stelle im k-System des zu sortierenden Wertes. In den Blättern können alternativ die Adressen der Werte anstatt der Werte selbst gespeichert werden. Dann lassen sich in einem Schritt alle Werte in den Blättern speichern und in einem weiteren sortiert in die Wurzel zurückholen. Es reicht aus die Werte soweit in den Baum zu schieben, bis sie sich trennen.

Haben wir nun eine Beschränkung von einer Datenleitung pro Speicherplatz, müssen die Werte nacheinander ausgelesen werden. Das Anfügen von einem Index bei mehrfachen Werten kann nun entfallen, da mehrfache Werte in einer separaten Liste verwaltet werden können. Jeder Zwischenknoten merkt sich, welche Werte durch ihn hindurchgingen, indem er für jeden Wert das entsprechende Bit auf 1 setzt. Dieses Bit wird auf 0 gesetzt, wenn der Zwischenknoten keinen auszulesenden Nachfolger mehr hat. Begonnen wird mit dem jeweils kleinsten Wert bei aufsteigender Sortierreihenfolge, mit dem größten bei absteigender.

Es ergibt sich die Komplexität \(\mathcal{O}\)(n) (Speichern, Nachfolger prüfen, Bits maskieren, Auslesen). Ist ein zusätzlicher Wert einzusortieren, fällt eine Zusatzkomplexität von \(\mathcal{O}\)(log n) an (binäre Suche in einer sortierten Liste). Werden d Datenleitungen verwendet, verringert sich der Komplexität des Sortierens um den Faktor 1/d. Sind die Werte g-mal so lang wie ein Speicherplatz fassen kann, erhöht sich die Komplexität um den Faktor g.

Ist der Speicher nicht als Baum vom Grad k organisiert, erhöht sich die Komplexität um den Faktor logkn, weil dann jeder Zwischenknoten zu einem Wert gelesen werden muss. Je mehr sich von einem Baum vom Grad k in der Speicherorganisation wiederfindet, desto geringer ist die Komplexität. Sollen die ersten kp Speicherplätze anderweitig genutzt werden, so sind alle Zwischenknoten der p. Stufe zu durchsuchen. Die Komplexität erhöht sich dadurch marginal, wenn der Speicher gut gefüllt ist, ansonsten entsprechend mehr mit dem Worst-Case-Faktor \(\mathcal{O}\)(kp).

Derzeitig praktikable, nicht-parallele Sortieralgorithmen, die auf Austauschen der n Eingabewerte beruhen, haben eine Komplexität von \(\mathcal{O}\)(n log n). Dieser Wert kann wie beschrieben deutlich durch das an Radixsort angelehnte Verfahren unterboten werden.


Im Folgenden soll der optimale Sortieralgorithmus Bitsort vorgestellt werden. Er sortiert stabil mit der stets gleichen Zeitkomplexität \(\mathcal{O}\)(n) und benötigt \(\mathcal{O}\)(n) zusätzlichen Speicherplatz. Hierbei wird davon ausgegangen, dass der Vergleich zweier Werte die Zeitkomplexität \(\mathcal{O}\)(1) benötigt, die Werte als Bitfolge vorliegen und alle Bits eines Wertes ebenfalls in \(\mathcal{O}\)(1) abgearbeitet werden können. Es wird ferner vorausgesetzt, dass der Speicher als Binärbaum realisiert ist und der Weg von Wurzel bis Blatt ebenfalls in \(\mathcal{O}\)(1) durchlaufen werden kann. Ist p die Anzahl der parallelen Schritte für paralleles Bitsort, so ist die Zeitkomplexität \(\mathcal{O}\)(n/p).

Nachdem ein Wert abgearbeitet wurde, liegen die bis dahin eingefügten Werte sortiert vor. Das Einfügen eines weiteren Wertes hat die Zeitkomplexität \(\mathcal{O}\)(1). Nach jedem Einfügen können die m Werte mit Zeitkomplexität \(\mathcal{O}\)(m) ausgegeben werden. Der Speicher muss mit einer gewissen eigenen Intelligenz versehen sein: Jeder Speicherknoten muss in der Lage sein den Wert, der ihn erreicht, selbständig zu speichern und an den nächsten Speicherknoten weiterzugeben, wenn er schon besucht wurde, bzw. seine Adresse an die Zentraleinheit zurückzugeben, wenn er noch nicht besucht wurde, nachdem er den Wert gespeichert hat. Der jeweils nächste Speicherknoten ergibt sich aus dem entsprechenden Bit des Wertes innerhalb der Speicherhierarchie.

Die Bits eines Wertes werden jeweils - beginnend bei dem führenden Bit - solange abgearbeitet, bis ein Unterschied zum vorherigen Wert oder die Gleichheit feststeht. Jeder Wert wird als Blatt in einen Binärbaum eingefügt. Bei Gleichheit speichert ein Blatt entweder die Anzahl der Werte für dieses Blatt, die Adresse einer Liste, die die Adressen für diesen Wert enthält, oder, wenn die Bits des Wertes noch nicht vollständig abgearbeitet wurden, den Wert selbst bzw. den Bitrest. Die Bitkette wird immer dann an der Stelle aufgelöst, an der ein Blatt gebildet wird. Sehr viele Bits des gleichen Werts können mit ihrer Anzahl gespeichert werden. Dies bietet sich bspw. bei Fließkommazahlen in Exponentialdarstellung an. Die Listen können zu einer zusammengefasst werden, wenn jeder Eintrag auf seinen Nachfolger (Vorgänger) gleichen Werts verweist bzw. auf null, wenn es keinen gibt. Die inneren Knoten speichern den Wert, der sie als letztes passiert hat, bzw. die gemeinsame Bitkette zweier Werte unterhalb des Knotens, von dem diese abgezweigt sind.


In allen Sortierverfahren, bei denen Werte mit einer Bitlänge von l = q a mit Adresslänge a sortiert werden, erhöht sich die Zeitkomplexität pro Wert von \(\mathcal{O}\)(1) auf \(\mathcal{O}\)(q). Wenn \(\mathcal{O}\)(r) der Durchschnittswert von \(\mathcal{O}\)(q) ist, ist also in der Zeitkomplexität des Sortierverfahrens mindestens ein \(\mathcal{O}\)(n) durch \(\mathcal{O}\)(r n) zu ersetzen. Ist s der Durchschnittswert der Anzahl der verschiedenen (!) Werte, die in einem Bucket nach Sortierung bis Bitlänge a landen und deren Bitlänge größer als a ist, so ist die Zeitkomplexität des Sortierverfahrens \(\mathcal{O}\)((log s + r) n). Dabei werden die erwähnten Werte eines Buckets pro Bucket in einem AVL-Baum abgelegt (bzw. in einem B-Baum, wenn sie in einem zum Hauptspeicher relativ langsameren externen Speicher gespeichert werden). Dort wird jeweils immer nur mit dem signifikanten Teilwert von Adresslänge eines Wertes gearbeitet.

Wenn on darauf verzichtet, dass die Werte nach jedem Abarbeiten eines Wertes vollständig sortiert vorliegen, dann kann eine Zeitkomplexität \(\mathcal{O}\)(r n) für die komplette Sortierung durch Verwendung von zwei Hauptspeicherbereichen erreicht werden. Die Werte werden zuerst bis Adresslänge in Buckets sortiert und dann Adresslänge für Adresslänge (d. h. Teilwert für Teilwert) Bucket für Bucket weitersortiert. Das Abarbeiten der Werte, deren zuvor abgearbeiteter Teilwert gleich ist, wird als ein Durchlauf gezählt. Hierbei wird vorausgesetzt, dass das Lesen und Schreiben der Teilwerte eines Wertes und seiner Adresse über alle Durchläufe durchschnittlich komplett als \(\mathcal{O}\)(r) gezählt wird.

Der zweite Hauptspeicherbereich wird nach jedem Durchlauf gelöscht, um für den nächsten Durchlauf zur Verfügung zu stehen, bis der Bucket abgearbeitet ist. In den ersten Hauptspeicherbereich werden stets nur die Adressen in der aktuellen Sortierreihenfolge zurückgeschrieben, bevor die Werte mit gleichem soeben abgearbeitetem Teilwert weitersortiert werden. Jeder Wert ist zusammenhängend im Speicher abzulegen, damit auf jeden Teilwert schnell zugegriffen werden kann. Über die Zeitkomplexität lässt sich zugegebenermaßen streiten. Die Werte eines Buckets und alle Adressen sollten zusammen in den Hauptspeicher passen, um relativ lange Ladezeiten zu vermeiden.

Beide Verfahren können gut kombiniert werden: Erst das \(\mathcal{O}\)(r n)-Verfahren für den Stamm, dann das \(\mathcal{O}\)((log s + r) n)-Verfahren für das Laufende. Sortierte Daten können in \(\mathcal{O}\)(n) in Hauptspeicher und AVL- bzw. B-Baum abgelegt werden. Damit können insbesondere schnell Indizes für nicht-indizierte Tabellenspalten in Datenbankabfragen aufgebaut werden. Bei umfangreichen Tabellen macht es einen deutlichen Unterschied, ob ein Index in \(\mathcal{O}\)(r n) statt in \(\mathcal{O}\)(r n log n) aufgebaut wird und dann ein Wert durchschnittlich in \(\mathcal{O}\)(log s + r) statt in \(\mathcal{O}\)(log n + r) oder schlechter gesucht werden kann. Bei geschickter Nutzung eines genügend großen Hauptspeichers können bequem mehrere Indizes gleichzeitig gehalten werden. Bei Zahlen ist r normalerweise recht klein in Abhängigkeit von der Genauigkeit und s bei entsprechender Verteilung ebenfalls. Ähnliches gilt für (komprimierte) Wörter, wenn die Speichergröße der heute handelsüblicher Rechner entspricht. Sortieren durch Mischen beliebig vieler sortierter Listen ist ebenfalls in \(\mathcal{O}\)(r n) möglich.


Diskussion von Bitsort: Es eignet sich gut für parallele Programmierung und ist stabil. Es ist unter den gemachten Voraussetzungen optimal. Bitsort tut nur das, was absolut erforderlich ist, ist ebenfalls optimal für den schnellen laufenden Aufbau von Indizes in (relativ schnell wachsenden) Datenbanken und für die Suche (s. u.). Suchbäume brauchen nicht ausgeglichen werden. Für Bitsort empfiehlt sich eine maschinennahe Implementierung. Es schlägt für Werte mit relativ wenigen Bits (maximal Adresslänge) und entsprechende Hardware alle mir bekannten Sortierverfahren, wenn die Werte nacheinander gelesen werden müssen. On sollte sich reiflich überlegen, ob sich eine Anpassung der Hardware lohnt, um die beschriebene Zeitkomplexität zu erreichen. Die Implementierung eines entsprechenden Speichers mit relativ geringer Intelligenz ist zwar einfach und spart komplexere Prozessoren, aber durch Einsatz hinreichend vieler von diesen oder Parallelverarbeitung (z. B. parallele Nutzung von Speicherbereichen) kann der Term log s + r in \(\mathcal{O}\)((log s + r) n) kleiner als 1 gemacht werden, wenn on nur AVL- bzw. B-Bäume einsetzt und hinterher die Ergebnislisten in \(\mathcal{O}\)(n) mischt.


Zur Unterstützung des Sortierens und Suchens in heterogenen (verteilten) Datenbanken (etwa unterschiedlicher Datenbankmodelle) kann eine Datenbanksprache eingesetzt werden, die mithilfe aus diesen erstellter dynamischer Datenstrukturen eine vereinheitlichte Datenmanipulation (z. B. unter einer einheitlichen Oberfläche) erlaubt, solange die Datensätze einen irgendwie gleichartigen Aufbau haben. Sie kann aufgrund entsprechender Vorgaben dynamisch (evtl. vorausschauend) entscheiden, welche Manipulationsschritte durchzuführen sind. Ihr müssen nur die entsprechenden Speicherinformationen der Datenbanken mit dem Aufbau der Datenbankstrukturen zur Verfügung gestellt werden.

Programmcode- und Datenänderungen (wie die Integration weiterer Datenbanken) zur Laufzeit können vorgesehen werden, wenn ausreichende Sicherheitsmechanismen (einschließlich Berechtigungsprüfung und Setzen von Sperren) zur Verfügung stehen. Die Indizes können bspw. parallel oder zu lastarmen Zeiten in Abhängigkeit von ihrer Größe mit unterschiedlichen Datenstrukturen - angepasst an die individuelle Problemstellung bzw. optimiert - aufgebaut werden. Evtl. reicht ein temporäres Mischen oder paralleles Zugreifen aus. Leistungsfähige Standards können die Implementierung einer solchen Datenbanksprache deutlich erleichtern.


Ausblick in die Graphentheorie: Sei n die Anzahl der Knoten eines endlichen schlichten zusammenhängenden Graphen. (Wenn er nicht schlicht ist, lasse on durch Aussortieren in \(\mathcal{O}\)(n) nur die kleinste parallele Kante und keine Schlingen zu. Wenn er nicht zusammenhängend ist, entferne man in \(\mathcal{O}\)(n) alle isolierten Knoten.) Da Sortieren und paralleles Addieren und Vergleichen in \(\mathcal{O}\)(1) möglich ist, liefert der Algorithmus von Dijkstra jeweils einen kürzesten Weg in ihm in höchstens \(\mathcal{O}\)(n), wenn negative Gewichte ausgeschlossen sind. Wie können in ihm ein Minimal- und ein Maximalgerüst in \(\mathcal{O}\)(n log n) oder gar in \(\mathcal{O}\)(log n) berechnet werden?

Entspreche jeder Knoten einer anderen natürlichen Zahl. Dann lassen sich die Kanten, die von ihm ausgehen parallel in jeweils höchstens \(\mathcal{O}\)(n) bzw. \(\mathcal{O}\)(1) sortieren. Seien alle Kanten zu Beginn weiß gefärbt. Jeder Knoten hängt die kleinere und dann die größere Zahl der beteiligten Knoten der Kante mit dem kleinsten Gewicht aller weiß gefärbten Kanten an dieses Bit für Bit als Wert an, die von ihm ausgehen und speichert den kleinsten Wert, der ihn erreicht. Dies ist in höchstens \(\mathcal{O}\)(n) bzw. \(\mathcal{O}\)(1) möglich. Dann hat jeder Knoten einen nächsten Nachbarknoten und die Kanten, die aus jeweils zwei Knoten desselben Minimalgerüsts bestehen, werden schwarz gefärbt. Dies ist ebenfalls in höchstens \(\mathcal{O}\)(n) bzw. \(\mathcal{O}\)(1) möglich.

Nun setzt sich das Verfahren mit den weiß gefärbten Kanten in höchstens \(\mathcal{O}\)(log n) Schritten fort, wobei der kleinste Wert eines Minimalgerüsts in höchstens \(\mathcal{O}\)(n) bzw. \(\mathcal{O}\)(1) bestimmt werden kann, bis ein Gesamtminimalgerüst in höchstens \(\mathcal{O}\)(n log n) bzw. \(\mathcal{O}\)(log n) entstanden ist. Ein Gesamtmaximalgerüst kann durch jeweilige Subtraktion der Kantengewichte von einer hinreichend großen Konstante als neue Kantengewichte berechnet werden.

Mit der Berechnung kürzester Wege lässt sich im Computer z. B. ein Verkehrsleitsystem simulieren, das auf veränderte Bedingungen mit Änderung der Kantengewichte reagiert. Paketkollisionen können verhindert werden, wenn die Knoten durchnummeriert werden und jeweils das Paket als erstes zum Zuge kommt, das den Vorgängerknoten mit der kleinsten Zahl durchläuft. Hierbei können Kollisionen minimiert werden, indem Verkehrsteilnehmern Zwischenziele auf weniger belasteten Strecken vorgegeben werden.

© 2006-2011 by Boris Haase


Valid XHTML 1.0 • Haftungsausschluss • mail@boris-haase.de • PDF-Version • Literatur • Schlagwörter • Definitionen • Statistik • PHP-Code • RSS-Feed • Seitenbeginn