Disclaimer: Diese Mitschrift ist als Ergänzung zur Vorlesung gedacht. Wir erheben keinen Anspruch auf Vollständigkeit und Korrektheit. Wir sind jederzeit froh um Hinweise zu Fehlern oder Unklarheiten an grafdan@ethz.ch.
Wenn Sie an dieser Mitschrift mitarbeiten möchten, melden Sie sich hier.
Wir wollen heute die Techniken zum Entwurf und zur Analyse von Algorithmen, die wir letzte Woche gesehen haben, auf ein erstes Themengebiet anwenden: das Suchen in Datenmengen. Wir nehmen an, dass wir Datensätze vor uns haben, die je durch einen Schlüssel identifiziert werden. Ein Array mit Elementen bezeichnet die Schlüsselmenge dieser Datensätze und wir bekommen nun einen weiteren Schlüssel , den wir in der Menge suchen. Wir wollen also wissen ob es einen Index gibt, sodass gilt.
Der Einfachheit halber nehmen wir meist an, dass diese Schlüssel positive ganze Zahlen sind. Es können aber auch genausogut Zeichenketten wie in einem Wörterbuch sein. Ein Beispiel:
Wir haben letzte Woche auch gelernt, dass niemand von Ihnen die Rektorin kennt. Darum dachte ich mir, schlage ich mal im ETH-Who-is-who nach, was ich über Sarah Springman herausfinde. Das ist ein dickes Buch mit 1521 Seiten und den Angaben zu rund 45'000 ETH-Absolventen.
Wenn wir nun die Rektorin darin von vorne nach hinten suchen kann das lange dauern. Man muss nicht Informatik studieren um zu sehen, dass es nicht sinnvoll ist, bei Abel und Abgottspon zu beginnen. Was würden Sie tun?
Das Verzeichnis ist zum Glück alphabetisch sortiert und das wollen wir natürlich ausnutzen. Schlagen wir das Buch in der Mitte auf bei 'Luginbühl' auf, so wissen wir sofort, dass sich die Rektorin nicht in der ersten Hälfte versteckt und können die ersten 760 Seiten von nun an getrost ignorieren. In der Mitte der zweiten Hälfte, auf Seite 1140, sind wir mit 'Sidler' schon ziemlich nahe und können erneut 380 Seiten (die erste Hälfte des Restes) wegwerfen. Nun schauen wir auf Seite und sehen, dass wir mit 'Weibel' übers Ziel hinausgeschossen sind. So ignorieren wir fortan die hintere Hälfte und fahren weiter auf Seite .
TODO Skizze der binären Suche im Buch
Nach rund sieben weiteren Schritten landen wir so auf Seite 1166 zwischen 'Springer' und 'Spross' und stellen fest, dass Prof. Springman nicht an der ETH studierte[1]. Uns interessiert heute aber auch nicht unbedingt der Werdegang der Rektorin, sondern das Suchverfahren, das wir soeben angewendet haben.
Wir haben ausgenutzt, dass das Alumni-Verzeichnis alphabetisch sortiert ist. Wir verlangen also von unseren Schlüsseln in , dass sie entsprechend einer totalen Ordnung sortiert sind. Für ganze Zahlen kann das die aufsteigende Ordnung "<" sein und für Zeichenketten eben die lexikographische Ordnung.
Wie wir Schlüssel sortieren, werden wir nächste Woche im Detail studieren. Für heute nehmen wir einfach an, dass wir bereits sortiert vor uns haben, also
Das Divide-and-Conquer-Verfahren des wiederholten Halbierens und Wegwerfens, das wir vorhin angewandt haben, heisst binäre Suche. Divide-and-Conquer-Verfahren beschreiben wir am einfachsten rekursiv:
In jedem rekursiven Aufruf passen wir also entweder das linke oder das rechte Ende der noch relevanten Teilliste an. Wir können das Verfahren daher auch leicht iterativ formulieren indem wir Schritt für Schritt die Grenzen anpassen:
Wie bereits bekannt, stellen wir uns zu jedem neuen Algorithmus zwei Fragen: Ist er korrekt und ist er schnell?
Die Korrektheit der binären Suche zeigen wir am einfachsten mit Hilfe einer (aus Eiffel wohl bekannten) Schleifeninvarianten. Nach jeder Iteration gilt: "Falls das gesuchte Element in existiert, dann ist es im Bereich ". Wir argumentieren in gewohnter Induktion:
Die Korrektheit folgt nun aus der Invariante und daraus, dass wir die Rekursion nur dann abbrechen, falls kein Elemente mehr übrig ist oder wir gefunden haben.
In jeder Iteration halbiert sich der verbleibende Suchbereich in etwa. Um genau zu sein sind bei einer Suche mit Elementen im nächsten Aufruf noch oder Elemente übrig. Wir können also schreiben:
Wir teleskopieren
was uns zur Vermutung führt: .
Induktionsbeweis
Somit liegt die Laufzeit der binären Suche in .
Führen wir uns das (eindrückliche!) Resultat dieser Analyse nochmals vor Augen. Eine Suche im Telefonbuch von vorne nach hinten skaliert nur linear mit der Grösse des Buches. Fügen wir eine Seite hinzu, so müssen wir im schlimmsten Fall eine Seite mehr anschauen. Fügen wir 100 Seiten hinzu, sind es 100 Schritte mehr. Auch wenn wir etwas cleverer sind und jeweils 10 Seiten auf einmal weiterspringen senkt dies lediglich die Steigung unserer linearen Wachstumskurve und erzielt nichts fundamental Besseres.
Was wir intuitiv machen und soeben analysiert haben, ist ein exponentieller Speedup! Solange das Telefonbuch nicht mehr als doppelt so dick wird, genügt ein einziger zusätzlicher Suchschritt.
In der Praxis kann dies locker den Unterschied zwischen unglaublich langsam und instantan ausmachen. Binäre Suche ist nur einer von vielen Algorithmen mit dieser Eigenschaft und wir wollen zur Illustration kurz ein zweites Beispiel anschauen: Ich würde gerne zählen, wieviele Studierende momentan im Raum sind. Ich könnte nun jeden Sitzplatz durchzählen ( Schritte) oder minimal schneller in Doppelsitzgruppen zählen ( Schritte). Was wir alle gemeinsam machen können ist folgendes Verfahren[2]: (etwas Morgenturnen zur frühen Stunde)
Kopfrechenkünste und einigermassen gleichmässiges Timing vorausgesetzt, können wir so die Anzahl Personen in logarithmisch vielen Schritten bestimmen. Selbst für einen doppelt so grossen Vorlesungssaal würde es also nicht doppelt so lange sondern lediglich einen Schritt länger dauern.
Kehren wir nun zur binären Suche zurück. Die Frage "Geht es noch schneller?", die wir uns letzte Woche antrainiert haben, bleibt noch zu beantworten. Vielleicht finden wir ja gar noch einen besseren Algorithmus in oder gar .
Um zu argumentieren, dass es nicht schneller geht, können wir uns einen beliebigen, deterministischen Suchalgorithmus auch als Entscheidungsbaum vorstellen, der in jedem Knoten einen Schlüsselvergleich durchführt und dann je nach Ergebnis erfolgreich endet oder in einen von zwei Teilbäumen absteigt.
Dieser Suchbaum muss nun mindestens Knoten enthalten, damit jeder mögliche Ausgang berücksichtigt wird, denn der Schlüssel kann ja theoretisch an jeder Position im Array stehen. Die Worstcase-Laufzeit des Suchalgorithmus entspricht nun der Tiefe des Baumes, also dem längsten Pfad von der Wurzel zu einem Blatt. Ein Binärbaum der Höhe hat höchstens Knoten, daher impliziert die Bedingung dass gelten muss. Somit hat jeder Algorithmus mindestens logarithmische Laufzeit und die binäre Suche ist asymptotisch optimal!
Mit einem ähnlichen Argument, können wir auch zeigen, dass wir selbst im Mittel nicht schneller sein können als logarithmisch.
Die binäre Suche hat eine lange Geschichte und ist bekannt dafür, zwar einfach auszusehen aber trotzdem fehleranfällig in der Implementierung zu sein.
Donald Knuth schreibt in seinem Buch[3], dass die binäre Suche 1946 wohl als erster nichtnumerischer Algorithmus publiziert wurde, aber fünfzehn Jahre lang niemand korrigierte, dass das beschriebene Verfahren nur für der Form funktionierte. Jon Bentley behauptet in "Programming Pearls" gar, dass es selbst unter Berufsprogrammierern nur rund 10% der Kandidaten gelingt die binäre Suche fehlerfrei zu implementieren und alle möglichen Endlosschleifen und Randfälle zu vermeiden[4].
Es gibt aber auch viele durchaus sehr berechtigte Abwandlungen der binären Suche, die oft nützlich sind und wir nun betrachten wollen.
Vergessen wir die Algorithmik für den Moment und überlegen wir uns, wie wir selber in einem Telefonbuch suchen. Auf der Suche nach "Springman" schlagen wir das Telefonbuch wohl nicht genau in der Mitte sondern eher etwas im hinteren Bereich auf. Wir nehmen an, dass die Nachnamen übers Alphabet halbwegs gleichmässig verteilt sind und "S" daher etwa im letzten Drittel anzutreffen sein sollte.
Genau diese Idee macht sich auch die Interpolationssuche zu Nutze. Statt zu wählen, interpolieren wir zwischen den Schlüsseln am Rand linear und erhalten so
Diese Schätzung ist natürlich nur dann gut, wenn die Schlüsselwerte im Suchbereich einigermassen gleich verteilt sind. Im schlimmsten Fall ist diese Schätzung miserabel und die Interpolationssuche betrachtet jeden einzelnen Schlüssel. Überlegen Sie sich doch als Übungsaufgabe eine Eingabe, bei der diese Worst-Case-Laufzeit eintritt.
Man kann jedoch auch zeigen (was wir hier jedoch nicht tun), dass die Interpolationssuche im Mittel nur rund Vergleiche braucht, wenn die Schlüssel unabhängig gleich verteilte Zufallszahlen sind. Auf gutmütigen Eingabedaten kann dies also durchaus nochmals einen asymptotischen Geschwindigkeitszuwachs bedeuten.
Denksportaufgabe: Überlegen Sie sich wie Sie die Vorzüge der binären Suche und Interpolationssuche in einen einzigen Algorithmus kombinieren können.
Die binäre Suche und die Interpolationssuche setzen voraus, dass wir die Grösse der Schlüsselmenge kennen, bzw. dass wir nur endlich viele Schlüssel vor uns haben.
Für sehr grosse gibt es einen hübschen Trick, der sich exponentielle Suche nennt. Dabei beginnen wir mit dem Bereich und verdoppeln die Länge dieses Intervalls, bis wir sicher sein können, dass ein potentieller Schlüssel mit Wert im Bereich enthalten ist. Ab da führen wir eine binäre Suche auf dem Bereich durch.[5]
Die Schleife in Zeile 3 und 4 endet spätestens nach Iterationen. Asymptotisch bedeutet die exponentielle Suche also keinen Overhead gegenüber der binären Suche. Der Name exponentielle Suche deutet also nicht auf die Laufzeit sondern das exponentielle Wachstum von hin. Falls sich weit vorne in der Schlüsselliste befindet, z.B. an Position , so sind wir bereits nach konstant vielen Schritten fertig, egal wie gross ist. Wenn wir annehmen, dass in alle Schlüssel verschieden sind, also für alle , dann können wir die Laufzeit gar in Abhängigkeit des gesuchten Schlüssels als angeben.
Manchmal wollen wir aber auch explizit erlauben, dass Duplikate enthält, also nur monoton, nicht aber streng monoton anwächst. Wir wollen dann nicht nur irgendeinen Index mit finden, sondern zum Beispiel den kleinsten solchen Index, also das erste Vorkommen von in .
Überlegen Sie sich, wie Sie den Code der binären Suche anpassen müssen, um diesen Index zu finden, ohne die Schleifeninvariante und die Laufzeitanalyse zu verletzen.
Für den Rest der Zeit vor der Pause wollen wir uns nun noch überlegen, wie schnell wir in unsortierten Schlüsselmengen suchen können. Das naheliegende, simple Verfahren, das die Elemente der Reihe nach mit vergleicht, heisst lineare Suche oder auch sequentielle Suche.
Die lineare Suche ist offensichtlich korrekt und braucht im schlimmsten Fall Schlüsselvergleiche.
Erstes Argument: Ein einfaches Argument, dass wir in unsortierten Mengen mindestens Schlüsselvergleiche brauchen, liegt auf der Hand: Wenn wir nicht jeden Schlüssel mit vergleichen, so riskieren wir Korrektheit, denn genau das Element, das wir nicht anschauen, hätte die Nadel im Heuhaufen sein können.
Dieses Argument ist aber nicht korrekt! Ein Algorithmus darf auch die Elemente von untereinander vergleichen und wir müssen begründen, warum das keine Vergleiche einsparen kann. Theoretisch können wir zum Beispiel bis jetzt nicht ausschliessen, dass ein Algorithmus die Elemente in sagen wir sortiert und dann in weiteren Schritten mittels binärer Suche nach sucht. Dass genau dies nicht passieren kann, weil wir fürs Sortieren mindestens Schlüsselvergleiche benötigen, werden wir nächste Woche sehen aber wer garantiert uns, dass es keine anderen Tricks dieser Art gibt?
Good judgement comes from experience, and experience comes from bad judgement. - Nasreddin
Verbessertes Argument: Sei a die Zahl der Vergleiche, die nicht involvieren, und die Zahl der Vergleiche mit . Die Vergleiche teilen die Elemente in Gruppen ein, sagen wir Gruppen. Dabei sei eine Gruppe definiert als eine Teilmenge der Elemente, sodass darin jedes Paar von Elementen über eine Kette von Vergleichen verglichen wurde.
Zu Beginn ist die Gruppenzahl gleich . Das Zusammenlegen zweier Gruppen benötigt mindestens einen Vergleich. Bei Gruppen, wurden also mindestens Vergleiche benutzt, also .
Um nun nach zu suchen, brauchen wir mindestens einen Vergleich pro Gruppe, also . Somit gilt für die Anzahl Vergleiche .
Passen wir die lineare Suche minimal an, können wir damit auch das minimale Element in unsortierten in Schlüsselvergleichen bestimmen.
Eine interessante Frage dazu: Wenn wir sowohl das Minimum als auch das Maximum bestimen wollen, so können wir das leicht in Schlüsselvergleichen. Doch geht es auch besser?[6]
Hier ein Tipp:
Wir vergleichen die Elemente zuerst paarweise untereinander in Vergleichen. Danach kommt von jedem Paar nur noch das kleinere Element für das Minimum in Frage und analog kann nur noch das grössere das Maximum sein. Somit gelingt es uns insgesamt in Vergleichen[7].
In der zweiten Stunde betrachten wir die Suche nach Rang statt nach Wert. Zuvor stellten wir die Frage "Kommt der Schlüssel in der Menge vor?" und nun wollen wir beantworten "Was ist der -kleinste Schlüssel in ?"
Ein Beispiel: Bei einer Eingabe von und suchen wir das fünftkleinste Element in , also die . Für suchen wir das mittlere Element, den sogenannten Median.
Nehmen Sie doch alle kurz Ihre Legi hervor. Jede/r von Ihnen hat eine eindeutige achtstellige Leginummer (z.B. 10-916-617). Wir sind nun an der Median-Leginummer interessiert, um in etwa herauszufinden wie lange der "durchschnittliche" Student dieser Vorlesung schon immatrikuliert ist. Überlegen Sie sich kurz, wie sie dazu (mit oder ohne Computer) vorgehen würden? Gehen Sie reihum, um alle Leginummern auf Papier zu sammeln? Was machen Sie danach?
In dieser Stunde werden wir nun vier Verfahren sehen (zwei einfache, zwei etwas komplexere), die uns diesen Median bestimmen können.
Wiederholt das Minimum entfernen: Ein erster Ansatz verwendet, was wir vor der Pause gemacht haben: Wir bestimmen das Minimum in und entfernen es aus . Danach ist das insgesamt zweitkleinste Element das Minimum im verbleibenden Array. Für das -te Element wiederholen wir dieses Vorgehen mal in Gesamtlaufzeit .
Das ist nicht sehr praktikabel. Wir fragen "Wer hat die kleinste Leginummer?" und schicken ihn/sie vor die Tür. Das wiederholen wir mal, was dauert.
Sortieren: Ein weiterer naheliegender Ansatz ist die Elemente aufsteigend zu sortieren und dann einfach das -te Element in der sortierten Folge anzuschauen. Wir werden nächste Woche sehen, dass wir in sortieren können - eine drastische Steigerung gegenüber dem naiven .
Häufig sind wir mit bereits zufrieden, doch wir schauen uns jetzt noch zwei Verfahren an, denen es gar in gelingt, das Auswahlproblem zu lösen.
Die Grundidee ist folgende: Wir wählen ein Element aus, das wir als "Pivot"[8] bezeichnen. Nun zählen wir wie viele Elemente kleiner gleich sind und wie viele grösser als sind. Danach schauen wir in welchem der beiden Teile, das -te Element liegen muss und ignorieren den anderen Teil fortan.
Für diesen Aufteilungsschritt gruppieren wir die Schlüssel so um, dass der Pivot zwischen den Elementen kleiner und denen grösser zu liegen kommt, was wir leicht in Schritten tun können. Damit sind die verbleibenden Elemente wieder direkt nebeneinander im Array und wir können unser Verfahren rekursiv auf diesen Teilbereich aufrufen.
Was macht ein gutes Pivot-Element aus? Ein gutes Pivot-Element soll die Schlüsselmenge möglichst gleichmässig aufteilen, sodass wir möglichst viele Elemente fortan ignorieren können. Wenn wir wiederholt gute Pivot-Elemente finden, dann reduziert sich die Schlüsselmenge rapide und wir haben schnell nur noch wenige Schlüssel vor uns.
Im schlimmsten Fall, schliesst ein Pivot aber immer nur ein einziges Element aus, z.B. wenn wir versehentlich immer wieder das Maximum als Pivot wählen aber eigentlich das Minimum suchen. Dann bräuchten wir Pivots und hätten eine Laufzeit von . Wir sind also auf gute Pivots angewiesen!
Ein guter Pivot hat die Eigenschaft, dass er einen linearen Anteil der Schlüssel auf beiden Seiten hat, also mindestens Schlüssel in beiden Teilen hat, für irgendein positives, konstantes . Wenn es uns gelingt so einen Pivot in linearer Zeit zu finden, dann können wir auch eine lineare Zeit für den ganzen Algorithmus zeigen:
wobei wir in der letzten Zeile den Grenzwert der geometrischen Reihe benutzten, also dass .
Es bleibt also lediglich die Frage: Wie finden wir einen solchen guten Pivot in linearer Zeit?
Für die erste Idee namens Quickselect, die von Tony Hoare aus dem Jahr 1961 stammt, nehmen wir uns den Zufall zu Hilfe. Wir wählen einen zufälligen Schlüssel als Pivot und zählen aus, ob er mindestens Elemente auf beiden Seiten hat. Wir wollen also einen Pivot aus den mittleren Elementen. Falls wir Glück haben und gerade so einen Pivot aus der sortierten Mitte gewählt haben, sind wir fertig, ansonsten versuchen wir unser Glück einfach nochmals erneut.
Was ist die Wahrscheinlichkeit dass wir einen guten Pivot wählen? Von Schlüsseln sind "gut", also liegt die Wahrscheinlichkeit .
Wieviele Wiederholungen brauchen wir im Mittel bis wir so einen guten Pivot finden? Sei dieser Erwartungswert. Es gilt , denn entweder wir sind nach einem Versuch fertig, oder wir beginnen nochmals von vorne. Daraus folgt . Im Schnitt müssen wir es also nur mit Pivots versuchen.
Somit ist die erwartete Laufzeit, um einen guten Pivot zu finden . Da wir in jedem Pivotierungsschritt mindestens einen Viertel der Elemente ausschliessen (in der Analyse oben also einsetzen können), läuft damit Quickselect in erwarteter Zeit .
Der einzige Wermutstropfen bei Quickselect ist die Einschränkung auf den Erwartungswert. Wir können also nicht garantieren, dass Quickselect in jedem Fall nur linear viele Schritte braucht. Wenn es dumm läuft und wir nie einen guten Pivot treffen, was extrem unwahrscheinlich aber möglich ist, dann terminiert Quickselect nicht einmal.
Das Ziel des letzten Algorithmus ist deshalb deterministisch einen guten Pivot finden, ohne dass die asymptotische Laufzeit darunter leidet.
In den 70er Jahren hatten die Forscher Blum, Floyd, Pratt, Rivest und Tarjan die entscheidende Idee dazu, die heute als "Median der Mediane nach Blum" bekannt ist.
Funktioniert diese komische Doppelrekursion wirklich? Finden wir so einen guten Pivot und bleibt die Laufzeit linear?
Wie gut ist dieser Pivot? Wie viele Elemente sind sicher kleiner als ?
Mindestens Elemente.
Genau gleich viele Elemente sind sicher grösser als . Also erfolgt der zweite rekursive Aufruf auf höchstens Elementen.
Als Rekursionsgleichung erhalten wir somit:
Was wir noch zeigen wollen: Diese Rekursionsgleichung hat eine lineare geschlossene Form, also .
Beweis durch Induktion
Nun wählen wir und fahren fort mit
Wir haben also mit den Basisfall gross genug gewählt, sodass hier im rekursiven Fall die additive im linearen Term Platz hat.
Warum Fünfergruppen? Mit Gruppengrösse drei oder vier kommt bei der Rekursion etwas nicht strikt kleineres heraus. Die beiden Teilprobleme zusammengenommen sind nicht mehr kleiner als , was keine lineare Laufzeit mehr ergibt. Alle Gruppengrössen ab fünf funktionieren aber genauso gut. Die Konstante muss aber auch entsprechend grösser gewählt werden, sodass die Basisfälle mit anwachsen.
Prof. Springman studierte und promovierte in Geotechnik an der Universität Cambridge Homepage. ↩︎
Quelle: CS 50 @ Harvard, Prof. David Malan ↩︎
Donald Knuth. The Art of Computer Programming, Volume 3, Section 6.2.1, Seite 419 ↩︎
Diese Blogpostserie gibt eine ausführliche Abhandlung über die gängigsten Fehler in Implementierungen der binären Suche [Link]. ↩︎
Den ersten Vergleich dieser binären Suche können wir uns noch einsparen, wenn wir statt mit mit starten. ↩︎
Tipp: Divide-and-Conquer mit Basisfall . ↩︎
Man kann auch zeigen, dass es nicht besser als in Vergleichen gehen kann. Dies ist die Aufgabe 16 in Abschnitt 5.3.3 in Knuths The Art of Computer Programming, Volume 3. Das wurde erstmals in diesem Paper von Ira Pohl gezeigt. ↩︎
Pivot: Französisch für "Angelpunkt" oder "Drehpunkt" ↩︎
Wir wenden es quasi als Blackbox an, ohne genau zu verstehen wie es funktioniert. ↩︎