Neuer Buchsortieralgorithmus erreicht nahezu perfekte Leistung
(quantamagazine.org)- Das Bibliothekssortierproblem bestimmt nicht nur die Ordnung im Bücherregal, sondern auch die Kosten sequentieller Speicherung auf Festplatten und in Datenbanken; neue Forschung senkt die durchschnittliche Einfügezeit auf nahezu die theoretische Grenze
- Ein Algorithmus von 1981 garantierte auf deterministische und glatte (smooth) Weise eine durchschnittliche Einfügezeit von ((log n)^2), doch mehr als 40 Jahre lang wurde keine niedrigere obere Schranke gefunden
- Spätere Untersuchungen zu unteren Schranken zeigten, dass für allgemeine Algorithmen (log n) optimal ist, während für glatte und deterministische Algorithmen die Grenze bei ((log n)^2) liegt, sodass ein randomisierter, nicht-glatter Ansatz nötig wurde
- 2022 senkten Bender, Kuszmaul und andere mit einem randomisierten, history-independenten Algorithmus die obere Schranke auf ((log n)^{1.5}); die neueste Arbeit erreicht mit begrenzter Nutzung vergangener Informationen ((log n)(log log n)^3)
- Die verbleibende Lücke besteht aus einem (log log n)-Term, und dieser Fortschritt könnte Anwendungen wie die auf List Labeling basierende Speicherung und Verarbeitung dynamischer Graphen beschleunigen
Was das Bibliothekssortierproblem fragt
- Das Bibliothekssortierproblem behandelt die Frage, wie sich die Zeit zum Verschieben minimieren lässt, die nötig ist, um neue Elemente einzufügen und dabei die sortierte Reihenfolge zu erhalten
- Wenn man Bücher an einer Seite zusammendrängt, müssen beim Einfügen eines neuen Buchs in der Mitte viele Bücher erneut verschoben werden
- Beim Hinzufügen eines Buchs von Isabel Allende könnte es nötig sein, den gesamten Bestand zu verschieben
- Wird danach ein Buch von Douglas Adams hinzugefügt, kann sich dieselbe Arbeit wiederholen
- Verteilt man freien Platz passend über das ganze Regal, lassen sich die Einfügekosten senken, doch entscheidend ist, wo und wie viel Platz freigelassen wird
- Formaler ist dies als List-Labeling-Problem bekannt und wurde in einer Arbeit von 1981 eingeführt
- Der Anwendungsbereich reicht weit über Bücherregale hinaus bis zur Platzierung von Dateien und Einträgen auf Festplatten und in Datenbanken
- Die Zahl der Elemente kann in die Milliarden gehen
- Eine ineffiziente Anordnung führt zu langen Wartezeiten und hohen Rechenkosten
Leistung aus Sicht oberer und unterer Schranken
- Die Leistung einer sortierten Anordnung wird meist daran gemessen, wie lange das Einfügen eines einzelnen neuen Elements dauert
- Gibt es (n) Elemente und müssen im schlimmsten Fall alle Bücher verschoben werden, ist die Einfügezeit proportional zu (n)
- Das kann als obere Schranke für die Zeit zum Hinzufügen eines neuen Elements gelten
- Die Arbeit von 1981 fragte, ob sich die durchschnittliche Einfügezeit deutlich unter (n) senken lässt, und präsentierte einen Algorithmus mit Garantie von ((log n)^2)
- Es handelt sich um einen deterministischen Algorithmus, der nicht auf Zufälligkeit beruht
- Er besitzt die Eigenschaft glatt (smooth) zu sein, das heißt, Elemente müssen innerhalb des Bereichs, in dem Einfügungen oder Löschungen stattfinden, gleichmäßig verteilt sein
- Forschende versuchen, die Lücke zwischen oberen und unteren Schranken zu schließen; stimmen beide überein, gilt ein Algorithmus als optimal
Einschränkungen durch frühere Resultate zu unteren Schranken
- Eine Studie von 2004 zeigte für die allgemeinste Version des Bibliothekssortierproblems eine fundamentale untere Schranke: Kein Algorithmus kann besser als (log n) sein
- 1990 wurde bestätigt, dass die untere Schranke für glatte Algorithmen bei ((log n)^2) liegt
- 2012 folgte das Resultat, dass auch deterministische Algorithmen ohne Randomisierung dieselbe untere Schranke ((log n)^2) haben
- Diese Ergebnisse bedeuten, dass sich die obere Schranke von 1981 in Höhe von ((log n)^2) mit rein glatten oder deterministischen Algorithmen kaum verbessern lässt
- Michael Bender kam zu dem Schluss, dass für bessere Resultate ein randomisierter und nicht-glatter Algorithmus nötig ist
- Ein nicht-glatter Ansatz wirkte intuitiv riskant, weil die Elemente dann nicht gleichmäßig verteilt werden
- Auch warum zufällige Entscheidungen helfen sollten, war nicht offensichtlich
2022: Mit History Independence die obere Schranke gesenkt
- Bender, William Kuszmaul und vier weitere Forschende entwickelten 2022 einen history-independenten, nicht-glatten und randomisierten Algorithmus
- Ein history-independenter Algorithmus verrät nicht den vergangenen Zustand des Regals
- Kuszmaul nannte als Beispiel, dass jemand nicht erkennen kann, ob ein Buch früher im Regal stand, nachdem es entfernt wurde
- Diese Eigenschaft kann aus Datenschutz- oder Sicherheitsgründen nützlich sein
- Dieser Algorithmus senkte erstmals die obere Schranke von 1981 und reduzierte die durchschnittliche Einfügezeit auf ((log n)^{1.5})
- Kuszmaul fand es überraschend, dass ein Werkzeug, das normalerweise für Privatsphäre genutzt wird, einen Algorithmus schneller machen kann
- Helen Xu vom Georgia Institute of Technology bewertete die Idee, History Independence aus anderen Gründen als Sicherheit zu nutzen, als potenziell einflussreich auch für andere Probleme
Neueste Forschung: Begrenzte Vergangenheitsinformationen plus Randomisierung
- Bender, Kuszmaul und andere senkten in der neuesten Arbeit die obere Schranke erneut und erreichten ((log n)(log log n)^3)
- Dieser Wert entspricht ((log n)^{1.000…1}) und liegt sehr nahe an der fundamentalen unteren Schranke (log n)
- Der neue Ansatz ist ebenfalls nicht-glatt und randomisiert, verwendet diesmal aber eine begrenzte history dependence
- Der Algorithmus betrachtet einen Teil vergangener Trends, um auf künftige Einfügungen vorbereitet zu sein
- Wenn viele Bücher von Autoren mit N am Anfang des Nachnamens hereinkommen, etwa Nabokov, Neruda oder Ng, bleibt im N-Bereich etwas mehr freier Platz
- Wird jedoch zu viel Platz reserviert, kann das problematisch werden, wenn später viele Bücher von Autoren mit A hinzukommen
- Bender erklärte, dass dieser Ansatz nützlich wurde, weil man strategisch randomisierte, wie viel Vergangenheit in Entscheidungen einfließt
- Seth Pettie bewertete die neue Arbeit so, dass sie Randomisierung auf eine völlig andere Weise nutzt als die Veröffentlichung von 2022
Verbleibende Lücke und mögliche Anwendungen
- Die verbleibende Lücke ist ein kleiner (log log n)-Term
- Bender sagte, es sei noch unklar, ob die obere Schranke weiter gesenkt oder die untere Schranke angehoben werden müsse
- Pettie meint, wenn die Lücke so klein ist und eine Grenze natürlich, die andere aber unnatürlich wirkt, setze sich meist die natürlichere Grenze durch
- Künftige Verbesserungen würden daher eher die obere Schranke auf (log n) senken
- Er fügte jedoch hinzu: „Die Welt ist voller seltsamer Überraschungen.“
- Brian Wheatman von der University of Chicago sieht in diesen Arbeiten theoretisch eine beträchtliche Verbesserung und auch in Anwendungen erhebliches Potenzial
- Helen Xu interessiert sich seit Kurzem für die Speicherung und Verarbeitung dynamischer Graphen mit auf List Labeling basierenden Datenstrukturen und erwartet, dass dieser Fortschritt sie fast sicher schneller machen wird
1 Kommentare
Hacker-News-Kommentare
Mich hat ebenfalls überrascht, dass „ein Werkzeug, das für Datenschutz eingesetzt wurde, auch andere Vorteile bringen kann“.
Wenn man genauer darüber nachdenkt, geht es bei Performance meist nicht buchstäblich darum, „mehr Befehle pro Stunde auszuführen“, sondern eher darum, eine Methode zu wählen, mit der man weniger Arbeit erledigen muss.
Die Sicherheitseigenschaft der History Independence bedeutet hier auch: „Man muss die Historie nicht nachverfolgen, und buchstäblich kann man es auch nicht.“ Dadurch wirkt es wie ein interessanter Performance-Ansatz, Kryptografie als Einschränkung zu nutzen, um unnötige Arbeit zu verhindern.
Soweit ich es verstehe, ist es ein Modell, in dem man beliebig viel Rechenzeit verwenden darf.
Wenn man zum Beispiel weiß, dass eine Liste sortiert ist, kann man binäre Suche verwenden. Vielleicht kann aber auch die Wahl, wie viel Information man weglässt, zentral sein. Solche Fälle sieht man allerdings seltener, und ein einfaches Beispiel fällt mir nicht sofort ein.
Frage mich, ob ich der Einzige war, der versucht hat, die zentralen Papers zu finden, die der Artikel beschreibt, also das ursprüngliche Problem und den nahezu optimalen Algorithmus [1], [2].
Beide scheinen irgendwo tief im Artikel verlinkt zu sein; es wäre für Leser sehr hilfreich, wenn Quanta am Ende eines Artikels verpflichtend alle Referenzen sammeln würde.
[1] Nearly Optimal List Labeling:
https://arxiv.org/abs/2405.00807
[2] A sparse table implementation of priority queues:
https://link.springer.com/chapter/10.1007/3-540-10843-2_34
In „This problem was introduced in a 1981 paper“ verlinkt „1981 paper“ auf https://link.springer.com/chapter/10.1007/3-540-10843-2_34, und im nächsten Absatz, „Last year, in a study that was presented at the Foundations of Computer Science conference in Chicago, a team of seven researchers“, verlinkt „a study“ auf https://arxiv.org/abs/2405.00807.
Beide stehen im dritten bzw. vierten Absatz der Einleitung, noch bevor es in Details, Geschichte und Kontext geht. Wenn das schon als „tief im Artikel“ gilt, müssen unsere Maßstäbe für tief ziemlich unterschiedlich sein.
Genau dieses Problem habe ich mir letzte Woche angesehen. Ich wollte Einträge in einer Datenbanktabelle an beliebige Positionen setzen, dabei aber möglichst den Rest der Liste unangetastet lassen.
Wenn ein Nutzer nach Eintrag 5 ein neues Element hinzufügt, wird dieses Element zu 6, aber die bereits hinter 5 vorhandenen Einträge werden nicht aktualisiert. Es gibt tatsächlich sehr ausgefeilte Algorithmen, die dieses Problem verwalten und die theoretischen Grenzen minimieren.
Für diese konkrete Variante schien mir aber die einfachste Lösung zu sein, Fractional Indexing zu verwenden und gelegentlich die Kosten für eine Neuverteilung der Liste zu tragen.
Im Grunde funktioniert er gut, wenn der Labelraum im Verhältnis zur Anzahl der Einträge groß ist. Wenn nicht, braucht man ausgefeiltere Methoden. Wenn man zum Beispiel nur 4 Bytes für Labels hat und eine Milliarde Einträge, wird es problematisch.
Soweit ich mich erinnere, bestand die praktische Lösung darin, Lücken zwischen den Elementen zu lassen. Also zum Beispiel statt 0, 1, 2 eher 0, 100, 200 zu verwenden und bei Bedarf neu zu indizieren. Das dürfte ausreichend gut funktionieren.
Was mir einfiel, war wie gesagt Fractional Indexing; weil Dezimalzahlen lästig sind, stellt man es als Vektor dar und kann es als Zahlen-String ausdrücken, der lexikografisch sortiert wird.
Ein zwischen 1 und 2 eingefügtes Element bekommt den Index 11. Zwischen 11 und 19 ist alles möglich. Zwischen 1 und 11 wäre es 101, zwischen 11 und 2 wäre es 12 und so weiter. Diese Indizes sind allerdings keine Zahlen, sondern Strings, die lexikografisch verglichen werden.
Es gibt sicher auch klare Nachteile. Zum Beispiel verbraucht das Sortieren solcher Indizes deutlich mehr Speicher, weil Strings viel größer sind als Zahlen. Es fühlt sich auch zu clever an, als dass es keine unerwarteten Nachteile hätte.
In der Praxis ist diese Grenze zwar sehr eingeschränkt, aber wenn man die Labels nicht einfach nur als Ordnungslabels für eine Collection nutzt, sondern sie direkt als Array-Indizes verwendet, um Elemente zu speichern, wird der Unterschied wirklich zum Problem. Das modelliert das Bibliothekssortierproblem im wörtlicheren Sinn.
Ich erinnere mich, dass ich vor einigen Jahren Studierenden ein Problem vorgestellt habe, das auf dem Library Sort-Algorithmus basierte.
Der Titel des ursprünglichen Papers ist mir noch immer klar im Gedächtnis: „Insertion Sort is O(n log n)“
Der Titel wirkt ziemlich clickbaitig.
Ich frage mich, ob es einen Grund gibt, warum dieser Algorithmus in der Praxis wirklich schneller sein sollte als die derzeit verwendeten Ansätze.
Der Ort, an dem mir dieses Problem hauptsächlich begegnet ist, sind Arrays in B-Tree-Knoten; dort bezweifle ich, dass es schneller wäre, als einfach
memmove()zu verwenden. Und bei wirklich großen Arrays dürfte es einfacher sein, gleich einen B-Tree zu verwenden.Damit gehört auch dieser Algorithmus zu der Kategorie, die asymptotisch zwar schneller ist, paradoxerweise aber langsamer als die praktisch eingesetzten Algorithmen. Ein Beispiel sind schnelle Algorithmen zur Matrixmultiplikation, die langsamer sind als ein gut implementierter lehrbuchmäßiger O(n^3)-Algorithmus (GEMM).
Das erste Beispiel auf der Seite enthält ein Zitat, das ihren Nutzen gut erklärt:
„Als Beispiel für einen galactic algorithm basiert die schnellste bekannte Methode zur Multiplikation zweier Zahlen auf einer 1729-dimensionalen Fourier-Transformation. Sie benötigt nur O(n log n) Bitoperationen, wird aber wegen der großen in der Big-O-Notation versteckten Konstanten in der Praxis nicht verwendet. Dennoch zeigt sie, warum solche Algorithmen nützlich sein können. Die Autoren sagen, sie hofften, dass sie durch weitere Verbesserungen schon für Zahlen mit Milliarden oder Billionen von Stellen praktisch einsetzbar werde.“
Die Aussage, dass man „die obere Schranke auf (log n) × (log log n)^3 senkt — entsprechend (log n)^(1,000...1)“, stimmt.
Eine der schönen Eigenschaften, wenn man Big-O-Komplexität anhand polynomialer Referenzklassen betrachtet, ist, dass Logarithmen infinitesimale Werte liefern. Ein Treffer gegen Leute, die sagen: „Infinitesimale gibt es eigentlich nicht.“
Ich war überrascht zu erfahren, wie die British Library Millionen von Büchern und jede Woche zahlreiche Neuerscheinungen verwaltet.
Das erste Buch, das Anfang dieses Jahres einging, wurde an die Regalposition 2025.0000001 gestellt, das nächste direkt daneben an 2025.0000002. Den Rest erledigt der elektronische Katalog.
Man muss die Bücher nicht neu umsortieren, aber es ist eine Lösung, die nicht dazu passt, durch die Regale zu gehen und Bücher zu suchen.
Vielmehr wird Ähnlichkeit absichtlich vermieden, damit Picker nicht aus Versehen einen ähnlichen, aber falschen Artikel greifen.
Auch zu Hause vergesse ich oft, wohin ich Dinge gelegt habe, die ich nur gelegentlich benutze — etwa in welchem Schrank und in welcher Box die Ersatzklingen für das X-Acto-Messer liegen. Weil ich versuche, ähnliche Dinge zusammenzulegen, quillt eine Box über, während eine andere nur halb voll ist.
Manchmal stelle ich mir vor, all meinen Besitz in einer Tabelle zu erfassen und festzuhalten, in welcher Box er liegt; dann würde ich nichts mehr verlieren und den Stauraum maximal effizient nutzen. Aber es ist absehbar, dass ich beim Einräumen neuer Dinge das Update vergessen würde, und es fühlt sich wie eine unmenschlich seltsame Methode an, die eher ein Roboter anwenden würde als ein Mensch.
Die Animation ganz oben im Artikel hat in mir den Wunsch geweckt, daraus einen Bildschirmschoner zu machen.
Ich versuche gerade, die zentrale Einschränkung zu verstehen. Geht die Problemdefinition von einem vorab allokierten Array fester Länge aus?
insert(X),delete(X),label(X)labelliefert das Label eines Elements X, das zuvor eingefügt und noch nicht gelöscht wurde. Das Label ist eine Zahl von 0 bis n-1, wobei n die Anzahl der aktuell gespeicherten Elemente ist.