Herzlich willkommen zu Algorithmen 2.
Wie immer starten wir wieder mit einer Wiederholung.
Mit den Sachen, die wir letzte Woche gemacht haben.
Ich werde nicht nochmal die komplizierten Details erklären, die lassen
wir einfach weg.
Die könnt ihr euch anschauen, wenn ihr Lust dazu habt.
Nachdem wir das gemacht haben, machen wir weiter mit randomisierten
Algorithmen.
Das heißt, das sind im Prinzip Algorithmen, die eine gewisse Art von
zufälligen Entscheidungen beinhalten, um dann zu einem Ergebnis zu
kommen.
Als letztes gucken wir uns heute externe Algorithmen an.
Das sind also Algorithmen, wo die Daten potenziell nicht mehr in den
Hauptspeicher passen, sondern nur noch auf einen großen
Sekundärspeicher, wie zum Beispiel eine Festplatte.
Dann hat man nicht mehr das Ziel, asymptotisch die
Berechnungskomplexität zu minimieren, sondern das Hauptziel ist dann,
die IOs erstmal zu minimieren, weil das ist der limitierende Faktor.
Aber das sehen wir später alles noch.
Machen wir also nochmal Wiederholung.
Was haben wir im Prinzip die letzten zwei Wochen gemacht?
In den letzten zwei Wochen haben wir uns Flussprobleme angeschaut und
Cut -Probleme.
Und insbesondere haben wir uns letzte Woche angeschaut, was passiert,
wenn Algorithmen nicht mehr Flüsse während ihrer Laufzeit haben,
sondern Priflüsse.
Und diese Präflüsse, die haben im Prinzip die Eigenschaft, dass mehr
Fluss in den Knoten reinfließen kann, als rausfließen kann.
Und dieser Fluss, der dann auf diesem Knoten ist, nennen wir Exzess.
Also ich schreibe das jetzt nochmal hin.
Ein Preflow ist ein Fluss ohne Flusserhaltung.
Und stattdessen haben wir gesagt, wir wollen den Exzess auf einem
Knoten, dass der Inflow von V minus der Outflow von V, der soll größer
als 0 sein.
Dann haben wir diese Flusserhaltungsbedingung ersetzt durch diese
Preflow -Bedingung, die nochmal sagt, in einem Knoten darf mehr Fluss
reinfließen, als rausfließen.
Dann haben wir gesagt, wenn der Exzess von einem Knoten echt größer
als 0 ist, dann definieren wir den Knoten als aktiv und haben gesagt,
S und T sind nie aktiv.
Wobei S und T hier die designierten Knoten sind, S die Quelle und T
die Senke.
Also aus S kommt Fluss raus, in T soll der Fluss rein.
Dann hatten wir definiert ein Residual-Netzwerk, im Prinzip wie
vorher.
Dann haben wir eine Funktion eingeführt, Procedure Push, E gleich VW.
Und was diese Funktion jetzt im Prinzip macht, ist nichts anderes als
Exzess von einem Knoten zu nehmen und den über eine Kante auf den
nächsten Knoten zu transferieren.
Und zwar genau die Höhe Delta.
Und das heißt, wir müssen den Exzess im Wesentlichen auf dem Knoten V
reduzieren um Delta, den Exzess auf dem Knoten W um Delta erhöhen.
Wenn E eine Rückwärtskante ist, dann müssen wir den entsprechenden
Fluss auf der Rückwärtskante um Delta reduzieren.
Sonst wird eben dieser Fluss um Delta erhöht.
Und dann hatten wir den sogenannten Preflow-Push-Algorithmus.
Wir hatten uns den Preflow-Push-Algorithmus generisch angeschaut und
er hat gesagt, wir starten erstmal, indem wir für alle ausgehenden
Kanten von S diese Push-Operationen durchführen.
Und zwar mit dem Delta auf die Kapazität gesetzt.
Das ist das Maximale, was wir aus diesem Knoten rauspushen können.
Wir haben initial gesagt, dann haben wir Label eingeführt.
Und diese Label sagen, D von S ist am Anfang N und gleich 0 für alle
anderen Knoten.
Und dann die Hauptfunktion von diesem Preflow-Push-Algorithmus ist der
Teil hier unten.
In dem wir gesagt haben, solange wir aktive Knoten haben, schieben wir
Fluss über ausgehende Illegible Edges.
Eine Kante war Illegible, wenn der Endpunkt niedriger vom Level ist
als der Startpunkt.
Das heißt, wir können Fluss immer nach unten schieben.
Wenn wir so eine Kante gefunden haben, dann schieben wir über diese
Kante den entsprechenden Fluss Delta.
Wobei Delta jetzt im Prinzip die beste Wahl ist, so wie wir sie hier
unten sehen.
Nämlich das Minimum aus dem Exzess, der tatsächlich auf dem Knoten V
ist und der Kapazität, die ich über die Kante noch rüberschieben kann.
Wenn ich keine auswählbare Kante habe, dann wird dieser Knoten hier
gelabelt.
Das heißt, ich schiebe den Level nach oben und das ist im Prinzip der
ganze Algorithmus.
Jetzt gab es hier zwei Notationen.
Einmal, was ist ein saturierender Push?
Ein saturierender Push ist der, der Delta im Prinzip gleich die
Kapazität der Kante hat, weil man dann eben die Kantenkapazität
saturiert.
Die wird dann ausgelastet und dementsprechend, wenn der Exzess hier
der limitierende Faktor ist, dann nennen wir diesen Push non
-saturierend.
Jetzt haben wir uns ein paar Lemma überlegt.
Das erste Lemma war, dieser Algorithmus, den wir gerade gesehen haben,
der erhält den Preflow.
Das heißt, während des ganzen Algorithmus ist F ein Preflow, generiert
keine Steep Edges.
Und Steep Edges waren hier Edges, wo die Level zwischen zwei Knoten im
Prinzip mehr als ein Level auseinanderhängen.
Und während des ganzen Algorithmus geht D von S gleich N und D von T
gleich 0.
Das war das erste Lemma.
Das zweite Lemma, was wir gesehen haben, wenn unser Generic Preflow
Push Algorithmus terminiert, dann ist F maximaler Fluss.
Und dass es ein Fluss ist, das ist im Prinzip sehr einfach zu sehen.
Einfach, weil die Nachbedingung, also wenn ich diese Bedingung, die
hier in dieser While-Schleife steht, negiere, dann steht da für alle
Knoten gilt der Exzess ist gleich 0.
Und das heißt, dass der Inflow von jedem Knoten gleich der Outflow ist
und damit weiß man, die Funktion F ist ein Fluss.
Und dass das Ding maximal ist, dafür mussten wir ein bisschen mehr
arbeiten.
Jetzt hatten wir noch ein Lemma, das hat gesagt, wenn V aktiv ist,
dann existiert ein Pfad von V zu S in GF.
Und die Interpretation von dem Lemma ist, wenn ich Fluss auf einem
Knoten habe, dann muss der da irgendwie hingekommen sein, also kann
ich ihn auch irgendwie wieder zurückschieben.
Dann haben wir das nächste Lemma.
Da haben wir gesagt, für alle V und V gilt, die Distanz von V ist
kleiner als 2n.
Also das Label von einem bestimmten Knoten wird nie größer als 2n.
Damit haben wir uns überlegt, dass die Anzahl Gesamt-Relabel-Operation
kleiner gleich 2n² ist.
Und dann haben wir uns weiter überlegt, auf diesem abstrakten Level
hier, dass die Anzahl Saturating-Pushes kleiner gleich n mal m ist.
Das ist im Prinzip das, was wir jetzt vor zwei Wochen gemacht haben.
Dann haben wir letzte Woche weiter gemacht und haben uns dann
angeschaut, was ist denn jetzt mit den unsaturierten Pushes.
Und da haben wir gesagt, die Anzahl non-saturating Pushes ist O von n²
mal m, unter der Bedingung, dass Delta eben genauso gewählt ist.
Minimum Excess von V CEF.
Und für beliebige Knoten- und Kantenausfallregeln.
Na gut, wie haben wir das gemacht?
Da gebe ich jetzt auch nochmal kurz die grobe Skizze, also die globale
Struktur von dem Ding.
Wir haben im Prinzip gesagt, füge mal eine Potentialfunktion ein,
wichtiges Konzept.
Und zwar hier über alle Knoten, die aktiv sind.
Dann haben wir uns Eigenschaften überlegt für diese Potentialfunktion.
Am Anfang ist das Ding immer größer gleich 0, am Anfang ist es gleich
0 und genauso ist es 0 am Ende.
Dann zweitens, ein non-saturating Push erniedrigt V mindestens um 1.
Drittens, ein Relabel erhöht V um 1, also hier halt genau 1.
Und viertens, ein saturierender Push erhöht V um höchstens 2n.
So und die Dinger hier kann man sich relativ leicht überlegen.
Machen wir jetzt nicht im Detail nochmal.
Was wir dann aber gesehen haben mit diesen Annahmen hier, können wir
zeigen, dass erstens V kleiner gleich 2n² plus n mal m mal 2n ist.
Und damit können wir eben die Anzahl an non-saturierenden Pushes
abschätzen.
Und das ist eben genau die Behauptung.
Ja, da kommt man genau auf dieses n² mal m hier.
Okay, so und dann hatten wir einen Satz, den ich jetzt auch im Detail
nicht mehr hinschreibe.
Der sagt, ein arbitrary Preflow-Push-Algorithmus läuft in O von n² mal
m.
So, das war erstmal das wichtige Ergebnis.
Ja, wir haben jetzt gezeigt, okay, das ist jetzt die Laufzeit von
unserem Algorithmus.
Und gleichzeitig haben wir, wie ich ja gerade eben schon erwähnt habe,
gezeigt, dass wenn das Ding terminiert und es tut es damit
offensichtlich, dann finden wir einen maximalen Fluss.
Dann hatten wir uns überlegt,
wie man die Laufzeit von dem Algorithmus verbessern kann.
Laufzeit verbessern und dann hatten wir im Wesentlichen zwei Optionen.
Erstens, wir speichern die aktiven Knoten in der FIFO.
Da kommen wir zu einem Algorithmus, der O von n³ hat.
Da haben wir uns im Detail nicht angeschaut, warum das so ist.
Wir haben uns stattdessen angeschaut, eine Heuristik, die sagt Highest
Level First.
Und das sagt im Wesentlichen, wir wollen immer den Knoten mit
maximalem Label auswählen.
Und das war eben der komplizierte Teil der letzten Vorlesung.
Jetzt kommen wir insgesamt auf einen Algorithmus, der O von n² mal
Wurzelm hat.
Jetzt war das schöne, also ein ganz wichtiges Ergebnis, dass wir zum
einen diese Laufzeitgarantien hier haben.
Das heißt, wir haben erstmal irgendwas, womit wir die Komplexität von
dem Algorithmus abschätzen können.
Dann haben wir uns tatsächlich aber noch Heuristiken angeschaut, mit
denen man die Laufzeit verbessern kann.
Man den Algorithmus aber nicht mehr gut analysieren kann.
Und diese Heuristiken haben dazu geführt, dass der Algorithmus in der
Praxis sehr nah an Linearzeit skaliert.
Was für Heuristiken haben wir uns im Prinzip angeschaut?
Also A, die erste Heuristik war Aggressive Relabeling.
Und dieses Relabeling sagt im Wesentlichen, ein Knoten kann ich ja
direkt das 1 plus das minimale Label meiner Nachbarschaft geben.
Weil sonst muss ich alle entsprechenden Relabels ja einzeln
durchführen.
B war ein Global Relabeling.
Alle O von Edge Inspections.
Und zwar haben wir dann gesagt, dieses D von V setzen wir auf GF
Reverse BFS von T.
Zittens, wir wissen, wenn ein Knoten ein Label hat, was größer gleich
N ist, was passiert dann?
Na gut, dann muss der Fluss, der auf dem Knoten ist, zum Startknoten
zurückgeroutet werden.
Aber das ist einfach.
Und dann haben wir gesagt, okay, dann machen wir einfach ein
Spezialverdraht aus.
Special Treatment.
Und die letzte Heuristik, die wir uns angeschaut haben, war die Gap
Heuristik.
Ich glaube, du hast die auch nochmal in der Übung erklärt, oder?
Machst du das erst morgen?
Okay, machen wir morgen nochmal in der Übung.
Was da im Wesentlichen passiert ist, wenn ich ein Level habe, das leer
ist, dann kann ich alle Knoten, die über diesem Level sind, direkt auf
Level N schieben und den Fluss im Prinzip returnen, weil ich weiß, ich
kann nur über Steep Edges keinen Flow senden.
Okay, das war es soweit zur Wiederholung.
Gibt es Fragen dazu?
Sehr gut.
Okay, also was wir uns jetzt anschauen, sind im Prinzip randomisierte
Algorithmen.
Und da erkläre ich jetzt auch im Detail,
was wir damit meinen.
Okay, hier bei diesen randomisierten Algorithmen ist es jetzt so, dass
wir zum einen das machen, was auf der Folie draufsteht und zum anderen
erkläre ich euch noch einen anderen Algorithmus, der nicht auf den
Folien draufsteht.
Aber erstmal, was meine ich überhaupt mit randomisierten Algorithmen?
Achso, genau, da sollte ich vielleicht auch noch ein Wort zu lassen.
Also es ist folgendermaßen und zwar, die nächsten drei Kapitel sind
randomisierte Algorithmen, externe Algorithmen und parallele
Algorithmen.
Und für all diese Dinge, die wir jetzt hier kurz anschneiden, gibt es
im Prinzip Spezialvorlesungen an unserem Institut, wo man sich noch
weiter vertiefen kann.
Okay, fragen wir mal kurz nach.
Wer hat im Prinzip schon mal mit einem randomisierten Algorithmus
gearbeitet?
Ja, hier ich auch.
Wer noch?
Wer nicht?
Ja, größtenteils also Enthaltungen.
Okay, wer kennt Quicksort?
Alle?
Okay, also haben alle schon mal mit randomisierten Algorithmen
gearbeitet, weil im Prinzip das Pivot, was man bei Quicksort wählt, um
diese beiden Mengen zu splitten, das ist ja eine zufällige
Entscheidung.
Und dann analysiert man den Algorithmus und kriegt dann damit die
Laufzeit im erwarteten Fall.
Die Hauptidee bei randomisierten Algorithmen ist im Prinzip, wir
wollen zufällige Entscheidungen verwenden, um entweder einen
Algorithmus zu beschleunigen oder einen Algorithmus zu vereinfachen.
Manchmal kann man eben durch zufällige Entscheidungen den Algorithmus
signifikant vereinfachen.
Also die Hauptidee, verwende Zufall zur Beschleunigung oder
Vereinfachung von Algorithmen.
Und was wir jetzt einfach annehmen ist, wir haben eine zusätzliche
Operation, die uns eine Zufallszahl gibt.
Und zwar nennen wir die jetzt mal randomInt von c.
Und die liefert uns einen Zufallswert zwischen 0 und c-1.
Jetzt nehmen wir an, unsere Maschine, auf der wir arbeiten, also zum
Beispiel die Maschine hier, die kann uns Zufall geben.
Und jetzt muss man dazu sagen, dass die Maschinen hier uns keinen
echten Zufall geben.
Also alles, was da rauskommt, ist in irgendeiner Art und Weise
deterministisch.
Aber im Prinzip Zahlen generieren können, die nachher so aussehen, als
wäre sie zufällig.
Also in diesen Laptops oder was auch immer hat man nachher
Zufallsgeneratoren, die man mit einem bestimmten Wert initialisieren
kann.
Und dann fragt man ihn jedes Mal, okay, also sagen wir mal, ich habe
diesen Zufallsgenerator, ich initialisiere den mit einer bestimmten
Zahl, was weiß ich, das Datum von heute.
Und jetzt frage ich ihn nach Zufallszahlen, dann kriege ich eine Menge
von Zahlen.
Und jetzt initialisiere ich nochmal mit dem Datum von heute, ich frage
ihn wieder nach Zufallszahlen, ich kriege genau die gleichen Zahlen.
Das heißt, es ist eigentlich nicht zufällig.
Aber für sich genommen sehen die Zahlen nachher zufällig aus und es
reicht dafür, nachher die Algorithmen umzusetzen, die diese
Zufallsentscheidungen brauchen.
Genau, also die Aussage ist, echter Zufall ist nicht durch
deterministische Rechner erzeugbar.
Ja, das geht einfach nicht.
Das heißt, wir haben Pseudo-Zufall.
Pseudo-Zufallsgeneratoren.
Okay, also die Message, wir haben keinen echten Zufall hier, sondern
nur so Pseudo-Zufall.
Nur so Obwudezeugs.
So nebenbei bemerkt, wenn man im Prinzip als Algorithm-Engineer
arbeitet, dann führt es dazu, dass man randomisierte Algorithmen im
Prinzip deterministisch laufen lassen kann.
Das hat den Vorteil, dass wenn man einen Fehler im Code hat und das
passiert halt für eine bestimmte Zufallsentscheidung, dann kann ich
das Ganze reproduzieren, indem ich den Zufallsgenerator einfach
entsprechend initialisiere und kann dann immer noch die Fehler finden.
Ja, wenn ich echten Zufall hätte, würde das auf einmal nicht mehr
gehen und dann wäre ich darauf angewiesen, dass der Fehler nochmal
auftritt.
Ja, und dann passiert der vielleicht gar nicht mehr.
So, jetzt haben wir eine Klassifizierung von Zufallsalgorithmen.
Und da gibt es im Wesentlichen zwei Stück.
Also einmal gibt es Monte-Carlo-Algorithmen.
Hat das schon mal jemand gehört?
Sehr gut, ich schreibe es trotzdem nochmal hin.
Oder will jemand sagen, was es bedeutet?
Okay, also ich schreibe es nochmal hin.
Wir haben im Prinzip eine deterministische Laufzeit, unabhängig von
den Zufallszahlen.
Aber das Ergebnis, was wir bekommen, ist mit einer bestimmten
Wahrscheinlichkeit p...
...inkorrekt.
So, prima, ja.
Also ich habe jetzt einen Algorithmus, der gibt mir vielleicht nicht
das richtige Ergebnis zurück.
Das heißt, ich brauche eigentlich ein Verfahren, was mir danach
verifiziert, okay, das Ergebnis ist korrekt.
Zum Beispiel, und das werden wir gleich noch sehen, wenn ich Zahlen
sortiere, möchte ich danach verifizieren, zum einen, die Zahlen sind
sortiert, das ist einfach, und zum anderen möchte ich verifizieren,
ist es tatsächlich eine Permutation der Eingabe.
Jetzt gibt es einen Trick bei den Monte-Carlo-Verfahren, das nennt
sich Boosting.
Und das heißt im Wesentlichen, dass wenn ich jetzt rausfinde, okay,
der Algorithmus hat mir ein falsches Ergebnis wiedergegeben, dann
führe ich ihn einfach nochmal aus und checke halt wieder, okay, ist
das Ergebnis korrekt.
Und dann kriege ich nachher eine Wahrscheinlichkeit von p hoch k in
der k-ten Iteration, dass das Ergebnis, dass alle Ergebnisse im
Prinzip, die ich vorher gesehen habe, inkorrekt waren.
Ja, und dann weiß ich, okay, für k gegen unendlich finde ich
irgendwann ein korrektes Ergebnis, weil die Wahrscheinlichkeit, dass
das Ergebnis inkorrekt ist, eben gegen 0 geht.
So, genau, noch eine Message hier, die Effizienz von diesen Monte
-Carlo -Algorithmen ist abhängig von der Effizienz des Checks, den wir
da durchführen.
Okay, zweiter Algorithmus, Las Vegas, bisschen mehr Gambling.
Las Vegas-Algorithmen haben im Prinzip immer ein korrektes Ergebnis.
Und bei denen ist es dann tatsächlich der Fall, dass die Laufzeit der
Zufallsvariable ist.
Beispiel, so genau, also wer kann mir jetzt im Prinzip ein Beispiel
nennen für Las Vegas-Algorithmen?
So, ja, was war die Antwort?
QuickSort, genau, die Antwort ist QuickSort, ist natürlich richtig.
QuickSort oder zum Beispiel Hashing.
Ja, okay, gucken wir uns zwei Beispiele an.
Also erstes Beispiel, zwei Beispiele.
Genau, was wir jetzt machen wollen ist im Prinzip Ergebnisüberprüfung
für Sortieren.
Beim Sortieren.
Dann als allererstes mal, okay, was muss man machen, wenn ich ein
Ergebnis habe?
Ich muss halt überprüfen, ist die Ausgabe tatsächlich sortiert?
Ja, und das ist trivial.
Also ich iteriere einmal über das Array und gucke halt, okay, sind die
Zahlen da aufsteigend sortiert?
Trivial, nichts zu tun, easy going.
Die schwierigere Frage ist, ist die Ausgabe, die ich da gerade
berechnet habe, oder die der Algorithmus da gerade berechnet hat, eine
Permutation der Eingabe?
Also, Permutations-Eigenschaft, Fragezeichen, ja und das ist jetzt ein
bisschen involvierter.
Okay, jetzt gucken wir uns im Prinzip an, wie man genau diese
Permutations -Eigenschaft überprüfen kann mit einem randomisierten
Algorithmus.
Dafür brauchen wir erstmal eine Variable field, die uns zu einem Key
von einem Element irgendein Element in einem Körper f zuweist, und
zwar ein eindeutiges Element.
Ja, die Funktion soll injektiv sein.
Weiter habe ich eine Funktion key, und die weist einem Element ein Key
zu.
Das heißt, wir machen das jetzt auf dem allgemeinen Level, wo wir
tatsächlich irgendwelche Elemente nehmen und die Keys von diesen
Elementen sortieren.
Das heißt, ich muss zu den Elementen am Ende mir ein Key zurückgeben
lassen.
So, und jetzt gibt es hier einen kleinen Satz, der sagt, diese
Elemente hier, e1 bis en, die sind eine Permutation von s' gleich e1'
bis en'.
Und zwar genau dann, wenn diese Funktion q von z, die ich jetzt
definiere, identisch der Null ist.
Und diese Funktion q von z definieren wir als Produkt von i gleich 1
bis n von z minus Field von key von e1 minus Produkt i gleich 1 bis n
z minus Field von key von ei'.
Jetzt müssen wir uns erstmal kurz überlegen, warum das gilt.
Und dann müssen wir uns überlegen, was passiert da eigentlich und wie
sehen da die Wahrscheinlichkeiten aus und so weiter.
Also Beweis.
Die Einrichtung.
Okay, also wenn wir eine Permutation haben, na gut, was steht dann
hier?
Diese Produkte hier sind nichts anderes als, also da stehen im Prinzip
genau die gleichen Produkte und ich kann sie nachher umordnen, sodass
die Produkte exakt identisch sind und damit ist klar, dass dann q von
z identisch Null ist.
Also ich schreibe das jetzt im Detail nicht mehr hin, dann gilt eben q
von z ist identisch der Nullfunktion.
So, Rückrichtung.
Also wir nehmen mal an, wir haben keine Permutation.
Na gut, was passiert dann?
Dann existieren im Prinzip m größer gleich 1 lineare Terme in beiden
Produkten, die nicht in den anderen existieren.
Und damit ist auch wieder offensichtlich klar, dass das nicht
identisch die Nullfunktion sein kann.
Ja, ich kann dann die anderen Elemente, die gleich sind, kann ich
rauskürzen und habe dann irgendwas, was nicht identisch die
Nullfunktion ist.
Okay, was machen wir jetzt damit?
Na gut, wir wissen, dass das, was hier steht, nichts anderes als ein
Polynom ist.
Und zwar insbesondere hat dieses Polynom höchstens Grad N.
Also q von z hat maximal Grad N.
So und jetzt wissen wir, wir haben zwei Fälle.
Entweder die Funktion ist identisch Null oder dadurch, dass sie
maximal Grad N hat, hat sie höchstens N Nullstellen.
Also das heißt, entweder q von z ist identisch Null oder hat höchstens
N Nullstellen.
So, das heißt, wir können jetzt im Prinzip für diese
Ergebnisverifikation ein Algorithmuschen schreiben.
Algorithmus, der zwei Eingaben s und s' hat.
Der macht dann folgendes.
Konstruiere die Funktion q.
Werte q von z aus, wobei z in f zufällig.
Okay, also ich kann jetzt zum Beispiel einen Intervall nehmen von 0
bis c und wähle dann halt irgendwie ein entsprechendes Element hier
aus.
Wenn dieses q von z gleich Null ist, dann ist dieses s hier
Permutation von s' und zwar mit Wahrscheinlichkeit 1 minus N durch
Betrag f.
Das ist genau das, was ich gesagt habe.
Wir haben höchstens N Nullstellen und damit habe ich eben entweder
eine Nullstelle gefunden oder das Ding ist identisch Null.
Die Wahrscheinlichkeit, dass es eben eine Nullstelle ist, ist da
dementsprechend gegeben.
Gleichzeitig ist es so, dass Polynome in Linearzeit ausgewählt werden
können.
Das heißt, wir haben hier im Prinzip einen Algorithmus, um das zu
testen, der in Linearzeit läuft.
Und jetzt nochmal eine Preisfrage.
Ist das Monte Carlo oder ist das ein Las Vegas Algorithmus?
Wer weiß das?
Ja, da vorne?
Ja, richtig.
Triviale Frage.
Also das ist offensichtlich Monte Carlo.
Monte Carlo Beispiel.
Okay, gibt es noch Fragen zu dem Beispiel?
Okay, dann gucken wir uns das nächste Beispiel an.
Was wir jetzt machen wollen ist im Prinzip, also wir haben ja schon
ein paar Graphenalgorithmen in der Vorlesung gehabt.
Und auch wieder jetzt, wenn man als Algorithm Engineer arbeitet und
Algorithmen für Graphen entwickeln möchte, braucht man häufig
Testinstanzen.
Und eine von diesen Testinstanzen, sprich Graphen, könnten zum
Beispiel zufällig erzeugte Graphen sein.
Das heißt, ich definiere mir irgendeine Graphklasse, wo ich weiß,
diese Graphklasse hat bestimmte Eigenschaften.
Und jetzt möchte ich aus dieser Graphklasse einen zufälligen Graphen
rausziehen.
Also ich will irgendwie... ich habe eine Graphklasse, die hat beliebig
viele Elemente und jetzt will ich einen zufälligen herausgreifen.
Und eine von diesen Graphklassen nennt sich Barabasi Albert.
Und deswegen schauen wir uns jetzt an.
Barabasi Albert Graph Generation.
Und jetzt muss ich nochmal vorwegnehmen, das wird im Prinzip gleich
nochmal ziemlich spannend.
Weil wir am Ende von dieser Seite hier einen Algorithmus haben, der im
Prinzip parallel arbeiten kann, ohne dass er kommuniziert.
Da gibt es noch einen kleinen Trick, wie man das macht.
Und dann kommt raus, wenn man tatsächlich Algorithmen bauen möchte,
die von Zufall abhängen und am besten nachher gar nicht kommunizieren
in so einem parallelen Rechner, dann kann man den Zufall eventuell auf
anderen Maschinen wieder berechnen.
Aber gucken wir uns erstmal an, was ich meine mit Barabasi Albert
Modell.
Also Modell.
Das Modell sagt, wir haben jetzt erstmal ein Seed Network.
Und dieses Seed Network hat im Prinzip N0 Knoten.
So was wir jetzt machen ist, wir fügen Stück für Stück Knoten hinzu.
Also add nodes v1l time.
Und zwar so, dass jeder Knoten, den ich da hinzufüge, zu d
existierenden Knoten verbunden wird.
So und dieses d ist jetzt im Prinzip ein Parameter, der dieses Modell
beschreibt.
Also d ist vorgegeben, ich weiß nachher, das N, das große, ist
vorgegeben.
Und das sind die beiden Modellparameter und mit denen baue ich im
Prinzip diesen Graphen auf.
Jetzt ist die Frage, jetzt muss ich mir wieder über
Wahrscheinlichkeiten Gedanken machen.
Und jetzt sage ich Endpoint Likelihood.
Endpoint Likelihood.
Pu ist d von u durch Summe w, d von w.
Also erstmal stellt man fest, ich habe einen Graphen gegeben, der im
Prinzip n-1 Knoten hat und ich will den enden Knoten hinzufügen.
Jeder dieser Knoten hat jetzt schon eine bestimmte Anzahl Links.
Das heißt, das ist genau dieses d von u hier.
Und hier unten steht im Prinzip die Summe über alle Knoten, die ich
vorher schon drin habe.
Und da die Anzahl Links, die diese Knoten haben.
Das heißt insbesondere, wenn ich jetzt hier diese Pu über alle u's
aufsummiere, die schon existieren, ist das erstmal eine
Wahrscheinlichkeitsverteilung, weil die Summe am Ende 1 ist.
Und was wir jetzt hier auch noch sehen ist, die Art und Weise, wie
diese Wahrscheinlichkeiten hier bestimmt sind, heißt, dass Knoten, die
schon sehr sehr viele eingehende Kanten haben oder die generell sehr
viele Kanten haben, die sind nachher wahrscheinlicher als neuer
Endpunkt für den neuen Knoten.
Und was heißt das im Prinzip?
Was modellieren wir damit?
Wenn ich in einem sozialen Netzwerk bin, wie zum Beispiel Twitter, und
einen Knoten habe, der sehr sehr viele Kanten hat, stellen wir uns
nochmal vor, Justin Bieber auf Twitter oder Barack Obama, dann ist es
sehr wahrscheinlich, dass ein neuer User genau diesem User nachher
folgen wird.
Weil der hat sowieso schon viele Follower und damit ist es
wahrscheinlicher, dass wir da im Prinzip reinkommen.
Das heißt, schreiben wir das nochmal hin.
Neue Knoten haben im Prinzip Präferenz, sich an Knoten anzuheften, die
schon stark verlinkt sind.
Und was heißt das jetzt im Umkehrschluss?
Na gut, wenn ich mir die Gradverteilung von diesem Netzwerk anschaue,
dann sieht die ungefähr so aus.
Wobei das jetzt hier, also hier steht erstmal D von U, das ist eine
logarithmische Skala hier unten.
Und hier ist im Prinzip die Anzahl links, D von U.
Achso, das ist die Anzahl Knoten, die entsprechend diesen Knotengrad
haben.
Und das Ding hier, was man hier sieht, nennt man Power-Logic
-Redistribution.
Das heißt, wenn ich mir ein soziales Netzwerk hernehme, wie eben
Twitter, Facebook oder was auch immer, dann stellt man fest, dass die
Verteilung der Knotengrade im Prinzip genau so aussieht.
In der Log-Log-Skala, also das ist hier auch eine logarithmische
Skala.
Und der Trick ist jetzt, dass dieses Modell, dieses Barabasi-Albert
-Modell, nachher Graphen generiert, die genau diese Degree
-Distribution hat.
Das heißt, wenn ich einen Algorithmus entwerfen will, der auf sozialen
Netzwerken gut funktioniert, dann kann ich mir diese Barabasi-Albert
-Graphen hernehmen und auf denen beliebig viele Instanzen generieren
und beliebig viel testen.
Da habe ich ein wichtiges Modell, mit dem man seine Algorithmen testen
kann.
Jetzt ist es so, der einfachste Algorithmus, der mir spontan einfällt,
ist zu sagen, in jeder Iteration berechne ich diese
Wahrscheinlichkeiten hier neu und ziehe dann eine Zufallsvariable
anhand dieser Wahrscheinlichkeiten und kriege damit erstmal einen
wunderbar langsamen Algorithmus.
Weil ich in jeder Iteration für jeden Knoten irgendwie alle Knoten
anschauen muss und dann irgendwie, das kriege ich dann quadratische
Laufzeit, offensichtlich.
Es geht besser.
Und zwar mit dem Algorithmus von Brandes und Battageli.
Und der macht jetzt folgendes.
Der sagt also, hier am Anfang ist die Kantenmenge erstmal leer.
Und jetzt sagen wir, für v gleich 0 bis n-1, do for i gleich 0 to d-1,
und du wähle
mal j als zufällige Zahl, also random, in 0 bis Betrag e-1.
Moment, e setzen wir auf v und u per Definition e von i.
Und sagen danach, u ist vereinigt diese Kantenmenge.
Jetzt muss ich dazu noch ein Wort verlieren.
Was dieses e im Prinzip macht, das ist nichts anderes als eine Reihe.
Und jetzt haben wir für jede Kante zwei Felder.
Nämlich einmal den Startpunkt und einmal den neuen Endpunkt.
In dem Fall vielleicht 0.
Und zwar das Ganze d-mal.
Das heißt, ich habe hier im Prinzip die ersten Positionen.
Weiß ich, okay, da steht sowieso 0.
Und dann setze ich da an dem zweiten Punkt immer die entsprechenden
Knoten auf die Zufallsentscheidung, die ich da habe.
Und wenn ich jetzt hier an der Stelle bin und diesen Knoten hier
füllen möchte, schreibe ich eben den Knoten v da rein.
Und für diesen Knoten brauche ich einfach nur einen zufälligen Wert in
diesem Array hier zu finden.
Jetzt ist die Frage, okay, warum funktioniert das?
Na gut, also ich weiß, dass jeder Knoten proportional oft zu seinem
Knotengrad in dem Array davor vorkommt.
Das heißt, hier kann ich zufällig und gleich verteilt wählen und finde
dann dementsprechend mit der richtigen Wahrscheinlichkeit den Knoten u
als Endpunkt.
Okay, klar soweit?
Ja, wer hat das verstanden?
Okay, wer hat es nicht verstanden?
Okay, gibt es Fragen dazu?
Ja,
genau, also die Frage war, am Anfang ist es eh leer.
Stimmt, dann ist der Algorithmus eventuell nicht ganz korrekt
hingeschrieben.
Am Anfang nimmt man halt die Null.
Also wenn ich am Anfang noch keine Kanten habe, setze ich halt das
Ding auf Null.
Ja, und dann hat man eben Self-Loops.
Also Self-Loops sind hier nicht ausgeschlossen.
Okay, weitere Verständnisfragen zu dem Algorithmus?
Okay, so und jetzt kommt, also das ist erstmal schon cool, weil das
ist offensichtlich linear in der Anzahl Kanten, die ich generiere,
plus minus die Laufzeit, die ich da eben habe, die ich für die
Zufallsentscheidung brauche.
Aber ich brauche eben keine Zufallsverteilung mehr, die von
irgendwelchen Wahrscheinlichkeiten abhängt oder eine komplizierte
Zufallsverteilung, sondern ich habe bloß noch Uniform und
Gleichverteilt.
Und das ist genau die Operation, die wir am Anfang hingeschrieben
haben.
So.
Und jetzt machen wir folgendes.
Wir benutzen Hashing.
Und machen jetzt nämlich was anderes.
Also wir sagen, okay, wir nehmen jetzt eine Funktion oder schreiben
jetzt eine Funktion hin, die heißt generateEdge von i.
Sagen r ist 2i plus 1.
Und dann wiederholen wir, repeat,
r ist h von r until r even.
Ja, und dann gibt die Funktion nichts anderes zurück als i durch d.
Und r durch 2d.
So.
Und jetzt muss ich im Prinzip nochmal ein bisschen genauer erklären,
was hier eigentlich passiert.
Wir gehen jetzt davon aus, dass diese Hash-Funktion im Prinzip eine
Zahl r auf eine Zahl 0 bis r-1 bildet.
Also hHash-Funktion, die r auf
Zahl 0 bis r-1 abbildet.
Und abbildet.
Und der Trick ist jetzt, dass eine gute Hash-Funktion Pseudo-Zufall
erzeugt.
Also ich kann diese Hash-Funktion verwenden, um im Prinzip Pseudo
-Zufall deterministisch zu erzeugen.
Was macht der Algorithmus?
Der macht jetzt folgendes.
Wir wollen diese Zahl u hier generieren.
Jetzt generiert er eine zufällige Zahl in diesem Array mit dieser Hash
-Funktion.
Das mag meinetwegen hier sein.
Wenn diese Zahl ungerade ist, dann macht er nichts anderes als im
Prinzip die Wahl, die ich an dieser Stelle getroffen habe, nochmal neu
zu berechnen.
Also wenn ungerade,
neu berechnen.
Wenn das Ding allerdings gerade ist, also zum Beispiel hier, dann weiß
ich, welche Zahl da steht.
Dann kann ich die Zahl berechnen.
Das ist nämlich genau dieses r durch 2d.
Und das heißt jetzt aber, ich leiste irgendwie mehr Arbeit,
habe ich die Array-Zugriffe, die ich vorher hatte, habe ich durch
Neuberechnung mit Hashing ersetzt.
Was heißt das jetzt für uns?
Als allererstes mal überlegen wir uns, wie oft muss ich hier neu
berechnen?
Na gut, die Wahrscheinlichkeit, dass ich eben immer immer ungerade
Positionen treffe, und zwar bis und endlich i gleich 0.
Das ist im Prinzip genau gleich 2.
Und damit heißt das, dass ich im Erwartungswert höchstens zweimal
diese Zahl neu berechne.
Das heißt, ich habe irgendwie einen Faktor 2 mehr Arbeit, statt diesen
Array -Zugriff.
Was aber der springende Punkt ist und warum man das macht, ist jetzt
folgender.
Ich kann das jetzt nämlich einfach parallelisieren.
Und vielleicht versteht man das erst, wenn man tatsächlich diese
parallele Section gehört hat.
Aber was wir jetzt ein bisschen händewedelnd machen wollen ist, wir
nehmen dieses Array, teilen es mal in zwei Teile, und dann sagen wir,
Prozessor 1 soll den ersten Teil ausrechnen und Prozessor 2 soll den
zweiten Teil ausrechnen.
Normalerweise, wenn ich hier hergehe und Prozessor 2 berechnet jetzt
diesen Knoten und die Zufallszahl ist irgendwo hier vorne, müsste ich
kommunizieren.
Prozessoren müssen die Information von dem lokalen Array
kommunizieren, damit der Prozessor hier weiß, was steht da eigentlich.
Und jetzt kann ich die Kommunikation aber komplett weglassen, weil ich
es einfach mit der Hash-Funktion neu berechne.
Das heißt, ich brauche gar nicht mehr kommunizieren.
Und dann ist es tatsächlich so, dass man ziemlich große Graphen, also
sagen wir mal so ein Petta-Edge-Graph, mit, das heißt also 10 auf 15
Kanten, in weniger als einer Stunde auf 16.000 Cores berechnen kann.
Also das Ding hier ist irgendwie das größte Ding, was man in der
Literatur so findet.
Und jetzt ist die Frage, und wie gesagt, das versteht man
wahrscheinlich erst, wenn man irgendwie den parallelen Teil gehört
hat, warum geht das?
Na gut, wir haben jetzt hier im Prinzip alles weggelassen, was
Kommunikation heißt.
Das heißt, wenn ich die Anzahl Prozessoren verdoppel, dann halbiert
sich die Laufzeit.
Jetzt mache ich das wieder und dann halbiert sich die Laufzeit wieder.
Ich habe nämlich keine Kommunikation da drin.
Und das heißt, man nennt das in den Parallelverarbeitungen nachher
Skalierbarkeit und das heißt, das Ding skaliert einfach perfekt.
Ja, und dann kann ich eben beliebig viele Prozessoren da drauf tun und
dann eben so Graphen berechnen oder halt, keine Ahnung, nochmal 10 mal
mehr Prozessoren und dann nochmal größere Graphen berechnen.
Okay, gibt es Fragen zu dem Ding?
Ja.
Das kleine E ist eine Kante, genau.
Also die, ja.
Genau, das große E, das steht hier nicht so genau, aber es ist im
Prinzip genau dieses Array von Anfang und Endknoten.
Genau, also U, also Moment, die Frage war, wenn ich dieses E von J
hier anschaue, dann ist es genau der Knoten an der Stelle J in dem
Array E.
Nee, Moment, also die Kanten sind wirklich so gespeichert, dass das
hier ein Array ist, wo Anfangspunkt, Endpunkt der Kante steht.
Ja, ich habe immer zwei Felder, Anfangspunkt, Endpunkt, Anfangspunkt,
Endpunkt.
Das, was an der Stelle gerade steht.
Also da muss man genau hingucken.
Ja, die Frage ist nochmal, wenn hier jetzt dieses J steht, welche
Kante nimmt man?
Ja, da habe ich die Frage richtig verstanden.
Ja, genau, und die Sache ist, dieses E von J gibt dir im Prinzip keine
Kante zurück, sondern einen Knoten.
So, und jeder Endknoten von dieser Kante steht hier drin in dieser
Liste von diesem Array.
Genau, also du schmeißt beide Endknoten rein.
Start und Ende.
Okay, also sonst können wir auch nach der Vorlesung nochmal
diskutieren.
Ja, da ist auch noch eine Frage?
Nee, weil E ist ja im Prinzip das ganze Array.
Also die Frage war, müssen wir J nicht aus 0 bis 2E-1 ziehen?
Okay.
Okay, sonst noch Fragen?
Genau, also im Prinzip, man hat hier nochmal zusammenfassend, man hat
hier ein Modell und kommt hier zu einem erstaunlich einfachen
Algorithmus, der sich dann mit ein paar Tricks, die wir im Prinzip zur
Zeit auch für andere Graphen wiederverwenden.
Also wir fangen jetzt an, tatsächlich andere Graphenmodelle mit genau
dem gleichen Trick hier immer wieder zu parallelisieren und kriegen
damit superskalierbare Algorithmen.
Communication efficient.
Und sieht dann, okay, das ist irgendwie einfach und dann wird es ein
bisschen komplizierter, aber ist immer noch einfach für eine
skalierbare Parallelisierung.
Ja, und das ist extrem nützlich in der Praxis.
Weil im Prinzip gibt es da draußen keine guten skalierbaren
Algorithmen, aber wenn man Algorithmen für Großrechner entwerfen
möchte, also skalierbare Algorithmen zur Generierung von Graphen, aber
wenn man Algorithmen für Großrechner entwerfen möchte, muss man die
tatsächlich am Ende generieren.
Wenn ich einen Algorithmus habe, einen Graphen habe, der 10 auf 15
Kanten hat, dann ist klar, dass ich den Graphen nicht einlesen möchte,
wenn ich da mit 100.000 Prozessoren rumrechne, weil ich dann einfach
ewig warte und extrem viel Rechenzeit verbrate.
Das heißt, ich muss Algorithmen haben, mit denen ich die Algorithmen,
die parallel sind, tatsächlich testen kann.
Und das macht genau dieses Ding da.
Okay,
also der nächste Punkt auf der Tagesordnung sind externe Algorithmen.
Okay, also externe Algorithmen.
Dafür muss ich erstmal das Modell einführen, was wir uns jetzt
anschauen.
Ich hatte ja vorhin schon am Anfang der Vorlesung gesagt, dass wir im
Prinzip ein Modell haben oder dass wir im Prinzip Algorithmen
entwerfen wollen für Instanzen, die nicht mehr in den Hauptspeicher
passen, sondern die nur noch auf den Sekundärspeicher passen, wie zum
Beispiel eine Festplatte.
Und die Festplatte, wenn ich jetzt anfange, Daten von der Festplatte
zu lesen, wenn ich jetzt mal weg von der SSD bin, habe ich irgendwie
einen Festplattenkopf, der zu einer bestimmten Spur hingehen muss und
dann dort Daten lesen kann von der Spur.
Das heißt, es kostet Zeit, dort hinzugehen und es ist viel, viel
langsamer als der Zugriff im internen Speicher.
Das heißt, das Modell, was wir jetzt haben, wir haben irgendwie
Register, wir haben eine arithmetisch-logische Einheit, diese ALU
hier, die im Prinzip Berechnungen durchführen kann.
Wir haben unseren internen Speicher M und wir haben eben unseren Large
Memory, zum Beispiel eben unsere Festplatte, die mit einem Bus an
diesen internen Speicher hier verbunden sind und dieser Bus kann immer
B -Wörter gleichzeitig lesen.
Genau, und dann steht hier so ganz nebenbei auf dieser Folie Block
Zugriffe zählen, Analyse.
Und ich kann mich genau daran erinnern, dass als ich damals irgendwie
externe Algorithmen das erste Mal gehört habe, ich mich immer
gewundert habe, was passiert hier eigentlich.
Und das ist genau der springende Punkt.
Anstelle jetzt von Arbeit, ja genau, anstelle jetzt sich zu überlegen,
wie ist die interne Arbeit von dem Algorithmus, wollen wir in den
Analysen immer die IOs minimieren.
Das heißt, wir wollen Algorithmen haben, die möglichst wenig von der
Platte lesen, oder nicht möglichst wenig, sondern möglichst effizient
von der Platte lesen, weil das ist dann nachher der limitierende
Faktor.
Und dann haben wir zwei Möglichkeiten für die Analyse.
Einmal werden wir Algorithmen sehen, wo wir die interne Arbeit
analysieren von dem Algorithmus.
Und auf der anderen Seite, das werden wir häufiger machen, wollen wir
uns anschauen, wie funktioniert, wie viele IOs hat der Algorithmus.
Also wie gesagt, hier ist das Modell, was wir haben.
Und dann wissen wir schon, unstrukturierter Zugriff ist teuer.
Eine Operation pro Element...
Eine IO-Operation pro Element...
So, was meine ich damit?
Stellen wir uns mal ganz einfach vor, ich habe einen großen Vektor,
der steht in der Datei, und jetzt habe ich unstrukturierten Zugriff,
das heißt, in irgendeiner Reihenfolge, ziemlich unstrukturiert, will
ich auf die Elemente in diesem Array zugreifen, was in meiner Datei
steht.
Was passiert dann?
Na gut, dann muss der Kopf von der Festplatte jedes Mal zu irgendeiner
bestimmten Spur laufen, dort dieses Element suchen, und dann habe ich
im Prinzip genau diese IO-Operation für dieses einzelne Element.
Da gibt es eine Frage.
Die Frage war, wird bei sowas Lokalität berücksichtigt?
Das ist der nächste Punkt, den ich gleich anbringe.
Aber soweit erstmal klar.
Wenn wir einen unstrukturierten Zugriff haben, also irgendein Element
haben, dann heißt das, wir brauchen erstmal eine IO-Operation.
Wenn das andere Element, weiß nicht wie weit weg ist von dem aktuellen
Element, brauche ich wieder eine IO-Operation.
Also unstrukturierte Zugriffe sind teuer.
Was wir also im Prinzip wollen, ist 1 durch B IOs für einen
effizienten Algorithmus.
Um nochmal zurück auf die Frage zu kommen, wird bei sowas Lokalität
berücksichtigt?
Der Haupttrick bei diesen externen Speicheralgorithmen, ist nachher
die Elemente so anzuordnen, dass die Lokalität im Prinzip
berücksichtigt wird.
Also dass ich im Prinzip Elemente lese, oder gleichzeitig lesen kann,
und zwar in dem Sinne, dass ich immer gleich B-Wörter lese, anstelle
von einem einzelnen, und in diesen B-Wörtern sind halt schon ein paar
Elemente von denen drin, die ich sowieso lesen möchte.
Und dann habe ich nur eine IO-Operation, für das Lesen von den ganzen
Elementen.
Also nochmal, die Frage war nochmal, wenn ich jetzt Zugriff im
Speicher habe, und dann B-Elemente habe, und dann noch einen weiteren
Zugriff, der halt irgendwie B-Elemente weiter ist, dann ist der
Zugriff ja weniger weit entfernt.
Wird hier nicht berücksichtigt.
Da ist auch nochmal eine Frage?
Okay.
Alles klar.
Also ich wiederhole es nochmal.
Das Teurere ist tatsächlich, nachher die präzise Position zu finden,
und nicht, wie weit es weg nachher ist.
Und dann ist damit ja die Frage auch beantwortet.
Weiß ich selber auch nicht sowas.
Aber gut.
Jetzt überlegen wir uns erstmal, wie teuer ist eine Scan-Operation?
Also mit Scan meine ich jetzt, ich will einfach einmal durch diese
Datei durchsweepen, und alle Elemente lesen.
Also gucken wir uns an.
Scan-Operation.
Na gut, wie kann ich das Teil hier implementieren?
Also im Wesentlichen...
Genau.
Also was wir jetzt machen ist, bei dieser Scan-Operation laden wir
nicht nur ein einzelnes Element, sondern laden im Prinzip direkt die
nächsten B-Elemente, und haben dann für B-Elemente genau ein IO.
Also sagen wir, wir laden immer ein Block der Größe b in einem
Schritt.
Und...
and process internally.
Das heißt, wir laden jetzt immer B-Elemente in den Speicher m hier,
machen damit irgendwas, und dann laden wir die nächsten B-Elemente
usw.
Und das heißt im Prinzip, die Scan-Operation von n hat Theta mal n
over b IOs.
Ja, das ist offensichtlich.
Ja, also weil ich einfach diese n Elemente in der entsprechenden Art
und Weise, wie ich es hier gerade geschrieben habe, abarbeite.
So, jetzt gucken wir uns mal ein einfaches Beispiel an.
Einfaches Beispiel.
Also wir nehmen jetzt ein Algorithmus mit Integern von 1 bis N.
Und zwar drei Arrays a, b, c.
Und sagen for i gleich 1 bis n do a von i gleich b von c von i.
So, und jetzt sieht man schon, dieses c von i, da können beliebige
Zahlen drinstehen.
Das heißt, im schlimmsten Fall springe ich komplett in der Datei von
b, in der Gegend drumherum, kriege halt jedes Mal für jedes Element,
was ich da lesen möchte, ein I.O.
Das heißt, im Worst-Case
habe ich irgendwie sowas wie Omega von n IOs.
Ja, klar?
Irgendwem nicht klar?
Okay, und das will man im Prinzip vermeiden.
Das wäre super langsam für diesen Algorithmus.
Und jetzt kommt im Prinzip diese Standard-Technik, die man macht.
Man benutzt im Prinzip eine Sortier-Operation, um die Elemente so
anzuordnen, dass ich sie I.O.
effizient lesen kann.
Also gucken wir uns erstmal, wir nennen das Ding jetzt Sort & Scan.
Was wir jetzt für den Algorithmus machen ist, wir scannen erstmal c.
Das heißt, wir schreiben dann Tupel auf unsere Festplatte.
c von 1 gleich 17 und da hinten den Index dran.
c von 2 gleich 5 2 c von 3 gleich Okay, und so weiter.
Danach sortieren wir das Ding nach der ersten Komponente.
Das heißt, ich kriege dann sowas wie c von 73 gleich 1 73 c von 12
gleich 2 und 12.
Ja, also hier stehen immer die Indizes gepaart.
Und jetzt haben wir nach der ersten Komponente hier sortiert.
Das Ding mal da drunter.
Hervorragend.
So, das sind dann die Elemente, die man hat.
Jetzt macht man einen parallelen Scan auf b und c.
Das heißt, ich scanne jetzt beide Dateien parallel und kriege dann
raus b von 1 73 b von 2 12 und so weiter.
Und dann sortiere ich nach der zweiten Komponente sort second was ja
wieder diese Indizes sind, die ursprünglichen.
Dann hier raus b von c von 1 0,1 b von c von 2 0,2 und habe dann die
Ergebnisse überrechnet.
Jetzt machen wir noch einen kleinen Hint, warum das funktioniert.
Na gut, was hier steht ist ja nichts anderes als c von 73.
Und hier steht nichts anderes als c von 12.
Und damit ist klar, dass ich am Ende dieses Ergebnis dann berechnet
habe.
Jetzt habe ich hier im Prinzip einmal sortiert, das heißt ich kriege
Komplexität für sortieren und ein paar mal gescannt, das heißt ich
kriege Scanning Complexity.
Jetzt muss ich natürlich noch Sorting Complexity hinschreiben.
Das sehen wir später in der Vorlesung.
Sort von n hat Theta von n über b mal Logarithmus von m über b von n
durch b.
IOs.
Und das ist das, was wir später sehen.
Und das ist viel besser als linear viele IOs.
Das ist offensichtlich hier der limitierende Faktor.
Und was wir im Prinzip gemacht haben, ist wir haben sortiert und
dadurch die Daten so angeordnet, dass wir sie nachher besser
verarbeiten können mit weniger IOs.
Und das ist eine Technik, die macht man immer wieder bei externen
Algorithmen.
Also alles, was man da so hat, macht man durch Sortieren und Scannen.
Das ist im Prinzip die Basis.
So, jetzt gucken wir uns bevor wir uns tatsächlich sortieren
anschauen, schauen wir uns an, wie funktionieren externe Stapel
sozusagen als
einfacher Einstieg noch dazu.
Also externe Stapel.
Reminder.
Was meine ich mit Stapel?
Na gut, entweder meine ich ein Stack oder eine Queue.
Und diese beiden, also das ist jetzt nichts Neues.
Stack und Queue sind zwei Datenstrukturen, auf die ich Elemente
reingeben kann und wieder rausholen kann und das eben in einer
bestimmten Reihenfolge.
Genau, also Unterschiede.
Stack ist LIFO und Queue ist FIFO.
Okay, also Stack sagt Last Infos Out, also das, was ich zuletzt
reingepackt habe, hole ich auch wieder raus.
Die FIFO sagt das, was ich zuerst reingetan habe, kommt auch zuerst
wieder raus.
Und dann ist es tatsächlich so, dass für wenn diese Elemente, also
wenn die Anzahl der Elemente, die in diesen Strukturen drinstehen,
wenn die in den Speicher passt, dann ist klar, wie man das effizient
implementiert.
Man hat eben ein Array der Größe n mit ein paar Pointern und dann gibt
es da nicht viel zu tun.
Die Frage ist jetzt, was macht man im externen Speicher?
Dann gucken wir uns mal die Folie an.
Okay, also im externen Speicher haben wir erstmal das blaue Ding hier,
was im Prinzip die externe Datei ist.
Und dann habe ich zwei Puffer, eins und zwei, zwei interne Puffer, die
in den Speicher passen.
So, und dann müssen wir uns angucken, wie funktionieren diese Push und
Pop Operationen.
Na gut, Push sagt jetzt, wenn Platz in diesem Puffer hier ist, dann
Moment...
dann schreibt im Prinzip die Daten, die ich da habe, in meinen Puffer
rein.
Wenn kein Platz ist, dann flasche ich im Prinzip den einen Puffer auf
diese Platte raus und kann damit effizient alle Elemente von diesem
Puffer auf einmal rausschreiben.
Also ich habe nur ein IO für diese B-Elemente in dem Puffer
amortisiert.
Pop funktioniert ebenso, wenn ich im Prinzip Elemente in meinem Puffer
habe, dann lese ich die, ansonsten muss ich sie halt B-Elemente in den
Puffer rein.
Jetzt kann man sich überlegen, was passiert hier eigentlich?
Na gut, auf makroskopischer Ebene implementieren wir den Stack mit B
-Elementen für die Festplatte und auf mikroskopischer Ebene machen wir
das, was wir vorher gemacht haben mit den Puffern.
Damit kriegen wir einen effizienten Algorithmus oder eine effiziente
Datenstruktur, die eben O von 1 durch B-IOS pro Operation hat.
Okay, Fragen zu diesen externen Stapeln?
Okay.
Genau, dann fangen wir mal an mit mit externem Sortieren.
Hier nochmal das Modell, okay, das erkläre ich jetzt nicht nochmal.
Was wir als erstes mal uns überlegen, okay, worauf ich jetzt hinaus
möchte, ist auf eine Variante von Merge Sort.
Was wir jetzt für eine Merge Sort brauchen, ist eine Funktion, die
zwei Dateien oder zwei externe Arrays IO-effizient mergt.
Das funktioniert folgendermaßen.
Wir haben jetzt hier erstmal die Sachen, die komplett in diesem großen
Speicher liegen.
Dann haben wir im Prinzip drei Puffer.
Einmal einen Puffer für diese Datei A, dann einen Puffer für die Datei
B und einen Puffer für die Datei C.
Und was wir jetzt machen wollen mit dieser Merge-Funktion, also wir
wissen, beide Arrays sind sortiert und am Ende soll C alle Elemente
von A und B enthalten, und zwar in sortierter Reihenfolge.
Das heißt, ich muss immer das größere Element Moment...
Also je nachdem, welche Variante wir uns jetzt anschauen, muss ich
hier immer das größere Element dann tatsächlich in C reinschreiben.
Wie funktioniert das?
Am Anfang sagen wir, wir lesen ein Element aus dem Array x also aus A,
denn es ist x, lesen ein Element y aus B und dann iterieren wir so
lange, wie viele Elemente wir hier haben und sagen, wenn x das
kleinere Element ist, dann schreiben wir x raus und lesen eins aus A
oder andersrum, wenn y das kleinere Element ist, dann schreiben wir y
in C und lesen eben aus B das neue Element.
So, und wenn ich jetzt eben genau diese drei Puffer hier habe, also
ein Puffer hier, ein Puffer da, ein Puffer da, kann ich auch wieder
die Writes und die Reads, die ich da habe, alle auf einmal machen.
Also ich kann immer B-Elemente auf einmal speichern und kriege damit
folgende Analyse dann hin.
Also hier IO-Analyse.
Das Lesen von Datei A ist eben Betrag A durch B IOs plus 1.
B hat eben Betrag A durch B IOs ebenfalls plus 1.
Schreiben Gesamtanzahl Elemente durch B IOs und insgesamt kriegen wir
ach so, genau, insgesamt kriegen wir eben diese zweimal Gesamtzahl
Elemente durch B IOs.
Und wir müssen sicherstellen, okay, die Puffer, die ich hier habe,
sollen tatsächlich auch in den Speicher passen.
Okay, Fragen zum externen mischen?
Okay, genau.
Also was wir jetzt als nächstes machen wollen, ist im Prinzip die
ist im Prinzip Merge Sort.
Also wir haben jetzt die Datei F und was wir machen möchten ist, wir
wollen diese Datei in Stücke zerteilen, die erstmal in den
Hauptspeicher passen.
Also wir wollen die Eingabe in Eingabeportionen in Größe m teilen.
Dann nehmen wir dieses Stück, sortieren das und schreiben es wieder
auf die Platte.
Das heißt, wir nehmen dieses erste Stück hier, sortieren, schreiben es
wieder auf die Platte.
Wir nehmen das m-Stück hier, sortieren, schreiben es wieder auf die
Platte.
Das heißt, dieses Sortieren hier, oder dieses Stück, was wir hier
sortieren wollen, nennen wir nachher Run.
Das heißt, als Schritt danach, oder was ist die Nachbedingung?
Na gut, jedes dieser einzelnen Stückchen hier ist sortiert.
Und das heißt im Umkehrschluss, dass wir im Prinzip jetzt hergehen
können und unsere Merge-Operationen nehmen können und diese einzelnen
Runs miteinander mergen können.
Und gleichzeitig kann man sich jetzt überlegen, okay, wie viele IOs
kriegt man hier?
Na gut, ich scanne ja nur hier drüber, sortiere intern und schreibe
danach wieder.
Das heißt, ich kriege 2n durch b IOs.
Okay, wie funktioniert das?
Wie funktioniert das Sortieren durch externes Mischen?
Na gut, ich habe jetzt hier diese ganzen Runs.
Ich mache diese Run-Formation, die kostet mich 2n durch b IOs.
Und dann machen wir nichts anderes als zu sagen, okay, solange mehr
als ein Run
existiert, mergen wir eben Paare von Runs und geben eben den Remaining
Run aus.
Und am Ende, klar, wir machen immer aus 2 Runs einen und dann am Ende
existiert eben bloß noch ein Run.
Und dann können wir uns noch überlegen, wie teuer das ist.
Na gut, dass diese Schleife hier, die wird im Prinzip Log n durch M
aufgeführt, weil das ist eben genau die Anzahl von Runs, die wir am
Anfang haben und damit kriege ich dann eben eine logarithmische
Rekursionstiefe.
Jedes Merge kostet mich 2n durch b, das heißt hier kriege ich
insgesamt 2 mal n durch b mal 1 plus Logarithmus von n durch m IOs.
Okay, gibt es Fragen dazu?
Okay, dann war es das im Prinzip für heute und dann machen wir morgen
weiter mit noch besseren Sortieralgorithmen und
externen Prioritätssisten.
Genau.
Okay, dann bis morgen.