Einführung
- Ein neuer Algorithmus zeigt einen Weg, das Problem des Sortierens in Bibliotheken zu lösen.
- Das Problem gilt nicht nur für das bloße Sortieren von Büchern, sondern auch für die Anordnung von Dateien auf Festplatten und in Datenbanken.
- Der neue Ansatz kombiniert den bisherigen Inhalt des Regals mit Zufälligkeit und erzielt damit Ergebnisse, die dem theoretischen Ideal nahekommen.
Die Grenze einengen
- Eine gängige Methode, ein gut sortiertes Bücherregal zu messen, besteht darin, die Zeit zu betrachten, die das Einfügen einzelner Elemente benötigt.
- Eine Arbeit aus dem Jahr 1981 stellte die Frage, ob sich ein Algorithmus entwerfen lässt, dessen durchschnittliche Einfügezeit deutlich unter n liegt.
- Eine Studie aus dem Jahr 2004 fand heraus, dass die optimale untere Schranke für das Bibliothekssortierproblem bei log n liegt.
- Sie zeigte, dass sich mit glatten oder deterministischen Algorithmen keine durchschnittliche Einfügezeit erreichen lässt, die besser als (log n)² ist.
Eine verborgene Geschichte
- 2022 versuchten Bender und seine Kollegen einen zufälligen und nicht-glatten Algorithmus und senkten die durchschnittliche Einfügezeit auf (log n)¹.⁵.
- Dieser Algorithmus stützt sich nicht auf frühere Aufzeichnungen des Bücherregals, was aus Sicherheitsgründen nützlich sein kann.
Die Lücke schließen
- Bender und Kuszmaul senkten die obere Schranke auf (log n) × (log log n)³ und kamen damit der theoretischen unteren Schranke sehr nahe.
- Der Algorithmus nutzt in begrenztem Maß Historienabhängigkeit, um künftige Ereignisse zu planen.
- Das Ergebnis baut auf früherer Forschung auf und nutzt Zufälligkeit auf eine völlig andere Weise.
Fazit
- Die Forschung stellt aus theoretischer Sicht eine wichtige Verbesserung dar und hat auch mit Blick auf Anwendungen großes Verbesserungspotenzial.
- Dennoch verhindert der Term log log n weiterhin eine vollständige Lösung; eine niedrigere obere Schranke oder eine höhere untere Schranke könnte die Antwort sein.
1 Kommentare
Hacker-News-Kommentare
Interessant, dass kryptografische Techniken zur Leistungssteigerung eingesetzt werden können. Performance bedeutet nicht einfach, mehr Anweisungen auszuführen, sondern zu entscheiden, wie man weniger Arbeit erledigt. Die Sicherheitseigenschaft „Historienunabhängigkeit“ bedeutet, dass keine Arbeit zur Nachverfolgung der Vergangenheit geleistet wird
Es ist schwierig, die im Artikel erwähnten Hauptarbeiten zu finden. Es wäre hilfreich für die Leser, wenn Quanta alle Literaturverweise am Ende des Artikels auflisten würde
Es gibt komplexe Algorithmen, um das Problem zu lösen, Einträge in einer Datenbanktabelle an beliebigen Positionen zu platzieren. Eine einfache Lösung für dieses Problem ist jedoch, Bruchwerte zu verwenden und die Liste gelegentlich neu anzuordnen
Ich erinnere mich, dass ich Studenten auf Basis des Algorithmus „Library Sort“ Aufgaben zu diesem Problem gestellt habe. Der Titel der ursprünglichen Arbeit lautet „Insertion Sort is O(n log n)“
Ich frage mich, ob es einen Grund gibt, warum das in der Praxis tatsächlich schneller sein sollte als die derzeit verwendeten Algorithmen. In den Arrays von B-tree-Knoten könnte die Verwendung von
memmove()schneller sein. Bei großen Arrays ist die Verwendung von B-Bäumen einfacherIch frage mich, ob die Problemformulierung ein vorab allokiertes Array fester Länge voraussetzt
Ich bin überrascht, wie die British Library Bücher verwaltet. Wenn ein Buch ankommt, kümmert sich der elektronische Katalog um den Rest, sodass Bücher nicht umsortiert werden müssen
Ich möchte die Animation oben im Artikel als Bildschirmschoner haben
Saubere Links für mobile Nutzer
Es stimmt, dass die obere Schranke auf (log n) mal (log log n)^3 gesenkt wird. Es ist interessant, dass Logarithmen in der Big-O-Komplexität unter Verwendung polynomieller Referenzklassen infinitesimale Werte liefern