Das Folgende setzt die Mengenlehre voraus und beantwortet für \(k, m, n \in {}^{\nu}\mathbb{N}^*\) die Fragen: Wie lassen sich \(n = \epsilon^{\sigma} \le k^m\) im Stellenwertsystem zur Basis \(k\) kodierte Werte in \(\mathcal{O}(1)\) sortieren? Wie schnell sortiert deterministische Parallelisierung praxisnäher Arbitrary-Precision-Zahlen? Wie lassen sich zwei Matrizen \(\in {}^{\nu}\mathbb{R}^{n \times n}\) in \(\mathcal{O}(\sigma)\) multiplizieren? Wie lässt sich das Minimal- bzw. Maximalgerüst eines Graphen mit \(n\) Knoten in \(\mathcal{O}(\sigma)\) berechnen? Was ist die Antwort auf das Halteproblem? Warum gilt \(P = NP\)?
Sei der Speicher teilweise in Form eines Binomial-Baumes der Ordnung \(k\) mit \(k^{\grave{m}}\) Speicherplätzen organisiert, wobei \(k^{\grave{m}} = 2^h\) mit \(h \in {}^{\nu}\mathbb{N}\) gelte. Jeder Speicherplatz sei in der Lage einen zu sortierenden Wert komplett aufzunehmen und jeder Kante entspreche eine Datenleitung. Ein fortlaufend mehrfachen Werten angehängter Index bildet zusammen mit dem alten Wert den neuen. Jeder \(j\)-te Zwischenknoten korrespondiert hierarchisch mit der \(j\)-ten Stelle zur Basis \(k\) des zu sortierenden Wertes.
Speichern die Blätter statt der Werte deren Adressen (in einem Schritt), erlaubt ein weiterer sie sortiert in die Wurzel zurückzuholen und sie maximal so weit in den Baum zurückzuschieben, bis sie sich trennen. Geht ein Wert durch einen Zwischenknoten, setzt dieser sein Bit auf 1, aber auf 0, falls der Zwischenknoten keinen auszulesenden Nachfolger hat. Die Sortierreihenfolge bestimmt den ersten Wert.
Die nachfolgende Architektur mit autonomen Speichereinheiten verfügt über einfache rechnerische Möglichkeiten. Zusammengeschaltete verteilte Rechner vermögen sie zu simulieren. Die Komplexität erhöht sich durch Einsortieren eines zusätzlichen Wertes um \(\mathcal{O}(\sigma)\), da dies einer binären Suche entspricht. Sie ist antiproportional zur Anzahl der Baumknoten im Speicher. Das Verwenden von \(d \in {}^{\nu}\mathbb{N}^*\) Datenleitungen verringert sie um den Faktor \(\tilde{d}\), die Belegung des \(g\)-fachen eines Speicherplatzes, erhöht sie um den Faktor \(g\).
Enthält der Speicher keinen Binomial-Baum der Ordnung \(k\), erhöht sie sich um den Faktor \({_k}n\), weil jeder Zwischen- knoten zu einem Wert zu lesen ist. Ein anderweitiges Nutzen der ersten \(k^p\) Speicherplätze mit \(p \in {}^{\nu}\mathbb{N}\) erfordert ein Durchsuchen aller Zwischenknoten der \(p\)-ten Stufe. Die Komplexität erhöht sich bei gut gefülltem Speicher marginal, andernfalls um den Worst-Case-Faktor \(\mathcal{O}(k^p)\).
Die zu multiplizierenden Matrizen sind so quadratweise je \(n\)-fach in einem Speicherwürfel abzulegen, dass jede Speichereinheit zwei Werte multipliziert und jeder Eintrag der Produktmatrix als Summe mit \(n\) Summanden in \(\mathcal{O}(\sigma)\) bestimmt wird (Vektorrechner). Matrixmultiplikation lässt sich auch über adressierte schwärmende Einträge realisieren. Tensorprodukte lassen sich effizient durch \(n\)-Speicherwürfel abbilden, die durch entsprechende Datenleitungen im dreidimensionalen Raum verbleiben.
Der optimale Sortieralgorithmus Bitsort sortiert stabil mit der Zeitkomplexität \(\mathcal{O}(n)\) und benötigt \(\mathcal{O}(n)\) zusätzlichen Speicherplatz. Voraussetzungen: Je zwei Werte liegen als Bitfolge vor, lassen sich in \(\mathcal{O}(1)\) vergleichen und ebenso deren sämtliche Bits abarbeiten. Ferner sei der Speicher teilweise als Binärbaum realisiert und der Weg von Wurzel bis Blatt kann ebenfalls in \(\mathcal{O}(1)\) durchlaufen werden.
Ist \(p \in {}^{\nu}\mathbb{N}^*\) die Anzahl der parallelen Schritte für paralleles Bitsort, so ist die Zeitkomplexität \(\mathcal{O}(\tilde{p} n)\). Jedes Einfügen in den stets sortierten Baum bzw. Ausgeben eines Wertes hat die Zeitkomplexität \(\mathcal{O}(1)\). Der Speicher sei mit folgender Intelligenz versehen: Jeder Baumknoten speichert den ihn erreichenden Wert selbständig und kann ihn an den nächsten Baumknoten weitergeben, wenn er schon besucht wurde, bzw. andernfalls seine Adresse an die Zentraleinheit zurückgeben. Der Wurzel entspricht kein Bitwert.
Begonnen wird bei dem höchstwertigen Bit eines Wertes. Jedes seiner nacheinander abgearbeiteten Bits bestimmt den nächsten Knoten innerhalb des Binärbaumes. Wurden alle Bits abgearbeitet oder ergibt sich ein Unterschied zum verglichenen Bit und wurde der zugehörige Knoten noch nicht besucht, speichert der folgende Knoten ggf. die nicht im Baum liegende Adresse der restlichen Bitkette des Wertes bzw. die Anzahl der Werte für diesen Knoten bei unerheblicher Reihenfolge gleicher Werte.
Die Zeitkomplexität aller Verfahren, die Werte der Bitlänge \(b = q a \in {}^{\nu}\mathbb{N}^*\) mit Adresslänge \(a \in {}^{\nu}\mathbb{N}^*\) sortieren, erhöht sich pro Wert von \(\mathcal{O}(1)\) auf \(\mathcal{O}(q)\). Ist \(r\) der Durchschnittswert von \(q\), ist in der Zeitkomplexität des Sortierverfahrens mindestens ein \(\mathcal{O}(n)\) durch \(\mathcal{O}(r n)\) zu ersetzen. Ist \(s \in {}^{\nu}\mathbb{N}^*\) die durchschnittliche 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 beträgt die Zeitkomplexität des Verfahrens \(\mathcal{O}(({_\epsilon}s + r) n)\).
Dabei werden die erwähnten Werte eines Buckets pro Bucket in einem AVL-Baum abgelegt oder in einem B-Baum bei Ablage in einem zum Hauptspeicher relativ langsamen externen Speicher. Dort wird jeweils nur mit dem signifikanten Teilwert der Adresslänge eines Wertes gearbeitet. Der Verzicht auf vollständig sortierte Werte nach jedem Abarbeiten eines Wertes reduziert die komplette Sortierung durch Verwendung von zwei Hauptspeicherbereichen zeitlich auf \(\mathcal{O}(r n)\).
Der zweite Hauptspeicherbereich wird nach jedem Durchlauf gelöscht, um für den nächsten Durchlauf zur Verfügung zu stehen, bis ein 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 weiter sortiert werden. Für den schnellen Zugriff auf jeden Teilwert ist jeder Wert zusammenhängend im Speicher abzulegen.
Die Verwendung des \(\mathcal{O}(r n)\)-Verfahrens für die Stammdaten und des \(\mathcal{O}(({_\epsilon}s + r) n)\)-Verfahrens für die Bewegungsdaten kombiniert beide gut. Damit lassen sich insbesondere schnell Tabellenindizes anlegen. Bei umfangreichen Tabellen macht es einen deutlichen Unterschied, ob ein Index in \(\mathcal{O}(r n)\) statt in \(\mathcal{O}(r \sigma n)\) angelegt wird und sich dann ein Wert durchschnittlich in \(\mathcal{O}({_\epsilon}s + r)\) statt in \(\mathcal{O}(\sigma + r)\) oder schlechter suchen lässt. Sortieren durch Mischen sortierter Listen ist ebenfalls in \(\mathcal{O}(r n)\) möglich.
Diskussion von Bitsort: Es ist unter den angegebenen Voraussetzungen optimal sowie für die parallele Programmierung, den schnellen laufenden Aufbau von Tabellenindizes in Datenbanken und die Suche darin gut geeignet. Seine Hardwareimplementierung ist eher ungewöhnlich. Während es noch eher Theorie als Praxis ist, verhält es sich bei dem nachfolgenden Verfahren eher umgekehrt.
Square Sort: In der computergestützten Nichtstandardmathematik stoßen traditionelle Sortierparadigmen an physikalische Grenzen. Die Verarbeitung sehr komplexer, zeigerbasierter Datentypen mit hoher Präzision wird nicht primär durch die Anzahl der mathematischen Vergleiche begrenzt, sondern durch Speicherbandbreite, Latenzen bei der Zeiger-Dereferenzierung und den Overhead der dynamischen Speicherverwaltung. Seine Zeitkomplexität ist \(\mathcal{O}(N\;{_2}N)\), die des Speichers ist \(\mathcal{O}(N)\).
Es führt ein statisches Speichermanagement mit einem asymmetrischen Work-Stealing-Scheduling zusammen und übertrifft klassische generische Verfahren (wie Timsort oder herkömmliche parallele MergeSort-Implementierungen) bei komplexen Datentypen deutlich, insbesondere bei Pseudozufallszahlen. Die genauen Laufzeiten und Leistungskennzahlen finden sich weiter unten. Eine interne Portierung von Julia nach C++ erbrachte vergleichbare Ergebnisse.
Klassische Merge-Ansätze skalieren im unteren Baum hervorragend, zwängen die Hardware im finalen Verschmelzungsschritt jedoch in einen Single-Thread-Flaschenhals. Square Sort verwendet stattdessen einen parallelen Divide-and-Conquer-Merge. Durch die strategische Suche nach Medianen und die binäre Verortung in den Teilvektoren wird der verbleibende Lösungsraum kontinuierlich partitioniert. Jeder asymmetrische Sub-Task wird dynamisch auf freie Prozessorkerne verteilt.
Die Überwindung der durch das Amdahlsche Gesetz beschriebenen Begrenzungen erlaubt ein hybrides Chunking für radikale Cache-Lokalität. Um die teuren Hauptspeicherzugriffe bei der Auswertung von Heap-Referenzen zu minimieren, übergibt Square Sort die Basis-Ebene an einen In-Place-Algorithmus. Die Datenblöcke werden so dimensioniert, dass sie im kernexklusiven L1/L2-Cache der CPU verbleiben. Dies vermeidet das „Cache-Thrashing“, das bei traditionellen Bottom-up-Verfahren unweigerlich auftritt.
Während andere Algorithmen den Garbage Collector (GC) bei Millionen von Arbitrary-Precision-Zahlen unter hohen Druck setzen, erlaubt Square Sort eine große Ressourceneffizienz und einen Zero-GC-Overhead durch statisches Speichermanagement. Der temporale Arbeitspuffer beträgt \(\mathcal{O}(N)\). Alternierende Vertauschungen der Speicherzeiger auf jeder Rekursionsebene ersparen zusätzliche Speicheranforderungen und garantieren eine lineare, deterministische Ausfallsicherheit ohne Allokationsspitzen.
Diskussion von Square Sort: Es ist kein generischer Allrounder für primitive Datentypen, sondern ein präzises mathematisches Instrument. Es verzichtet auf die SIMD-Vektorisierbarkeit nativer Maschinenzahlen zugunsten einer überlegenen, ausfallsicheren und massiv parallelen Skalierbarkeit bei den rechenintensiven, eindimensionalen Strukturen der Nichtstandardmathematik, die sich etablieren wird, wenn deren eindeutige Vorteile auch ihre Widersacher überzeugt hat.
| n × 105 | Tt (ms) | Ts (ms) | Tt / Ts | At (MB) | As (MB) | At / As |
|---|---|---|---|---|---|---|
| 1 | 4,29 | 0,95 | 4,51 | 1,26 | 0,06 | 20,08 |
| 4 | 16,36 | 2,25 | 7,27 | 5,05 | 0,10 | 50,89 |
| 16 | 64,51 | 11,56 | 5,58 | 20,23 | 0,15 | 139,34 |
| 64 | 271,74 | 46,83 | 5,80 | 80,90 | 0,30 | 267,73 |
| 256 | 4.250,16 | 377,37 | 11,26 | 323,60 | 0,87 | 371,40 |
| 1024 | 18.984,41 | 1.438,08 | 13,20 | 1.294,67 | 3,08 | 419,73 |
Die Tabelle macht die idealisierte Annahme der Landau-Notation \(\mathcal{O}(N\;{_2}N)\) zunichte. Deren vermeintlich statische Konstante \(C\) steigt bei Timsort ab der L3-Cache-Schwelle (\(N = 12,8 \times 10^6\)) deutlich an. Unvorhersehbare Zeigerzugriffe übersättigen den L3-Cache, wodurch \(C\) durch massive RAM-Latenzen sprunghaft eskaliert. Square Sort hält \(C\) durch strikte Lokalität stabil und zeigt auf: Reale Skalierbarkeit wird nicht durch asymptotische Mathematik, sondern durch physikalisches Speichermanagement bestimmt.
Sei \(n \in {}^{\nu}\mathbb{N}^*\) die Anzahl der Knoten eines endlichen schlichten zusammenhängenden Graphen. (Ist er nicht schlicht, lässt ein Aussortieren in \(\mathcal{O}(n)\) nur die kleinste parallele Kante und keine Schlingen zu. Ist er nicht zusammenhängend, werden in \(\mathcal{O}(n)\) alle isolierten Knoten entfernt.) Bei Ausschluss negativer Gewichte benötigt der Algorithmus von Dijkstra \(\mathcal{O}(n)\) Schritte für jeden minimalen Weg in dem Graphen, da Sortieren sowie paralleles Addieren und Vergleichen in \(\mathcal{O}(1)\) möglich ist.
Dessen Minimal- oder Maximalgerüst lässt sich in \(\mathcal{O}(\sigma n)\) oder gar in \(\mathcal{O}(\sigma)\) berechnen: Die Kanten eines Knotens lassen sich parallel in \(\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, die von ihm ausgehen, an dieses Bit für Bit als Wert an. Er speichert den kleinsten Wert, der ihn erreicht. Dies ist in \(\mathcal{O}(n)\) bzw. \(\mathcal{O}(1)\) möglich.
Das Schwarzfärben der Kanten zwischen jeweils zwei Knoten desselben Minimalgerüsts benötigt maximal die gleiche Zeit. Jeder Knoten hat dann einen nächsten Nachbarknoten. Ein Fortfahren mit den weiß gefärbten Kanten in \(\mathcal{O}(\sigma)\) Schritten kann den kleinsten Wert eines Minimalgerüsts in \(\mathcal{O}(n)\) bzw. \(\mathcal{O}(1)\) bestimmen, bis das gesamte Minimalgerüst in \(\mathcal{O}(\sigma n)\) bzw. \(\mathcal{O}(\sigma)\) entstanden ist. Für ein Maximalgerüst werden alle Kantengewichte von einer hinreichend großen Konstanten subtrahiert.
Haltesatz: Um ein festes \(r_m\) der Zahl \(0{,}r_{1}r_{2}…r_{m}\) zu erreichen, hält ein Programm für beliebige (Pseudo-) Zufallszahlen \(r_j \in {}^{\nu}\mathbb{N}\) mit \(k \in {}^{\nu}\mathbb{N}^{*}\) Stellen und Basis \(p := 2^k\) in \(m \in \mathbb{N}^{*}\) Schritten mit der Wahrscheinlichkeit \(\tilde{p}\).
Beweis: Dies ist ein optimales Ergebnis der Wahrscheinlichkeitsrechnung1.\(\square\)
Bemerkung: Zufall ist unentscheidbar. Damit existieren Programme, die mit beliebiger Wahrscheinlichkeit halten, und es folgen die Gödelschen Unvollständigkeitssätze. Der Gödelsatz „Ich bin nicht beweisbar.“ ist insofern sophistisch, als er das Scheinargument Petitio Principii ex negativo aufweist. Zum Lösen des Halteproblems ist ein Selbstbezug unsinnig, der ein Halten gleichzeitig gebietet und verbietet. Die Selbstreferenz macht das Diagonalargument für das Halteproblem unzulässig.
Satz: Ist \(\mathcal{L}\) die Menge aller (Typ-0-) Sprachen \(L_k\) aus endlichen Wörtern mit Maximallänge \(\nu\) für mittendliches \(|\mathcal{L}| = 2^{({\nu}^{\grave{\nu}}-1)/\acute{\nu}}\) (unter Anwendung der GR) und \(k \in \{1, …, |\mathcal{L}|\}\), gilt \(P = NP = \mathcal{L}\).
Beweis: Da sich jede deterministische Turingmaschine auch als nichtdeterministisch auffassen lässt2, gilt \(P \subseteq NP\). Es enthält \(P\) alle linearen Sprachen \(L_k\) und \(NP\) nur solche.\(\square\)
© 2006-2026 by Boris Haase