- Der Median lässt sich durch Sortieren leicht bestimmen, aber wegen der Sortierkosten bleibt man auch beim Auswahlproblem für ein einzelnes Element an die Grenze von O(n log n) gebunden
- quickselect durchsucht rekursiv nur die benötigte Seite und kann das k-te Element oder den Median im Durchschnitt in O(n) finden
- Zufällige Pivots funktionieren in der Praxis gut, aber wenn wiederholt schlechte Pivots gewählt werden, wird pro Schritt nur ein Element entfernt, wodurch sich die Laufzeit bis auf O(n²) verschlechtern kann
- median-of-medians wählt aus den Medianen von Gruppen zu je 5 Elementen erneut den Median, sodass selbst im Worst Case mindestens 30 % der Elemente entfernt werden können
- In realen Implementierungen können die Kosten für die Pivot-Berechnung hoch sein; daher kann introselect, das wie in der C++-Standardbibliothek quickselect und heapselect kombiniert, die praktischere Wahl sein
Grenzen der Medianbestimmung durch Sortieren
- Die einfachste Medianberechnung besteht darin, die Liste zu sortieren und anschließend den Wert am mittleren Index auszuwählen
- Bei Listen ungerader Länge wird das mittlere Element zurückgegeben, bei Listen gerader Länge der Durchschnitt der beiden mittleren Elemente
- Die beste Zeitkomplexität vergleichsbasierter Sortierverfahren liegt bei O(n log n), daher wird auch die Laufzeit dieses Ansatzes vom Sortieren dominiert
- Der Vorteil ist einfacher Code, aber um nur einen Median zu finden, wird mehr Arbeit als nötig geleistet
quickselect für durchschnittlich O(n)
- quickselect ist ein rekursiver Algorithmus von Tony Hoare und kann nicht nur den Median, sondern ein beliebiges k-tes Element einer Liste finden
- Der Grundablauf besteht darin, die Liste anhand eines Pivots aufzuteilen und dann nur auf der Seite weiterzusuchen, die das k-te Element enthält
- Einen Pivot aus der Liste auswählen
- Die Liste in Elemente kleiner oder gleich dem Pivot und Elemente größer als der Pivot aufteilen
- Bestimmen, auf welcher Seite das gesuchte k-te Element liegt, und nur auf dieser Teilliste rekursiv aufrufen
- Beim Abstieg in die rechte Teilliste den Wert von k um die Anzahl der bereits ausgeschlossenen linken Elemente anpassen
- In der Beispielliste
[9,1,0,2,3,4,6,8,7,10,5] sucht man wegen der Länge 11 das 6.-kleinste Element, grenzt den Bereich je nach Pivot ein und gibt schließlich 5 zurück
quickselect_median sucht bei ungerader Listenlänge mit quickselect den einen mittleren Index; bei gerader Länge werden die beiden mittleren Indizes gesucht und gemittelt- Wenn der Pivot die Liste annähernd halbiert, beträgt die verarbeitete Menge
n + n/2 + n/4 + ... = 2n und damit O(n)
Um den Worst Case zu vermeiden, braucht man einen guten Pivot
- Das durchschnittliche O(n) von quickselect beruht auf der Annahme, dass die Pivot-Wahl hinreichend gut ist
- Hat man Pech und wählt etwa in jedem Schritt das Maximum als Pivot, wird pro Schritt nur ein Element entfernt, was zu O(n²) führt
- Um auch im Worst Case lineare Zeit zu garantieren, muss quickselect in linearer Zeit einen ausreichend guten Pivot erhalten
- Dieser Algorithmus zur Pivot-Wahl wurde 1973 von Blum, Floyd, Pratt, Rivest und Tarjan entwickelt; der zugehörige Aufsatz ist als 1973 paper verlinkt
Pivot-Wahl mit median-of-medians
- median-of-medians ist ein Verfahren, um einen guten Pivot für quickselect auszuwählen
- Der Ablauf der Implementierung ist wie folgt
- Wenn es weniger als 5 Elemente gibt, wird die bestehende sortierbasierte Medianfunktion verwendet
- Die Liste wird in Gruppen zu je 5 Elementen aufgeteilt
- Unvollständige Gruppen mit weniger als 5 Elementen werden der Einfachheit halber verworfen
- Jede Gruppe wird sortiert und der Median an Index 2 gesammelt
- Aus der Liste der gesammelten Mediane wird erneut der Median gesucht und als Pivot zurückgegeben
- Da jede Gruppe eine feste Größe von 5 hat, gilt das Sortieren pro Gruppe als konstante Zeit; insgesamt ist es eine Arbeit von O(n)
- Der rekursive Aufruf zur Bestimmung des Medians der Mediane geht als Teilproblem der Größe
n/5 in die Analyse ein
Warum sich mindestens 30 % entfernen lassen
- Wenn man die 5er-Gruppen sortiert und als Spalten anordnet und dann die Mediane jeder Spalte erneut sortiert, um den Median der Mediane auszuwählen, lässt sich die Qualität des Pivots analysieren
- Selbst im Worst Case, in dem der Pivot so weit vorne wie möglich liegt, ist garantiert, dass die Elemente in bestimmten Quadranten kleiner bzw. größer als der Pivot sind
- Nimmt man aus jeder Spalte 3 Elemente und betrachtet die Hälfte der Spalten, lassen sich mindestens
3/5 * 1/2 * n = 3/10 n Elemente entfernen
- Garantierter Entfernungsanteil: {p:30}
- Die gesamte Laufzeit wird durch folgende Rekurrenz beschrieben
T(n) = n + T(n/5) + T(7n/10)
- Dabei entspricht
n der Partitionierungsarbeit, T(n/5) der Berechnung von median-of-medians und T(7n/10) der rekursiven Suche von quickselect
- Da diese Rekurrenz zwei rekursive Terme enthält, lässt sich das einfache Master-Theorem nicht anwenden; Induktion ist die intuitivere Beweismethode
Kombiniertes Ergebnis: Medianfindung in linearer Zeit
- quickselect kann den Median in linearer Zeit finden, wenn ein ausreichend guter Pivot gegeben ist
- median-of-medians kann den für quickselect nötigen guten Pivot in O(n) auswählen
- Kombiniert man beide Algorithmen, erhält man einen Algorithmus, der den Median oder das n-te Element einer Liste in linearer Zeit findet
Auswahl in realen Implementierungen
- In der Praxis reicht eine zufällige Pivot-Wahl fast immer aus
- Auch median-of-medians hat lineare Laufzeit, kann in der Praxis wegen der hohen Kosten der Pivot-Berechnung aber langsam sein
- Die C++-Standardbibliothek verwendet introselect, kombiniert heapselect mit quickselect und hat eine obere Schranke von O(n log n)
- introselect beginnt üblicherweise mit einem Algorithmus, der schnell ist, aber eine schlechte obere Schranke hat, und wechselt zu einem langsameren Algorithmus mit besserer Schranke, wenn kein effektiver Pivot gewählt werden kann
- In einem Vergleich der von der quickselect-Funktion betrachteten Elementanzahlen berücksichtigte ein deterministischer Pivot fast immer weniger Elemente als ein zufälliger Pivot; die Kosten für die Berechnung von median-of-medians sind darin jedoch nicht enthalten
- Ein new paper aus dem Jahr 2017 beschreibt, wie der median-of-medians-Ansatz mit anderen Auswahlalgorithmen konkurrenzfähig gemacht werden kann
1 Kommentare
Hacker-News-Kommentare
Vor etwa 4 Jahren habe ich verschiedene Median-Algorithmen verglichen, und der Artikel ist viel länger geworden als erwartet :)
https://danlark.org/2020/11/11/miniselect-practical-and-generic-selection-algorithms/
Vor 10–15 Jahren musste ich regelmäßig den Median von Milliarden von Werten finden, die aus mehreren Kilobyte großen Log-Einträgen geparst wurden. Für große Datenmengen haben wir damals MapReduce verwendet, und bei Daten dieser Größenordnung brauchte man nicht nur lineare Zeit, sondern möglichst auch ein Verfahren, das sich in einem einzigen Durchlauf auf mehrere Maschinen verteilen lässt
Hilfreich war, dass wir die Präzision und den Bereich der Daten kannten. Die Werte waren Zeitangaben in ganzen Millisekunden, also nicht negativ, und wir wussten auch, dass das 90. Perzentil deutlich unter 1 Sekunde lag
Normalerweise erfordert das Finden des Medianwerts eine Arbeit, die dem Sortieren ähnelt, aber unter solchen Bedingungen wird Bucket Sort möglich. Man erstellt einfach ein Dictionary, also ein Histogramm, bei dem der Schlüssel die Zeit in ganzzahligen Millisekunden ist und der Wert die Anzahl der Vorkommen
Da wir die maximale Zeit nicht kannten, haben wir alle Werte über 999 ms in den 999-ms-Bucket gelegt, damit die Größe des Dictionarys nicht explodiert; damit war es auf insgesamt etwa 2000 Integer für die Schlüssel und Werte von 0–999 begrenzt. Das unterschied sich von gewöhnlichem Bucket Sort, ließ sich aber selbst verteilt mit MapReduce sehr leicht in einem einzigen Durchlauf verarbeiten, und danach musste man nur noch den Median aus dem Histogramm ziehen
Die Zahl 10.000 ist nur frei gewählt, aber die für das gewünschte Konfidenzniveau nötige Stichprobengröße lässt sich statistisch berechnen und dürfte nicht so riesig sein
In einigen Systemen, mit denen ich zu tun hatte, schien Prometheus eine Begrenzung von etwa 10 Sekunden für Latenz zu haben. Anfragen, die darüber lagen, wurden daher alle als 10 Sekunden erfasst, obwohl sie in Wirklichkeit länger gedauert haben konnten. Interessant
Es gibt ein Nachwort, dass 2017 eine neue Arbeit erschienen ist, die den Median-of-Medians-Ansatz konkurrenzfähig zu anderen Selektionsalgorithmen gemacht hat, und dass der Autor der Arbeit, Andrei Alexandrescu, darauf hingewiesen hat
Er hat 2016 auch einen Vortrag über seinen Algorithmus gehalten. Er ist ein unterhaltsamer Redner, daher eine klare Empfehlung
There's Treasure Everywhere - Andrei Alexandrescu
https://www.youtube.com/watch?v=fd1_Miy1Clg
Wer mit Software arbeitet, sollte sich alles von Andrei anhören und lesen, was man finden kann. Auch dieser Vortrag ist ein echter Schatz
Im Grundstudium habe ich den median-of-medians quickselect-Algorithmus gelernt, und er hat mich wirklich beeindruckt. Ich habe ihn selbst implementiert, aber er war schrecklich langsam. Die Laufzeit wuchs zwar linear, aber damit das praktisch relevant gewesen wäre, hätte die Liste mindestens viele Milliarden Elemente haben müssen
Als ich darüber mit einem befreundeten Doktoranden sprach, sagte er sinngemäß: „Er ist langsam, aber das Wichtige ist, dass er beweist, dass man in einer unsortierten Liste in O(n)-Zeit selektieren kann. Früher wusste man nicht einmal, ob das möglich ist, und jetzt, da wir wissen, dass es möglich ist, könnte es auch schnellere lineare Algorithmen geben.“
Das war so eine einfache und zugleich tiefgründige Einsicht, dass ich mich fast für ein Graduiertenstudium beworben hätte. Ich weiß nicht, ob mein Freund sich an dieses Gespräch erinnert, aber für meine Ausbildung war es eine Art Wendepunkt
Man könnte ja auch denken: „Da wir schon wissen, dass irgendein Algorithmus existiert, könnte es auch einen schnelleren geben.“ Warum ist die Existenz eines O(n)-Algorithmus ein stärkeres Signal als die Existenz eines O(n log n)-Algorithmus?
Ich meine, der konstante Faktor dieses Algorithmus lag bei etwa 22, obwohl es auch ein verwandter Algorithmus gewesen sein könnte
Einer der interessanten Punkte am median-of-medians-Algorithmus ist, dass die Autorenliste durchweg Starbesetzung ist
Manuel Blum – Turing-Preisträger 1995
Robert Floyd – Turing-Preisträger 1978
Ron Rivest – Turing-Preisträger 2002
Bob Tarjan – Turing-Preisträger 1986 und erster Nevanlinna-Preisträger 1982
Vaughan Pratt – als Einziger auf der Liste kein Turing-Preisträger, aber emeritierter Stanford-Professor; er leitete das SUN-Projekt, bevor daraus Sun Microsystems wurde, spielte in den frühen Jahren von Sun eine wichtige Rolle als Forschungsleiter und Designer des Sun-Logos und hat außerdem viele coole Dinge hinterlassen, etwa die Pratt-Zertifikate für Primzahlen
Vier unabhängige Turing-Preise und sogar eine SPARCstation, dieses Paper hat alles
Die Autorenliste ist auf jeden Fall beeindruckend
Das „P“ in KMP steht ebenfalls für Pratt
return l[len(l) / 2]Ich bin kein Python-Experte, aber liefert der
/-Operator in Python nicht einen Float zurück? Warum verwendet man statt eines Floats als Array-Index nicht die Ganzzahldivision//?Bei sehr großen Arrays mag das kein Problem sein, aber es riecht trotzdem ziemlich nach Code Smell. Wenn man Python-Anfänger ist und nicht wusste, dass es zwei verschiedene Operatoren gibt, könnte man das noch durchgehen lassen, aber im Artikel gibt es noch seltsameren Code, der in einem Zweig Ganzzahldivision und im anderen Fließkommadivision verwendet
def quickselect_median(l, pivot_fn=random.choice):if len(l) % 2 == 1:return quickselect(l, len(l) // 2, pivot_fn)else:return 0.5 * (quickselect(l, len(l) / 2 - 1, pivot_fn) +quickselect(l, len(l) / 2, pivot_fn))Es gibt schon 50 Kommentare und anscheinend hat das niemand bemerkt, was nur meine bisherigen Vorurteile über die durchschnittliche Python-Codequalität weiter bestätigt
Wenn man mit einem Float auf ein Array indexiert, sollte das eine Exception auslösen
Statt Pseudocode wurde eine echte Programmiersprache gewählt, die wie Pseudocode aussieht, und als erklärender Code ist das vermutlich in Ordnung
Den Originaltext habe ich wirklich gern gelesen, aber an der Stelle „Wenn man in jedem Schritt das größte Element als Pivot wählt, kann aus O(n) statt O(n²) werden“ bin ich hängen geblieben
Wenn man sich Sorgen über adversariale Eingaben macht, kann man die Daten vorher in O(n) durchmischen, um zu verhindern, dass so etwas absichtlich herbeigeführt wird. Wenn die Daten zu groß sind, um sie leicht zu mischen, genügt es, einmal zu mischen, sobald der Bucket auf eine Größe geschrumpft ist, die sich mischen lässt
Wenn man gemischt hat, garantiert die Wahrscheinlichkeit, dass der Worst Case praktisch nicht eintritt. Wenn jemand sagt, dass es „technisch gesehen“ möglich sei, würde ich antworten, dass ein Angreifer „technisch gesehen“ auch alle Bits eines 256-Bit-Privatschlüssels erraten könnte
Unsere Welt ist auf Wahrscheinlichkeit aufgebaut. Jeder private Schlüssel ist dadurch geschützt, dass ihn praktisch niemand exakt erraten kann, nicht durch mathematische Unmöglichkeit
Soweit ich gelesen habe, ist quickselect nach dem Mischen in der Praxis O(n)
Wenn man der Zufälligkeit vertraut, ist die Wahrscheinlichkeit für eine Laufzeit über O(n) ohnehin sehr klein
Floyd-Rivest schafft das ebenfalls. Wenn ich mich richtig erinnere, sogar etwas effizienter
Aber ich habe nie wirklich verstanden, wie es funktioniert
https://en.m.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm
Wenn man das n-te Element auswählt und n sehr klein oder sehr groß ist, ist median-of-medians möglicherweise nicht optimal
Stattdessen kann man einen verzerrten Pivot wie in [1] verwenden oder etwas, das ich „j-tes von k-tem“ nenne. Auch Floyd-Rivest kann schneller sein
Es gibt ein Hobbyprojekt mit einem Durchsatz von 1,2- bis 2,0-fach im Vergleich zu gut implementiertem quickselect: https://github.com/koskinev/turboselect
Ich wäre an Material zu schnellen generischen In-Place-Selektionsalgorithmen interessiert
[1] https://doi.org/10.4230/LIPIcs.SEA.2017.24
Man könnte auch einen Streaming-Algorithmus verwenden, um eine Approximation eines beliebigen Quantils zu berechnen, ohne den gesamten Datensatz im Speicher zu halten
Kann man eine approximative Berechnung überhaupt zulassen? Welche Annahmen über die Daten braucht man, um Fehlerschranken festzulegen? Wie überprüft man, dass diese Annahmen weiterhin gelten?
Persönlich würde ich wohl eher zum im Original genannten quickselect-Algorithmus tendieren, bis ich wirklich in eine Situation komme, in der ich eine approximative Streaming-Median-Berechnung überhaupt in Betracht ziehen muss