Guten Morgen.
Mir fällt heute erst auf, dass wir hier zwei verschiedene Funkuhren
haben mit verschiedenen Zeiten.
Das ist etwas verstörend, aber ich glaube, die da stimmt.
Lassen Sie mich beginnen mit einer kurzen Rekapitulation der letzten
Vorlesung.
Da hatten wir uns mit fortgeschrittenen Hashtabellen beschäftigt, die
insbesondere gemeinsam haben, dass die Suchoperation in Worst-Case
konstanter Zeit läuft.
Das ist ja ein Unterschied zu dem, was wir in Algorithmen 1
kennengelernt haben.
Da hatten wir erwartet lineare Zeit für die Suchoperationen, aber es
konnte halt passieren, dass viele Elemente kollidieren und man dann
für einige Elemente auch mal länger suchen muss.
Das ist zum Beispiel in Echtzeitsystemen nicht so schön und kann auch
bei parallelen Algorithmen ein Problem sein.
Wir hatten uns dann Cuckoo-Hashing angeschaut, ein besonders elegantes
Verfahren, bei dem man eigentlich eine normale Hashtabelle hat und
zwei Hashfunktionen und einfach die Invariante aufrechterhält.
Jedes Element ist entweder an der Stelle abgespeichert, wo die eine
Hashfunktion bestimmt oder an der die andere Hashfunktion bestimmt.
Und der Trick war dann halt, dass eine Einfügeoperation etwas
komplexer ist.
Die muss dann Elemente durch die Gegend schieben, um diese Invariante
aufrechtzuerhalten.
Wir haben dann Varianten nicht kennengelernt, aber ich habe sie
erwähnt, die das Ganze dann auch noch platzeffizient machen, wo man
dann 90, 99 Prozent des Platzes der Tabelle ausnutzen kann, wenn man
eine oder beide von zwei Tricks verwendet.
Das eine ist, dass man sagt, die Hashfunktionen adressieren nicht
einzelne Elemente der Tabelle, sondern Blöcke, sodass man daneben
mehrere Elemente in einem Block unterbringen kann.
Das hat zwei Vorteile.
Erstens kann man halt einige Kollisionen direkt tolerieren und
zweitens kann man beim Einfügen sich dann aussuchen, welches Element
man rausschmeißt.
Man kann sich vorstellen, dass das einen dramatischen Effekt hat, weil
dann habe ich, wenn ich mehrere Sachen rausschmeiße, sondern sich
schnell verzweigenden Baum von Möglichkeiten.
Und das führt deshalb auch dazu, dass man selbst, wenn man kleine
Blöcke hat, bereits dramatisch sich verbessernde Platzeffizienz hat.
Und einen ähnlichen Effekt erreicht man dadurch, dass man mehr als
zwei Hashfunktionen hat.
Bei zwei Hashfunktionen habe ich immer nur eine Alternative.
Bei mehr habe ich auch wieder so einen verzweigenden Baum von
Alternativen.
Man kann das Ganze auch kombinieren.
Vielleicht schaffen wir es, dass in der Übung der Tobias Meier mal
seine Variante vorstellt, die das nicht nur kombiniert, sondern auch
mit einem zusätzlichen Trick dafür sorgt, dass man sehr feinkörnig
dynamisch die Tabelle wachsen lassen kann.
Dann hatten wir uns Zufallsgrafen angeguckt, die eigentlich eine
ziemlich esoterische mathematische Geschichte sind.
Vor allem, wenn man deren Eigenschaften analysiert, die aber
tatsächlich genau das beschreiben, was für Cuckoo-Helgen gebraucht
wird.
Und diese mathematischen Techniken, die man da verwendet, verwendet
man dann auch für diese Verallgemeinerungen.
Da muss man natürlich auch ein bisschen mehr rechnen.
In diesem Umfeld gibt es auch noch andere Varianten, dass man nämlich
tatsächlich perfekte Hash-Funktionen baut, die man dann aber auf die
Elementmenge zuschneiden muss.
Oder eben bei diesem Dynamic Perfect Hashing, wo man so zweistufige
Hashtabellen verwendet, wo man die Elementmenge dann dynamisch
festlegen kann.
Vielleicht noch mal zu diesen perfekten Hashtabellen, Hash-Funktionen,
die die Hash-Funktionen auf die Elementmenge zuschneiden.
Da brauche ich halt dann wenige Bits pro Element.
Und das ist insbesondere dann spannend, wenn ich die Elemente selber
gar nicht abspeichern muss.
Zum Beispiel hat man manchmal Anwendungen, wo man eine Funktion
abspeichern will oder sagen wir mal eine Wertetabelle.
Sie haben eine Elemente und für jedes Element möchte man einen Wert
haben.
Die Elemente selber interessieren sie gar nicht.
Aber sie wollen halt diese Wertetabelle für die Funktion abspeichern
und sie wollen diese Funktion auswerten können in konstanter Zeit.
Und dann kann ich eben tatsächlich... genau und dann ist es vielleicht
noch so, dieser Funktionswert, das ist vielleicht auch wenig, nur ein
paar Bits oder so.
Dann können sie so eine perfekte Hash-Funktion nehmen, die irgendwie
ein paar Bits pro Element braucht und die adressiert dann eine
Wertetabelle.
Und dann haben sie eine extrem kompakte Datenstruktur, wo sie die
Schlüssel gar nicht mehr speichern müssen.
Und da gibt es eine ganze Reihe Anwendungen von dieser Sichtweise.
So, gibt es noch Fragen zu sehr platzeffizienten oder sehr schnellen
Hash -Tabellen?
Dann kommen wir jetzt dem nächsten Kapitel externe Algorithmen.
Wir werden uns das vor allem anschauen in einem sehr einfachen Modell
von Speicherhierarchien, das ich in der Einführungsvorlesung über
Algorithmen Engineering auch schon vorgestellt habe.
Wenn wir uns hier das obere anschauen, dann ist das im Prinzip das von
Neumann - Modell für sequentielles Rechnen.
Also wir haben einen frei programmierbaren Speicher, der von einer
sequentiellen CPU zugegriffen wird, die halt immer beliebige Wörter
aus dem Speicher liest, in konstanter Zeit Operationen darauf
ausführt, auch wieder abspeichert.
Das Neue ist jetzt, dass wir sagen, dieser frei zugreifbare Speicher,
der hat begrenzte Größe und zwar M Maschinenworte.
M ist ein Parameter dieses Modells und es gibt aber auch noch einen
großen Speicher, den man aber nur blockweise zugreifen kann.
Also immer Blöcke von B Maschinenwörtern und dann ist B halt der
andere Parameter.
Und viele Algorithmen, jetzt sage ich erstmal vielleicht, was man da
modelliert.
Das Schöne ist, damit kann man ganz viel modellieren.
Die ursprüngliche Sichtweise war, das ist eine Festplatte, deshalb
habe ich das so ein bisschen rund gemalt.
Das ist der Hauptspeicher.
Das ist auch immer noch relevant, aber das könnte zum Beispiel auch,
das hier könnte auch der Hauptspeicher sein und das ist dann einer der
drei Cache-Levels, die aktuelle Mikroprozessoren haben.
Oder das könnte auch der L1-Cache sein und das ist der L3-Cache.
Oder das könnte eine SSD sein und das ist der Hauptspeicher.
Das kommt eben wirklich darauf an, wo jetzt in ihrer Anwendung der
Flaschenhals liegt.
Je nachdem guckt man sich halt die beiden Ebenen der
Speicherhierarchie an, die gerade für die Performance wichtig sind.
Und das ist jetzt ganz wichtig.
Wir haben in realen Architekturen viel komplexere Speicherhierarchie.
Ich habe aber in der Einführungsvorlesung schon gesagt, es hat
eigentlich keinen Sinn, Algorithmen zu entwerfen oder zu analysieren
in solchen sehr detaillierten Modellen, weil die Komplexität viel zu
groß ist.
Sie kriegen keine portablen Algorithmen hin, sie verstehen die Analyse
nicht oder sie kriegen sie erst gar nicht hin.
Das heißt, es ist wichtig eigentlich mit einfachen Modellen zu
arbeiten und das ist ein sehr gutes Beispiel dafür.
Und das möchte ich jetzt so ein bisschen mit Leben füllen.
Ich werde Ihnen ein paar Algorithmen vorführen, die tatsächlich in der
Praxis dann auch gut funktionieren.
Und dann kann man eben sich später noch überlegen, wie genau
implementiere ich die, damit ich das auf einer bestimmten Auswahl der
Speicherhierarchie eben habe oder wie gehe ich jetzt damit um, dass
ich in Wirklichkeit mehrere Prozessoren habe.
Trotzdem sind die Grundalgorithmen dann die gleichen.
Fragen zu dem Modell?
Genau.
Bei der Algorithmenanalyse ist es jetzt so, dass wir Blockzugriffe
zählen.
Das heißt, im Extremfall wird die Rechenoperation, die die CPU hier
durchführt, zählen wir gar nicht mehr.
Das ist auch eine Vereinfachung.
Aber natürlich sollte man den Algorithmus dann sozusagen auch auf
verschiedene Arten und Weisen analysieren, dass man nämlich zusätzlich
vielleicht noch den internen Rechenaufwand zählt.
Oder vielleicht auch noch andere Operationen, die mit anderen
einfachen Modellen dann...
Okay.
Schauen wir uns mal einen ganz einfachen External-Memory-Algorithmus
an, der aber schon eine dramatische Leistungsverbesserung bringt
gegenüber einer naiven Implementierung.
Wir wollen einfach einen Stapel implementieren.
Also die Operationen PUSH und POP wird jetzt implementiert als eine
Datei.
Das sind diese blauen Dinger hier und zwei Pufferblöcke, die im
Hauptspeicher sind.
Man kann sich überlegen, dass zwei wichtig sind.
Einer könnte in der Praxis funktionieren, aber es gibt
Operationenfolgen, wo das nicht funktioniert.
Können Sie sich mal überlegen, woran das liegt.
Aber ich sage jetzt lieber, wie ich die Operationen implementieren
möchte.
Also die PUSH-Operation macht PUSH so lange in diesem Puffer, wie das
geht.
Also hier ist so ein Bild.
In dem Fall ist jetzt die Pufferblock 1 voll, Pufferblock 2 ist halb
voll und dann kann ich da halt ein weiteres Element reinschreiben.
Alles gut.
Keine IOs.
Aber es könnte natürlich sein, dass beide Puffer voll sind.
Dann wird der Puffer 1, also der, der hier weit weg von dem Top-of
-Stack -Pointer ist, der wird auf die Platte geschoben und die beiden
Puffer wechseln ihre Rolle.
Also danach sieht es dann eigentlich so aus wie hier.
Also ich habe, der Puffer 2 ist leer und der Puffer 1 ist halt in dem
Fall dann voll, weil er ja gerade der zweite Block auch voll war.
Das wird jetzt der erste Block und damit ist sozusagen mein Gesamt
-Puffer halb voll.
POP funktioniert so ähnlich.
Das mache ich aus dem Puffer, so weit es möglich ist.
Wenn beide Puffer leer sind, lese ich halt Puffer 1 aus der Datei und
dann ist das Ganze wieder halb voll.
So.
Hat jetzt jemand eine Idee, warum man mit einem Puffer hier nicht
auskommt?
Also das ist so ein bisschen so ähnlich wie die amortisierte Analyse
von wachsenden Arrays.
Man könnte ja irgendwie die Situation haben, dass man immer
abwechselnd Push- und Pop-Operationen machen, die dann jedes Mal eine
IO -Operation erfordern.
Also machen wir mal ein Beispiel.
Also wir haben jetzt die Situation, wir haben nur einen Puffer-Block
und der ist komplett voll.
Und jetzt mache ich einen Push.
Was passiert dann?
Dann habe ich gesagt, ich schreibe das hier in den Hauptspeicher.
Also kommt der hier auf die Platte.
Und dann habe ich hier einen leeren Puffer und ein Element.
Dann mache ich einen Pop.
Dann habe ich einen leeren Puffer.
Dann mache ich noch einen Pop.
Dann muss er den vollen Block hier wieder reinlesen.
Ich kann ein Element rausholen.
Das sieht so aus.
Dann mache ich einen Push.
Dann ist er wieder voll.
Und ich bin auch in der Situation.
Und das immer abwechselnd.
Also Push, Pop, Pop, Push, Push, Pop, Pop.
Und ich habe jeweils für zwei Operationen eine IO-Operation.
Das ist zu teuer.
Und das kann man eben leicht umgehen, wenn man diese zwei Puffer
verwendet.
Die Details des Beweises möchte ich nicht vorführen.
Aber das ist eine amortisierte Analyse, die eigentlich ganz analog
funktioniert, wie wir das für dynamisch wachsende Arrays gesehen haben
in Algorithmen 1.
Sogar noch einfach, weil diese Datenstrukturen immer gleich groß sind.
Was man dann im Endeffekt hat, ist, dass man amortisiert 1 durch B IO
-Operationen pro Stack-Operation hat.
Das ist also dann um den Faktor B effizienter als eine naive
Implementierung, die einfach immer einen zufälligen IO auf die Platte
macht.
Fragen dazu?
Man kann sich das jetzt auch überlegen, wie man das dann erweitert.
Für zum Beispiel FIFO-Queues oder Double-Ended-Queues.
Die kann man dann alle mit einer konstanten Anzahl Pufferblöcke so
implementieren, dass man von 1 durch B IOs pro Operation hat.
Dann möchte ich mal was vielleicht etwas komplexeres vorstellen.
Externes Sortieren.
Da jetzt n unsere Eingabegröße.
Wie lange brauchen wir, um große Datenmengen zu sortieren, die am
Anfang auf der Platte liegen oder in dem externen Speicher halt.
Und dann soll die sortierte Ausgabe auch im externen Speicher liegen.
Dafür schauen wir uns erst mal eine einfache Basis-Operation an.
Mission zweier sortierter Folgen.
Als Repräsentation wähle ich jetzt eine Datei und ich mache hier
Annahmen darüber, wie das Betriebssystem eine Datei implementiert.
Nämlich auch wieder mit Pufferblöcken.
Ganz ähnlich, wie das eben bei den Stacks war.
Und zeige aber bei der Analyse, was da dann passieren müsste.
Also wir haben zwei sortierte Folgen A und B, die als Datei
repräsentiert sind.
Und wir wollen bei Mission, das heißt eine Folge C erzeugen, die auch
wieder sortiert ist und die Elemente aus A und B enthält.
Und was wir jetzt immer machen, wir haben eine interne gespeicherte
Variable x und y, die jeweils das kleinste noch nicht verarbeitete
Element von A und B darstellen.
Haben eine Schleife, die A-Betrag plus B-Betrag laufen wird.
Wenn x kleiner y ist, ist x offenbar das kleinste noch nicht
verarbeitete Element.
Dann schreibe ich das in die sortierte Folge C und muss dann, da das
ja das kleinste Element von A war, das nächste Element aus A lesen.
Das ist jetzt hier so ein bisschen dargestellt.
Ich nehme jetzt im Prinzip an, dass ich dieses schwarz umrandete Ding,
ist so ein Pufferblock, den mein Dateisystem im Hauptspeicher hält.
x ist das aktuelle Element.
Wenn das jetzt verarbeitet ist, lese ich das nächste Element.
Dann würde das hier weiß werden und das hier ist dann fett gesetzt.
Wenn ich das letzte Element aus dem Pufferblock gelesen habe, wird das
Betriebssystem den nächsten Block von A aus der Datei lesen.
Und um die Details muss ich mich dann angenehmerweise auch nicht
kümmern.
Das ist nämlich dann vielleicht sogar so, dass das Betriebssystem da
auch wieder so eine Doppelpufferung vornimmt, also im Hintergrund
bereits den nächsten Block liest, während der aktuelle Block
verarbeitet wird und ich damit dann noch höhere Bandbreiten erreichen
kann.
Aber da wir hier nur IO-Operationen zählen, interessiert uns das an
dieser Stelle nicht.
Aber wenn ich das so implementiere, profitiere ich dann trotzdem von
fortgeschritteneren Implementierungen, die weiter unten passieren.
Fragen zu dieser Merge-Operation?
Vielleicht nochmal auf der Schreibseite.
Habe ich hier auch diesen Pufferblock, da wird halt nur ein Element
nach dem anderen reingeschrieben.
Wenn der Pufferblock voll ist, schreibt er das auf die Datei und hat
dann einen leeren Pufferblock im Hauptspeicher wieder.
Frage?
Genau.
Das kommt jetzt.
Analyse.
Also ist da nicht die Laufzeit, sondern die Anzahl IO-Operationen?
Genau.
Also wie viele IOs brauche ich für das Lesen der Datei A?
Naja, das ist A-Betrag durch B aufgerundet, also kleiner gleich A
-Betrag durch B plus 1.
Für das Lesen von B brauche ich kleiner gleich B-Betrag durch B plus
1.
Für das Schreiben von C A-Betrag plus B-Betrag durch B aufgerundet.
Also insgesamt ist das kleiner gleich 3 plus 2 mal die Summe der
Längen der Eingaben.
Weil das Schreiben von C ist natürlich dann genau die Summe davon.
Und dieses plus 3 spare ich mir und schreibe das ist ungefähr zweimal
die Summe der Eingabelängen.
Was ich dann an Ressourcen brauche, sind drei Pufferblöcke.
Einen für A, einen für B, einen für C.
Das klingt jetzt nach einer trivialen Einschränkung, aber wir werden
halt dann externe Algorithmen kennen lernen, bei denen man dann eine
recht große Anzahl Pufferblöcke braucht und die beschränken dann
sozusagen die Auslegung des Algorithmus.
Da kommt man dann doch irgendwann an die interne Speichergröße dran
und das ist dann für die Analyse wichtig, genau zu gucken, was brauche
ich.
Was vielleicht auch noch ganz interessant ist, ich zähle jetzt hier
die IO-Operationen.
Man kann aber genauso gut auch über das Ein-Ausgabe-Volumen reden.
Also wenn man jetzt tatsächlich einen Algorithmus hat, bei dem man
sichergestellt hat, dass sämtliche IO-Operationen irgendwie einen
kompletten Block nützlicher Daten ranschaffen, dann kann man auch
einfach analysieren, was ist das gesamte Ein-Ausgabe-Volumen und das
sind dann oft Zahlen, die nur noch von der Eingabegröße abhängen und
gar nicht mehr von diesen Parametern m und b.
Das ist irgendwie praktisch, weil man eigentlich jetzt ein sehr
maschinenunabhängiges Komplexitätsmaß hat.
Insbesondere macht es bei der Analyse von IO-Volumen dann auch
durchaus Sinn, sich genau die konstanten Faktoren anzuschauen.
Wir hatten bisher bei der Algorithmenanalyse immer gesagt, naja, das
theoretische Modell zählt Maschinenbefehle, aber eigentlich müsste ich
für jeden Maschinenbefehl dann ja noch zählen, wie viele Taktzyklen
braucht er.
Das hängt aber bei modernen Architekturen wieder von tausend anderen
Hardware -Aspekten ab.
Das heißt, konstante Faktoren in der Laufzeitanalyse sind irgendwie
hoffnungslos, die wirklich komplett maschinenunabhängig zu erfassen.
Aber bei External-Memory-Algorithmen kann ich das plötzlich tun.
Das Ein-Ausgabe-Volumen ist etwas, das sehr greifbar ist und wie sich
das dann in Laufzeit umsetzt, hängt halt dann von irgendwelchen
technologischen Parametern der I.O.-Geräte ab oder vielleicht auch von
Details des Betriebssystems.
Aber man kann dann doch sehr oft sagen, aha, wenn ich hier das I
.O.-Volumen um Faktor 2 senke, dann wird tatsächlich der Algorithmus
auch schneller.
Während ich bei Operationen zähle, ist das oft viel schwieriger.
Wenn ich sage, ich spare hier so und so viele Multiplikationen, muss
dafür aber so und so viele zusätzliche Speicherzugriffe investieren,
dann ist völlig unklar, was das bedeutet.
Aber hier kann ich alles in die gemeinsame Währung Ein-Ausgabe-Volumen
übersetzen und hier wird es dann also viel spannender, auch konstante
Faktoren mehr anzuschauen.
Und Mischen ist offenbar eine ziemlich effiziente Operation.
Ich muss die Eingabe lesen, das Ergebnis schreiben, das klingt
irgendwie kaum zu verbessern.
Also es ist vielleicht auch ein guter Building-Block für komplexere
externe Algorithmen.
Jetzt schauen wir uns mal an, wie man daraus einen Sortieralgorithmus
baut.
Könnte jetzt auf den ersten Blick versucht sein, den Binary-Merge-Sort
-Algorithmus aus Algorithmen 1 direkt einzusetzen.
Das war ein rekursiver Algorithmus, der so top-down arbeitet, aber da
kommt man dann auf den untersten Rekursionsebenen
zu super kleinen Eingabefolgen, die aus einzelnen Elementen bestehen,
und die möchte man nicht irgendwie extern bearbeiten.
Muss man auch nicht, weil man da ganze Teilbäume der Rekursionen dann
im Hauptspeicher abarbeiten könnte.
Aber trotzdem macht es irgendwie nicht so viel Sinn, das rekursiv
darzustellen, sondern wir bauen jetzt einen nicht-rekursiven Merge
-Sort -Algorithmus, der bottom-up vorgeht.
Und dann macht es Sinn zu sagen, ja dann gehen wir doch mal... unser
Base -Case ist jetzt nicht irgendwie ein Element lesen und sich zu
freuen, dass das dann sortiert ist, sondern der Base-Case ist, wir
laden den ganzen internen Speicher mit Daten voll.
Man nennt das einen Run.
Hier habe ich zum Beispiel den Run, lade ich in den Hauptspeicher,
sortiere das mit einem internen Algorithmus und schreibe es wieder
raus.
Das mache ich mit jeweils Groß-M-Elementen und brauche dann also N
durch M Runs, aber im Endeffekt mache ich ja nichts anderes als alle
Elemente einmal lesen, dieser internen Sortier-Operation zu schreiben
und als so einen Run der Größe M wieder rausschreiben.
Wir müssen uns jetzt nicht wundern, dass das eben zwei N durch B IOs
braucht.
Oder von mir aus wieder plus eins.
Und ich habe hier jetzt so einen Fall, wo tatsächlich die interne
Speichergröße wichtig ist, die begrenzt sozusagen mit wie vielen Runs
wir hier arbeiten müssen.
Ich mache also erstmal diese Run-Formation und dann bottom-up gehe ich
immer vor und nehme Paare von Runs und mische die mit meiner Binary
Merge Operation zu einem doppelt so großen sortierten Run zusammen.
Das habe ich hier mal in dem Bild dargestellt.
Ich habe hier A und B gar nicht festgelegt.
Jedenfalls habe ich hier so eine Eingabe der Größe 48, also vier Runs
der Größe 12.
Hier werde ich die Buchstaben sortieren.
Das habe ich jetzt für diesen Run gemacht.
Dann nehme ich zwei Runs, mische sie zusammen zum sortierten Run und
dann die beiden entstehenden großen Runs zu einem.
Fragen zu dem Algorithmus?
Dann analysieren wir den mal.
Run-Formation haben wir gesagt, 2n durch b IOs.
Das Mischen der Paare braucht halt auch 2n durch b.
Wird alles einmal gelesen, alles einmal geschrieben.
Jetzt muss man sich noch überlegen, wie viele Iterationen brauche ich?
Na ja, ich halbiere jedes Mal die Anzahl Runs.
Ich habe am Anfang n durch M.
Dann brauche ich also log zur Basis 2 von n durch M und das noch
aufgerundet.
Also insgesamt 2n durch b mal 1 für die Run-Formation plus log n durch
M aufgerundet.
Fragen zu der Analyse?
Also hier haben wir jetzt tatsächlich den ersten Algorithmus, wo dann
beide Parameter b und M eine Rolle spielen.
Und wir sehen jetzt halt auch, dass je größer der interne Speicher
ist, desto schneller geht es das externe Sortieren.
Fragen dazu?
Gucken wir uns mal konkrete Zahlen an.
Ich habe jetzt mal so einen, ich sag mal gut ausgestatteten PC mir
angeschaut.
Ich gehe dann bei Alternate.de oder sowas auf die Webseite und gucke,
was sind da gut ausgestattete PCs und was sind aktuelle Festplatten.
Wie groß sind die?
Also die, die das beste Preis-Performance irgendwie oder also Preis
pro Byte haben.
Da sind dann irgendwie 3TB Platten sind im Moment so Standard und
günstig.
Damit kann man relativ problemlos 1TB Daten sortieren.
Also dieser Algorithmus oder die meisten der externen
Sortieralgorithmen, die man so sieht, sind nicht in place.
Das heißt, ich brauche doppelt so viel Platz auf der Platte, wie ich
Eingabegröße habe.
Und vielleicht ist auf der Platte auch noch was anderes drauf.
Also sage ich mal, ich will 1TB sortieren, brauche dann 2TB
Plattenkapazität.
Ich habe sagen wir mal 16GB RAM.
Und die Blockgröße ist jetzt ein bisschen spannender.
Wenn Sie da ältere Arbeiten oder Arbeiten von Theoretikern über
External Memory lesen, dann sind sie ein bisschen verwirrt, weil die
sagen dann ja, Festplatten haben irgendwie eine inhärente technisch
bestimmte Blockgröße.
Das stimmt bis zu einem gewissen Grade auch.
Es gibt zum Beispiel so Einheiten von, ich weiß nicht, 512 oder 1024
Byte, die gemeinsam gelesen werden und an einem fehlerkorrigierenden
Code unterworfen werden oder sowas.
Wenn Sie das aber als Ihre Blockgröße verwenden, kriegen Sie völligen
Quatsch raus.
Dann ist Ihr Algorithmus mehrere Größenordnungen langsamer, als Sie es
haben wollen.
Sondern die Blockgröße ist bei einer Festplatte tatsächlich irgendwas
von Designparameter, den Sie sich überlegen können für Ihren
Algorithmus.
Aber eine gute Faustregel ist zu sagen, ich gucke mir die Latenz an,
die ich habe, um eine beliebige Stelle meiner Festplatte zugreifen zu
können.
Das ist seit Jahrzehnten irgendwie in Größenordnung 10 Millisekunden.
Je nachdem ob es teure oder billige Hardware ist, dann Faktor 2, give
or take.
Und dann nehmen Sie eine Blockgröße, die dafür sorgt, dass dieser
Overhead für den Zugriff, Sie müssen ja da diesen mechanischen
Schreiblesekopf irgendwie bewegen, dass der amortisiert wird über eine
Datenmenge, die so groß ist, dass die Ein-Ausgabe-Bandbreite irgendwie
in der Nähe der Peak-Bandbreite ist, die Sie hätten, wenn Sie wirklich
nur sequenziell große Dateien legen und schreiben.
Und dann kommt man auf, also wenn Sie sich mal Bandbreiten heutiger
Festplatten angucken, die sind so in der Größenordnung 100 Megabyte
pro Sekunde, dann ist irgendwie ein ganz guter Kompromiss, 4 Megabyte
große Blöcke zu wählen.
Dann braucht ein IO sowas wie eine sechzehnte Sekunde.
Also dann hätten Sie, also ich habe hier Zweierpotenzen gewählt, damit
man gut rechnen kann, das kann auch ein Faktor 2 mehr oder weniger
sein.
Mit diesen Parametern würden Sie dann annehmen, dass Ihre Festplatte
64 Megabyte pro Sekunde IO-Bandbreite erreicht.
Jetzt setzen wir hier die Anzahl IO-Operationen ein.
Also N durch M ist dann 64 RANs.
Dann ist Log N durch M 6.
1 plus 6 ist 7.
Also Sie haben sieben Durchläufe durch die Daten.
Sie müssen jeweils hier lesen und schreiben.
Wenn Sie das alles ausrechnen, kommen Sie auf 2 hoch 16 Sekunden.
Das sind ungefähr 32 Stunden.
Also Sie können den Inhalt Ihrer Festplatte in eineinhalb Tagen
sortieren mit diesem Algorithmus.
Ich sage mal, das ist machbar, aber ich sage mal auch ziemlich bitter.
Da müssen Sie schon lange warten.
Wir wollen uns jetzt anschauen, wie man das Ganze von sieben
Durchläufen durch die Daten auf zwei Durchläufe reduzieren kann.
Und was man da macht, ist mehr Wege mischen.
RAN-Formation bleibt die gleiche.
Vielleicht kann man da hier den Algorithmus sich auch schon anschauen.
RAN-Formation bleibt die gleiche.
Aber was ich jetzt mache, ich mische so viele RANs zusammen, wie ich
es mir leisten kann.
In einem Rutsch nutze auch wieder meine Speicherkapazität voll aus.
Und wir werden sehen, ich kann dann sowas wie M durch B RANs in einem
Rutsch zusammensortieren.
Und das Ganze wird dann effizienter.
Die Zahlen gucken wir uns später an.
Schauen wir uns erst mal an, wie geht überhaupt das Mehr-Wege-Mischen.
Das ist eigentlich eine relativ simple Verallgemeinerung des Zwei-Wege
-Mischens.
Ich habe jetzt nicht mehr zwei Zahlen x und y, die das jeweils
kleinste Element der Eingabefolgen angeben, sondern ich habe k
Eingabefolgen.
k ist ein Tuning-Parameter, über den wir noch reden.
Und eine Ausgabefolge c.
x i ist jeweils das kleinste, noch nicht verarbeitete Element der
Eingabefolge a i.
Und ja, jetzt muss ich die ganzen Eingabe-Elemente verarbeiten.
Das sind Summe i gleich 1 bis k mal a i.
Betrag viele.
So, und jetzt muss ich jeweils das kleinste Element, das kleinste der
kleinsten Elemente sozusagen finden.
Das ist das kleinste, insgesamt noch nicht verarbeitete Element.
Also das kann ich jetzt hier... also finde i aus 1 bis k, so dass x i
minimal wird.
Auf den ersten Blick klingt das so, als bräuchte man dafür Zeit o von
k.
Theoretiker würde sagen, interessiert mich doch nicht.
Das sind ja keine IOO-Operationen.
Also ich gehe natürlich davon aus, dass diese x i im Hauptspeicher
sind.
Ich gehe außerdem davon aus, dass ich für jede Eingabefolge so einen
Puffer -Block im Hauptspeicher habe.
Also ich brauche k mal b Blocks, bloß ein bisschen für Programme und x
i usw.
Aber tatsächlich ist es so, wir reden ja auch über interne Arbeit, man
kann das im Endeffekt in einer Prioritätsliste speichern, das x i.
Und dann brauche ich nur o von log k Zeit.
Das wird später bei der Analyse der internen Arbeit eine Rolle
spielen.
Genau, also jetzt habe ich halt... ich brauche mehr Speicher für diese
Puffer -Blocks und ich muss ein bisschen mehr Arbeit leisten, aber das
ist interne Arbeit, um das wirklich kleinste verbleibende Element
auszuwählen.
Aber das dann in die Ausgabedatei c schreiben ist das gleiche wie
vorher und ich muss halt dann das x i als nächstes Element aus dem a i
lesen.
Gibt es Fragen zu dieser Mehr-Wege-Misch-Operation?
Analysieren wir das mal.
Anzahl IOs-Operationen, naja man muss Datei a i lesen, das kostet a i
durch b aufgerundet viele IOs.
Diese Rundung schenken wir uns jetzt mal.
Datei c schreiben, wie gehabt, Summe der Eingabelängen durch b.
Also insgesamt zweimal Summe der Eingabelängen durch b IO-Operationen.
So, das klingt jetzt auf den ersten Blick so.
Prima, dann wählen wir k als n durch b.
Das heißt, wir können alle Runs in einem Rutsch zusammen mischen und
alles ist gut.
Wir werden später auch sehen, dass das in der Praxis tatsächlich Sinn
macht.
Aber für die Theorie und auch für die breitere Anwendbarkeit des
Ergebnisses wollen wir diese Annahme mal nicht machen und überlegen
uns, naja, wie groß kann ich k denn maximal wählen?
Naja, diese k plus 1 Pufferblöcke müssen ja in den Hauptspeicher der
Größe m passen.
Wir haben jeweils Größe b, deshalb gilt sicherlich k plus 1 kleiner m
durch b.
Jetzt schenke ich mir dieses plus 1 und schreibe sowas wie k kleiner m
durch b.
Da bin ich ein bisschen zu optimistisch, aber die Asymptotik stimmt
dann am Ende.
Für die interne Arbeit später halten wir auch fest, dass der Aufwand
Summe der Eingabelängen mal locker ist.
Fragen zur Analyse?
Dann können wir jetzt den Sortieralgorithmus analysieren, der dadurch
entsteht.
Hier ist so ein Beispiel.
Ich habe jetzt vier, das ist die gleiche Eingabe, vier Runs und die
kann ich jetzt in einem Rutsch zusammenmischen.
In dem Fall Spielzeugbeispiel halbiere ich, verringere ich dann die
Anzahl Durchläufe durch die Daten von 3 auf 2.
Allgemeiner analysiert, die Anzahl IOs für die Randformation bleibt
die gleiche, die Anzahl IOs für eine Mischoperation bleibt auch die
gleiche, nur dass ich jetzt die Anzahl Rands um den Faktor m durch b
reduziere, der findet sich dann hinterher in der Basis des Logarithmus
wieder.
Also die Anzahl Mischdurchläufe, die ich brauche, ist jetzt log n
durch m zur Basis m durch b.
Insgesamt kriege ich dann 2n durch b mal 1 plus log m durch b, m durch
m.
Und das ist eine, ich sag mal, für den Nicht-Algorithmiker schon eine
relativ komplexe Formel.
Es sind vor allem drei Parameter drin, Logarithmusbasis, blablabla.
Trotzdem taucht genau diese Formel in ganz vielen externen Memory
-Algorithmen auf.
Selbst wenn da gar nicht sortiert wird, kommt am Ende wieder die
gleiche Komplexität raus.
Also diese Sortierkomplexität ist was sehr Fundamentales für externe
Memory -Algorithmen.
Deshalb haben die Algorithmiker da dann auch diese Funktion sort von n
definiert, die dann ganz oft in den Papers auftaucht.
Damit man diese lange Formel nicht mehr schreiben muss, schreibt man
einfach nur noch sort von n.
Fragen zu der Analyse des Multi-Way Merging Algorithmus?
Jetzt können wir... genau, jetzt habe ich gesagt...
Gucken wir uns erstmal die interne Arbeit an.
Da steht jetzt die Asymptotik, aber ich will vielleicht an der Tafel
mal Vergleiche zählen.
Das macht man oft bei Sortieralgorithmen, dass man sagt, was ich da
genau mache.
Das ist komplex, da sind viele Speicherzugriffe dabei.
Aber informationstheoretisch, was dahinter steht, ist, ich vergleiche
Elemente und nutze die Informationen, die ich dabei gewinne.
Vor allem haben wir ja auch diese untere Schranke, die zeigt, dass man
sowas wie nLogN-Vergleiche auf jeden Fall braucht, um n Elemente zu
sortieren.
Wir gucken jetzt mal, wie effizient dieser Mehr-Wege-Misch-Algorithmus
ist bezüglich der Anzahl Vergleiche.
Das ist auf den ersten Blick irgendwie eine ziemlich komplexe Formel,
wie viele Elementvergleiche habe ich.
Bei der Run-Formation nehme ich mal an, dass ich da einen
informationstheoretisch optimalen Algorithmus verwende.
Dann brauche ich sowas wie LogM-Vergleiche pro Element.
Dann habe ich Multi-Way-Merging, wo ich jedes Mal m durch b Rands mir
anschaue, also dann auch LogM durch b vergleiche.
Man kann hier tatsächlich auch den konstanten Faktor auf 1 drücken mit
einer passenden Priority Key.
Das sind so Turnierbaum-Datenstrukturen.
Details machen wir in Algorithm Engineering in der Vorlesung.
Und die Anzahl Phasen ist diese komplizierte Sache.
Aber jetzt lassen Sie mich mal auswerten, was dabei rauskommt.
Und Sie werden sich vielleicht ein bisschen wundern.
Die Aufrundung lasse ich weg und ich schreibe jetzt nur pro Element,
wie viele Vergleiche da stehen.
Was haben wir gesagt?
LogM plus LogM durch b plus Log zur Basis m durch b n durch m.
Das kann man aber schreiben, also Logarithmusgesetze braucht man hier
natürlich rauf und runter.
Log n durch m geteilt durch Log der Basis.
Log m durch b.
Ja,
das da ist ein Plus.
Sie haben recht, Entschuldigung, das muss ein Mal sein.
Und das ist praktisch, weil jetzt können wir das und das wegkürzen.
Und außerdem steht da jetzt Log m mal Log n durch m.
Nach Logarithmengesetzen kann man aber ein Produkt, ne, eine Summe von
Logarithmen als Logarithmus des Produkts der Werte machen.
Das ist also gleich Log m mal n durch m.
Dann kürze ich das auch noch weg und es steht einfach nur noch Log n
da.
Und jetzt kommt davor, das mache ich für jedes Element.
Also ich habe genau n Log n Vergleiche.
Das Einzige, was ich hier ignoriert habe, ist das Aufrunden.
Das heißt, ich habe jetzt informationstheoretisch nen sehr effizienten
Algorithmus, obwohl ich irgendwie an drei Stellen hier Dinge tue.
Ich mache internes Sortieren, ich mache Multi-Way Merging und ich
iteriere mehrere solche Multi-Way Merging-Iterationen.
Aber informationstheoretisch gesehen, weil ich immer gleich große Runs
mische, ist das ein sehr effizientes Verfahren bezüglich der Anzahl
Und das ist jetzt auch schon ein Hinweis, dass das bezüglich der
internen Arbeit eigentlich auch recht effizient ist.
Also ich mache nicht viel mehr interne Arbeit als bei normalen
internen Sortier-Algorithmen.
Das stimmt nicht ganz, weil insbesondere dieser Multi-Way Merging
-Prozess, wenn Sie da genauer hingucken, ist der ein bisschen weniger
effizient als das, was zum Beispiel bei Quicksort oder Samplesort und
solchen Dingen passiert, wo wir dann, glaube ich, bei dem parallelen
Algorithmen auch nochmal dazu kommen.
Aber insgesamt schon eigentlich ganz brauchbar.
Fragen zu der Analyse der internen Arbeit?
Ein anderer Aspekt, den man sich jetzt anschauen kann, wenn wir hier
wirklich über Festplatten reden, ist es tatsächlich so, dass dieser
komplizierte Ausdruck, Log Basis m durch b, n durch m, der ist
eigentlich immer 1.
Das liegt einfach daran, also diese Dinge, das war ja hier Log n durch
m durch Log m durch b, ich will, dass das kleiner gleich 1 ist.
Das ist dann der Fall, wenn n durch m kleiner m durch b ist.
Aber jetzt gucken wir uns mal an, wie ist das?
m durch b, wir hatten in unserem Beispiel, was war das?
16 Gigabyte RAM und 4 Megabyte Blöcke.
Das heißt, ich kann sowas wie 4000 RAMs zusammenmischen in diesem PC
-Beispiel, den wir hatten.
Vielleicht gibt es auch schlechter ausgestattete PCs, aber wenn man
sagt so, naja, 1000 ist sicherlich bei halbwegs vernünftigen Maschinen
irgendwie immer drin.
Aber wie groß ist n durch m?
Nein, das ist jetzt, klingt jetzt so, ja, Eingabegröße kann ja
irgendwas sein.
Aber man muss sich ja vielleicht überlegen, ich muss meine Eingabe
irgendwo speichern.
Auf den Festplatten.
Das kostet Geld.
Ich werde aber sicherlich keinen Rechner kaufen, bei dem ich 1 Million
Euro in Festplatten investiere und dann nur 100 Euro in RAM.
Das ist irgendwie nicht sinnvoll, sondern man wird, wenn man eine
Architektur hat, auf der man große Datenmengen verarbeitet, dafür
sorgen, dass man eine halbwegs vernünftige Balance hat zwischen dem,
was man in den Hintergrundspeicher investiert und dem, was man in den
Hauptspeicher investiert.
Also jetzt grob gesagt gleich viel oder von der gleichen
Größenordnung.
Und dann ist es eigentlich nur noch wichtig, wie viel teurer ist denn
RAM als Platte.
Und das ist im Moment, glaube ich, Faktor 300.
Das liegt auch ein bisschen daran, dass RAM im Moment sehr teuer ist,
schon lange sehr teuer ist.
Ich habe jetzt gerade auch gelesen, dass das möglicherweise
tatsächlich ein Kartell ist, das die RAM-Preise so hoch hält.
Trotzdem ist das der gleiche Wert, wie wir den eigentlich seit
Jahrzehnten haben, dieses Verhältnis.
Meine Hypothese ist sogar, dass bei Festplatten der langfristig
nochmal sinken wird, weil Festplatten eigentlich am Ende ihrer
Lebenszeit angekommen sind.
Die entwickeln sich nicht mehr so schnell, die werden auch nicht mehr
in so vielen Anwendungen gebraucht, weil man eigentlich mit
Halbleiterspeicher, also SSDs, heute die meisten Anwendungen viel
besser bedienen kann.
Und was wir da dann haben ist, dass die Blockgröße viel kleiner ist.
Also dieser Faktor steigt massiv, während der Preis pro Bit, da ist
der Faktor nicht 300, sondern im Moment sowas wie 20.
Das heißt, da gilt es erst recht.
Hat jemand eine Idee für irgendwie eine sinnvolle Zwei-Speicher
-Hierarchie -Ebene, wo das vielleicht nicht gilt?
Also das extreme Ding im Moment wäre, wenn ich einerseits den L1-Cache
nehme und andererseits den Hauptspeicher zum Beispiel.
Einen L1-Cache bei Intel-Architekturen, ich weiß nicht genau, 32, 64
Kilobyte für den Datencache.
Und dann ist der Hauptspeicher aber locker mal 64 Gigabyte.
Das sind dann sechs Größenordnungen dazwischen.
Das ist also eine ganz andere Hausnummer.
Da braucht man dann tatsächlich Algorithmen, wo man mehrere Durchläufe
hat, wenn man da cache-effiziente Sortieralgorithmen zum Beispiel
analysieren will.
Da ist der Faktor so viel größer, weil es nicht nur um die Kosten
geht, sondern auch darum, dass wenn ich einen Cache größer mache, dann
wird er nicht unbedingt teurer, aber er wird langsamer.
Einfach weil die Leitungen länger werden und die Anzahl Adress-Bits,
mit denen ich irgendwelche Operationen durchführen muss, werden größer
und so weiter.
Fragen zu dieser Argumentation?
Um das kurz zu sagen ist, wir können eigentlich das Sort N, wenn wir
wirklich über Festplatten oder Flash-Memory reden, das hier auf 1
setzen und dann steht hier einfach nur 4N durch B.
Also sortieren ist nicht viel teurer als Daten einfach nur lesen.
Sortieren ist ungefähr so teuer wie die Daten zweimal lesen und
zweimal schreiben.
Und wenn man noch genauer hinguckt, wenn man einen External-Memory
-Algorithmus, der Sortieren als Teilproblem hat, genau analysiert, ist
es oft so, dass man sich das Lesen der Eingabe und das Schreiben des
Ergebnisses, das kann man oft wegdiskutieren.
Wenn man hat dann so Pipeline-Verarbeitungen, wo man dann verschiedene
Phasen des Algorithmus direkt hintereinander stöpselt, dann kriegt man
2N durch B für Sortieren.
Also ist dann nur noch ein Faktor 2 teurer als die Daten einfach nur
einmal anzuschauen.
Das ist ganz wichtig, weil wir können also sozusagen Sortieren als
einen Building-Block von External-Memory-Algorithmen verwenden und es
kostet was, aber es kostet nicht richtig viel.
Und das heißt, alles was ich mit Sortieren irgendwie mir erleichtern
kann bei der Verarbeitung großer Datenmengen, kann ich mir meistens
auch leisten.
Und das ist eine wichtige Einsicht.
Wir werden da auch gleich eine Beispielanwendung sofort uns anschauen.
Jetzt gucken wir uns mal eine Verallgemeinerung von Sortieren an.
Das habe ich in Algorithmen 1 auch so gemacht.
Sortieren dynamisch ist im Prinzip eine Prioritätsliste.
Ich kann zum Beispiel auch sortieren, indem ich alle Elemente in eine
Prioritätsliste einfüge und sie dann mit Deletement wieder raushole.
Aber ich kann eben mehr Dinge tun.
Man kann sich jetzt fragen, kann ich diesen flexibleren Umgang mit den
Daten auch im External-Memory effizient machen?
Und das war erstaunlicherweise so, dass das...
Genau, also externes Sortieren, das gibt es seit immer.
Das war vielleicht in den 50er Jahren sogar noch wichtiger als heute,
weil man winzige Hauptspeicher hatte.
Da hat man dann Sortieren durch Mischen gemacht.
Und der begrenzende Faktor war dann nicht die Hauptspeichergröße,
sondern die Anzahl Bandlaufwerke, die man gleichzeitig betreiben
konnte.
Und dann hat man eben tatsächlich diese Bandinhalte gemischt.
Das war nochmal ein bisschen ein anderes Spiel, aber im Endeffekt die
gleichen Algorithmen.
Das heißt, effizientes externes Sortieren, auch mit Multi-Way Merging,
gibt es seit immer.
Externe Prioritätslisten hat spannenderweise ziemlich lange gedauert.
Bis da mal jemand was gemacht hat.
Und was irgendwie ganz witzig ist, dass dann...
Ende der 90er Jahre war ich damals am Max-Planck-Institut für
Informatik und dann haben, glaube ich, in dieser Arbeitsgruppe für
Algorithmen drei Leute mehr oder weniger unabhängig gleichzeitig
effiziente Priority Queues entworfen für externe Demografie.
Das war der Andreas Krauser in seiner Doktorarbeit, der Gerd Broder
als Post-Doc, zusammen mit einem Kollegen aus Dänemark und ich hatte
eigentlich vor, überhaupt mal auch praktisch das Ganze zu machen.
Also die beiden anderen hatten das ein bisschen theoretischer und ich
habe mir aber die praktischen Sachen angeschaut und auch eine
Datenstruktur dann gefunden, die heute auch noch eingesetzt wird und
die ich jetzt so mal vorführen möchte, beziehungsweise die Grundidee
davon.
Also was wir eigentlich wollen, ist
pro Operation 1 durch B mal Log-Basis M durch B, N durch M IOs
amortisiert.
Und wenn wir aber naiv vorgehen, zum Beispiel sagen, ja, wir haben in
Algo 1 einen Binary Heap kennengelernt, den legen wir einfach auf die
Platte und arbeiten darauf, dann kriegt man sowas wie, na ja, ganz
naiv sagen, Log-N IOs pro Delimit.
Aber man kann sich überlegen, dass man die obersten Levels dieses
Binary Heaps im Hauptspeicher hält und dann spart man sich sozusagen
Log -M IOs pro Operation und kriegt dann Log-N durch M.
Aber was wir wollen, ist viel weniger.
Wir wollen diesen Faktor 1 durch B und das haben wir ja gesehen, das
kann eine Million sein oder sowas und außerdem noch diese Basis M
durch B haben und haben dadurch um mehrere Größenordnungen schnellere
Operationen als wenn wir es naiv machen.
Da ist auch die Fallhöhe viel höher eigentlich als beim Sortieren.
Weil da haben wir ja jetzt gerade mal diesen naiven Binary Merge Sort
ersetzt durch Multiway Merge Sort und haben dann durch den Faktor Log
-M durch B gespart.
Das war dann in der Beispielrechnung ein Faktor dreieinhalb.
Hier sparen wir jetzt potenziell einen Faktor eine Million.
Und das ist ja eigentlich sogar noch viel spannender.
Also wie geht das?
Ich führe das jetzt erstmal vor für, ich nenne das mittelgroße
Priority Queues, die also schon viel größer sind als die
Hauptspeichergröße aber durchaus beschränkt in ihrer Größe.
Nämlich sowas wie M² durch B.
Genauer gesagt k mal m Elemente.
Also k und klein m, das sind Tuning-Parameter, aber am Ende wird dann
k gleich m durch b sein und klein m gleich Theta-Große.
Und außerdem mache ich noch was komisches.
Ich beschränke nicht die Größe der Datenstruktur, sondern die Anzahl
der Einfügeoperationen, weil das die Darstellung massiv vereinfacht
und weil die meisten Algorithmen ohnehin so sind, dass es keinen
großen Unterschied macht, ob ich mir die Maximalgröße der
Datenstruktur anschaue oder die Anzahl Operationen, weil der typische
Ablauf ist ohnehin, dass die Datenstruktur erstmal wächst, eine
Maximalgröße erreicht und dann wieder schrumpft.
Und die Gesamtzahl Einfügungen ist dann bis auf den konstanten Faktor
das gleiche wie die Maximalgröße.
Die Datenstruktur kann man am besten an diesem Bild verstehen.
Die hat drei Komponenten im Endeffekt.
Ich habe eine klassische Internal-Memory-Priority-Queue.
Das ist ein Einfügepuffer, der große klein m.
Die muss in den Hauptspeicher passen.
In dem Bild, alles was rot ist, ist im Hauptspeicher.
Und dann überlege ich mir jetzt vielleicht erstmal wie arbeite ich mit
diesem Puffer.
Ich habe gesagt, es ist ein Einfügepuffer.
Am Anfang ist meine Priority-Queue leer.
Der Puffer ist auch leer.
Also gehen Einfügungen einfach in den Puffer.
Also keine IOs.
Natürlich geht das irgendwann schief.
Dann ist der Puffer voll.
Was ich jetzt mache ist, ich sortiere den Puffer.
Kostet auch keine IOs.
Ist ja alles im Hauptspeicher.
Und dann schreibe ich diese sortierte Folge der Länge klein m auf die
Platte in den externen Speicher.
Und das sind diese Dinger hier.
Das Blaue ist extern.
Also ich habe bis zu K sortierte Folgen.
Und das einzige davon, was ich mir im Hauptspeicher habe, ist jeweils
ein Pufferblock mit den kleinsten, noch nicht entfernten Elementen.
Dann habe ich noch eine KW-Gemisch-Datenstruktur.
Die enthält im Endeffekt eine Priority-Queue, wo jeweils für jede
dieser Folgen das kleinste Element drin ist.
Und wenn Sie so wollen, sind diese Pufferblöcke auch Teile dieser KW
-Gemisch -Datenstruktur.
Dann ist irgendwie klar, was passiert.
Einfügen, sortieren.
Wenn der Puffer voll ist, sortieren und rausschreiben.
Und ich merke mir den kleinsten Block.
Den lasse ich im Hauptspeicher.
Und Delete-Min ist jetzt eigentlich auch einfach.
Es gibt zwei Möglichkeiten, wo das global kleinste Element stehen
kann.
Nämlich entweder im Puffer.
Dann kann ich es direkt aus dem Puffer rausholen.
Das kann mir nur helfen, weil ein Element, das ich da raushole, muss
ich niemals sortieren und rausschreiben.
Oder es ist halt irgendwo hier.
Aber es muss eines der kleinsten Elemente dieser Folgen sein.
Das heißt, in dieser Priority-Q sein.
Das heißt, ich muss nur ein Delete-Min aus dieser Priority-Q machen.
Beziehungsweise ich vergleiche das Minimum dieser Priority-Q mit dem
Minimum dieser Priority-Q.
Und je nachdem, welches da kleiner ist, wird dann aus der Q gelöscht
oder aus der.
Und natürlich, wenn ich hier lösche, muss ich dann das nächste Element
aus dem Pufferblock nehmen.
Oder wenn der Pufferblock leer ist, den nächsten Block von der Platte
lesen.
Fragen zu der Datenstruktur?
Analysieren wir das mal.
Das ist wieder eine amortisierte Analyse, aber ich fange jetzt nicht
an, detailliert mit irgendwelchen Tokens um mich zu werfen.
Es ist auch eigentlich ganz einfach.
Jedes Element wird einmal gelesen.
Und zwar zusammen mit B anderen.
Das heißt, für dieses Lesen habe ich einen Penalty von 1 durch B, den
ich auch der Insert-Operation schon zuschlagen kann.
Also ich habe so einen Token im Wert von 1 durch B IOs.
Das muss ich bei jedem Insert bezahlen.
Und das reicht dann aber, um, wenn ich hier so einen Pufferblock,
einen neuen zu lesen, für diese IO-Operation zu bezahlen.
Ansonsten wird jedes Element maximal einmal so einer internen Sortier
-Operation unterworfen.
Das kostet auch keine IOs.
Und dann rausgeschrieben.
Also jedes Element wird maximal einmal geschrieben und maximal einmal
gelesen.
Also ich habe für N Operationen 2 N durch B IOs.
Genauer gesagt sogar für N Einfüge-Operationen und so wie ich das
jetzt amortisiere, sind die Delete-Mins sozusagen umsonst.
Fragen dazu?
Also die Kosten sind tatsächlich amortisiert.
2 durch B IO-Operationen pro Insert-Operation und Delete-Mins sind
amortisiert gesehen umsonst.
Genau, und wenn ich jetzt über external...
wenn ich jetzt tatsächlich über Festplatten rede, dann wäre es das
jetzt auch schon fast.
Also ich kann jetzt meine Priority Queue so machen, dass ich...
Also wir haben ja gesagt K darf dann ruhig auch 1000 oder 4000 sein.
Ich kann dann eine Terabyte große Priority Queue maintainen.
Allerdings mit einem ziemlich großen Puffer, der dann den
Hauptspeicher ziemlich voll macht.
Und ich habe auch schon gesagt, wenn ich über die Cache-Levels der
Prozessoren rede, funktioniert das vielleicht nicht.
Und es war tatsächlich dann mein Anliegen damals, eine cache
-effiziente Priority Queue zu haben.
Also insbesondere, wie schlage ich Binary Heaps?
Das hatte bis dahin noch keiner gemacht.
Also es gab diese theoretischen Ergebnisse, die aber sehr große
konstante Faktoren da reinbauen.
Und ich habe gesagt, ich will mir das jetzt genau angucken, kann man
eine cache-effiziente Priority Queue machen.
Aber so, dass die theoretisch auch hier das Optimum erreicht.
Da kommt die Verallgemeinerung.
Aber hier habe ich noch eine Folie, die ich vergessen habe.
Interne Arbeit...
Ist aber nicht so spannend.
Für Delete-Min habe ich einen Vergleich, um die beiden Dinger zu
vergleichen.
Und Log-K-Vergleiche, um Delete-Min hier zu machen.
Oder Log-M
hier.
Oder Log-K hier.
Aber insgesamt auch von Log-M.
Und das Insert hat hier M mal Log-M-Operationen pro...
Einmal das Löschen amortisiert, Log-M pro Operationen.
Also das ist sehr effizient, was hier passiert.
Aber wie mache ich die großen Queues?
Das ist jetzt ein Zusatz, was man eigentlich gerne möchte ist, oder
das Beste, was man hier erreichen kann, ist, dass es genauso viele IOs
sind, wie für Sortieren.
Ich habe ja gesagt, wenn man eine Priority Queue hat, kann man damit
auch sortieren.
Ich kann erst alle Elemente einfügen in eine Priority Queue und dann
mache ich ganz viele Delete-Mins.
Also besser als dieses 2N durch B 1 plus Log-Basis M durch B N durch M
kann man nicht werden in der Anzahl IO-Operationen für N-Einfügungen.
Und das Überraschende war, da habe ich dann ziemlich lange gebastelt,
dass man das tatsächlich einschließlich des konstanten Faktors
erreichen kann.
Es gab wie gesagt mehrere andere Lösungen, auch eine nicht von der
Arbeitsgruppe, die alle asymptotisch diese Schranke erreicht haben.
Aber ich war der Erste, der diesen Faktor 2 erreicht hat damals.
Und das ist eben nicht nur wichtig, wenn man sagt, ich finde jetzt
konstante Faktoren wichtig, sondern das war eben auch wichtig, um in
der Praxis tatsächlich eine Verbesserung zu erzielen.
Und zwar nicht nur, wenn die Daten auf der Festplatte liegen, weil da
habe ich ja gesagt, da ist sozusagen die naive Implementierung eine
Million mal schlechter.
Da kann man sich einen Faktor 3, den man irgendwo wegwirft, leisten.
Aber wenn ich das auf der Hauptspeicher-Cache-Hierarchie habe, da kann
man irgendwie einen Faktor 3 oder 4 gewinnen, wie wir sehen werden.
Und dann darf ich den nicht wegwerfen.
Deshalb war das ganz wichtig.
Das ist jetzt auch tatsächlich so, also diese Konkurrenzergebnisse
sind theoretisch gesehen stärker, weil bei denen dieses N nicht die
Anzahl Einflüge Operationen ist, sondern die Maximalgröße der Q.
Das heißt, man kann dann Operationenfolgen definieren, wo diese Q
schlechter ist als diese Theorie-Datenstruktur.
Aber eine Anwendung zu finden, bei der das passiert, dürfte einem
recht schwer fallen.
Und man zahlt dann immer mit konstanten Faktoren, anderswo, die viel
schlimmer sind.
Wie sieht diese Datenstruktur aus?
Die ist eigentlich sehr ähnlich zu dieser mittelgroßen Q
-Datenstruktur.
Ich habe wieder einen Einfügepuffer.
Wenn der Einfügepuffer voll ist, schreibe ich die Sachen wieder raus
in sortierte Folgen der Länge M.
Das neue ist jetzt...
Also das Problem war ja, ich kann das K hier nicht beliebig groß
machen.
Ich kann also nicht beliebig viele von diesen sortierten Folgen
nebeneinander packen.
Deshalb mache ich folgendes.
Wenn ich mehr als K sortierter Folgen habe, nehme ich die Dinger und
mische sie zusammen zu einer sortierten Folge der Länge K mal M und
schreibe die in so eine weitere Gruppe von sortierten Folgen.
Und das kann ich wie oft wiederholen?
Genau Log Basis M durch B, N durch M.
Und dann kriege ich mehrere solcher Gruppen.
In meiner Implementierung habe ich tatsächlich so drei bis vier
Gruppen, die dann in der Praxis auftreten.
Und dann ist die Frage, wie man das so macht, dass diese zusätzliche
Hierarchie -Ebene einem nicht zu viel kostet.
Und das funktioniert dann so.
Vor allem, ich habe drei Gruppen, kann mir aber immer nur K-Elemente
leisten, die ich zusammenmischen kann.
Deshalb habe ich hier noch so Gruppenpuffer.
Die haben auch Größe klein m.
Das heißt, ich amortisiere dann viele Merge-Operationen in einer
dieser Gruppen über also viele Delete-Min-Operationen aus einer dieser
Gruppen über einen Puffer, wo ich dann immer gleich M-Stück davon
raushole.
Und dann kann ich es mir zum Beispiel auch leisten, Pufferblöcke von
der Platte zu lesen.
Man sieht hier auch recht komplexe Farben.
Die roten Sachen sind im Hauptspeicher, die blauen sind extern.
Aber es gibt hier so grüne Sachen, die dann hin und her geswappt
werden, die dann für die asymptotische Analyse auch wichtig sind.
Und dann habe ich mehrere von den Gruppenpuffern und dann gibt es
nochmal so einen Mischer und ich habe dann einen kleinen Deletion
-Puffer.
Also ich habe eine zusätzliche Hierarchie-Ebene da drin, wie das Ganze
dann abläuft und warum das dann diese Effizienz hier erreicht.
Das ist ein relativ komplexes Argument, aber damit möchte ich sie ja
auch nicht belasten.
Ich möchte halt nur hervorheben, dass diese einfache Queue hier eine
Verallgemeinerung hat, die tatsächlich auch sehr gut skaliert für
beliebig große Eingaben und theoretisch fast das Beste liefert, was
man sich vorstellen kann.
Fragen dazu?
Dann möchte ich Ihnen jetzt auch mal ein paar Experimente dazu
berichten.
Wir haben Experimente gemacht mit 32-Bit- Schlüsseln, zufällig
gewählt.
32 -Bit- assoziierter Information.
Dieser Lösch-Puffer, der kann ruhig auch sehr klein sein, der ist
Größe 32, die Gruppen-Puffer sind Größe 256, Merging-Degrees 128.
Compiler auf hochoptimierend gesetzt.
Und wir haben dann diese Parameter tatsächlich festgehalten über ganz
viele Architekturen, die wir ausprobiert haben.
Und das hat irgendwie nie einen Unterschied gemacht, wenn man an denen
dreht.
Ich habe die Experimente jetzt wiederholt für eine aktuelle
Architektur, habe da allerdings nicht mehr an den Parametern gedreht.
Das wäre nochmal ganz spannend, ob das inzwischen nach fast 20 Jahren
irgendwie sich die Architekturen so stark gewandelt haben, dass man da
mal dran drehen müsste.
Aber es funktioniert immer noch ohne Änderung der Parameter ganz gut.
Wir haben uns meistens die folgende Operationenfolge angeschaut.
Element einfügen, Element löschen, Element einfügen.
Das mache ich groß N mal.
Das heißt, dadurch, das ist immer so, dass es zwei Schritt vor, ein
Schritt zurück spielt.
Dann wächst also die Größe der Queue linear.
Und dann mache ich es umgekehrt, dann mache ich DeleteMin, Insert,
DeleteMin und dann schrumpft sie wieder linear.
Wir haben dann auch verschiedene Eingabefolgen untersucht.
Es war ein bisschen überraschend, dass das dann tatsächlich eine
gewisse Rolle spielt.
Trotzdem ist es jetzt vielleicht völlig absurd, sich einfach mal das
anzuschauen.
Und jetzt können wir mal gucken, was da passiert.
Also die beste Maschine damals war der DEC-Alpha-Prozessor mit 500 MHz
Taktfrequenz.
Das ist Baujahr 97.
Und was ich hier plotte, ist dieses groß N.
Das ist gleichzeitig die maximale Queuegröße und ein Viertel der
Operationen.
Auf der Y-Achse plotte ich nicht die Laufzeit, weil die wächst
natürlich stark an mit der Eingabegröße, sondern ich normiere das
sozusagen nach einer unteren Schranke für die Anzahl Vergleiche und
damit habe ich dann sowas wie eine Laufzeit pro Vergleich oder sowas,
die ich da plotte.
T-DeleteMin plus T-DeleteInsert geteilt durch LogN, weil ich sowas wie
LogN -Vergleiche pro Element brauche.
Das heißt, das ist insbesondere so, dass wenn es keine
Speicherhierarchie gäbe, müsste man bei einem binären Heap, das sind
hier diese Kreise, müsste man eigentlich eine flache Kurve erwarten.
Das ist aber nicht der Fall, bzw.
das ist am Anfang flach bis bei dieser Architektur 16.384 Elemente und
dann geht es so langsam linear hoch.
Das liegt halt daran, dass mit jeder Verdoppelung der Eingabegröße ich
dann einen zusätzlichen Cache-Fall im Endeffekt kriege.
Dann gab es ein Paper, das sagt, oh wir haben eine geniale
Verbesserung von binary Heaps, wir machen 4-ary Heaps.
Die waren zumindest auf der Architektur tatsächlich ein bisschen
besser, aber haben natürlich den gleichen Effekt, dass Cache-Falls
gibt, aber man spart irgendwie einen Faktor.
Also die Kurve ist flacher.
Das ist schon ein bisschen besser, aber irgendwie nicht super
spannend.
Während unsere Datenstruktur tatsächlich flach ist, was ein bisschen
überraschend war, dass die Kurve sogar runter geht.
Da dachten wir erst, das liegt an so Lower Order Terms.
Es ist aber tatsächlich ein zusätzlicher Effekt, dass diese konkrete
Operationenfolge führt dazu, dass ein immer größerer Anteil der Delete
-Min -Operationen aus dem Puffer erfolgt.
Beziehungsweise wenn ich etwas in den Insertion-Puffer tue und dann
das Delete-Min sozusagen ein frisch eingefügtes Element löscht, dann
spart sich das einiges an IO-Operationen.
Und es ist bei den verallgemeinerten Dingen dann sogar so, was die
Elemente ja in erster Näherung tun, ist, dass sie erstmal in die
Gruppe geschrieben werden, dann in die, dann in die.
Das heißt, sobald ich irgendwas direkt aus dieser Gruppe rausmische
oder aus der, spare ich auch bereits IOs, die ich kriegen würde, wenn
das hier wirklich durch alle Gruppen wandert, das Element.
Und man kann sich überlegen, dass diese Eingabefolge irgendwie dazu
führt, dass ein frisch eingefügtes Element tendenziell ziemlich klein
ist verglichen mit den Elementen, die noch in der Queue sind.
Weil das ist ja eine Priority-Queue, man löscht immer die kleinsten
Elemente.
Das heißt, alte Elemente, die schon lange in der Queue sind, sind
tendenziell ziemlich groß.
Während frisch eingefügte irgendwie uniform verteilt sind und dann
eher zu den kleinen gehören.
Und das ist ein Lokalitätseffekt, von dem man dann tatsächlich
profitiert.
Es gibt auch Anwendungen, die diese Struktur haben.
Man muss allerdings dazu sagen, es gibt auch welche, bei denen das
tatsächlich nicht passiert.
Zum Beispiel Dijkstra's Algorithmus macht ja, hat ja monotone Priority
-Queues, wo halt die eingefügten Elemente immer größer werden.
Weil das ist ja dann so dieser sich ausbreitende Suchradius des
Dijkstra -Algorithmus.
Da profitiert man nicht davon.
Das heißt, wenn man jetzt andere Eingabefolgen angucken würde, würde
man tatsächlich hier was Flaches sehen.
Trotzdem gewinnt man irgendwie einen deutlichen Faktor gegenüber
Konkurrenzimplementierung.
Und dann ist natürlich aus heutiger Sicht spannend, wie sieht das 20
Jahre später aus?
Da habe ich eine einigermaßen aktuelle Architektur von den letzten
Jahren, AMD Ryzen 1800X mit 16 MB L3-Cache, 3,6 GHz Taktfrequenz.
Der ist tatsächlich
Faktor 20 oder sowas schneller als dieser DC-Alpha.
Aber was jetzt spannender ist, wir haben eigentlich die Kurve sieht
qualitativ genau so aus, außer vielleicht, dass der Binary-Heap einen
viel steileren Anstieg hat.
Also diese ganze Performance-Steigerung, die ich kriege durch Erhöhung
von Taktfrequenzen, durch Erhöhung des Instruktionsparallelismus,
kriege ich tatsächlich nur, wenn ich Cachefalls vermeide.
Also der Penalty für ein Cachefall ist viel höher geworden als damals,
weil eben die Latenzen beim Speicherzugriff nicht so stark abgenommen
haben, wie die Taktfrequenzen zugenommen haben.
Und hier habe ich praktisch wieder dieses flache Verhalten und am Ende
einen Faktor 4 gewinnen und das ist eigentlich das gleiche wie der
Faktor 4, den ich hier hatte, außer dass ich jetzt bis zu 2x30
Elementen gehen muss, um das zu beobachten und damals bis 2x23.
Aber das ist auch irgendwie klar, 2x23 das ist hier da passt die
Eingabe fast noch in den Cache in den L3-Cache zumindest.
Also das finde ich ein ganz interessantes Ergebnis, dass ein
sorgfältig entworfener Algorithmus auch über 20 Jahre immer noch seine
Performance -Vorteile behält.
So, das waren Priority Queues.
Jetzt möchte ich mal einen ganz einfachen Graphen-Algorithmus im
External Memory vorstellen und zwar minimale Spannbäume mit Großkreis
-Algorithmus.
Und da machen wir es uns einfach.
Wir nehmen keinen voll allgemeinen minimalen Spannbaum-Algorithmus,
sondern einen sogenannten Semi-Externen.
Semi-Externe Graphen-Algorithmen sind solche, bei denen ich pro Knoten
konstant viele Maschinenworte im Hauptspeicher halten kann.
Also M ist gleich Omega klein n, wenn n die Anzahl Knoten ist.
Das heißt, die Kanten liegen auf der Platte und für die Knoten kann
ich aber konstant viel Information intern verwalten.
Das erleichtert mir den Entwurf von IO-effizienten Graphen
-Algorithmen.
Also hier die Prozedur Semi-Externer Kruskal, Eingabe ist ein Graph
mit Knotenmenge 1-n und eben einer Kantenmenge.
Was noch ganz interessant ist, ich brauche eigentlich gar keine Graph
-Datenstruktur.
Ich habe einfach eine Datei, die eine Liste von Kanten enthält.
Kante ist einfach ein Trippel, ein Knoten, noch ein Knoten und
Gewicht.
Und diese Liste E sortiere ich nach absteigendem Gewicht.
Das ist das gleiche, wie beim Kruskal-Algorithmus ohnehin gemacht
wird.
Nur, dass ich hier jetzt einen externen Algorithmus wähle und der hat
dann eben SortM IOs.
Und SortM war dieses 2n durch b mal 1 plus log Basis bla aufgerundet.
So, jetzt deklariere ich eine Union-Find-Datenstruktur.
Das ist jetzt genau der interne Algorithmus.
Union-Find-Datenstruktur war eine Datenstruktur, die eine Partition
meiner Eingabemenge verwaltet.
Und ich habe die Operation Find und Union.
Und Find liefert mir immer einen Repräsentanten einer Menge zurück.
Und Union fügt zwei Elementen zusammen und wenn ich sie gebaut habe,
am Anfang habe ich eine triviale Partition, wo jedes Element eine
eigene Teilmenge darstellt.
Und das Ganze repräsentiert sozusagen den minimalen spannenden Baum
der Kanten, die ich bereits gesehen habe.
Erinnern Sie sich vielleicht das Algorithm 1 dran.
Und was Kruskals Algorithmus macht, er iteriert durch die Kanten in
...
aber ich kann natürlich auch andersrum iterieren, also es ist nicht
falsch, was da steht.
Also ich iteriere durch die Kanten in aufsteigender
Gewichtsreihenfolge.
Das heißt, ich lese in der Datei, das sind 2n durch b i.
Wenn ich eine Kante uv gelesen habe, vergleiche ich die Repräsentanten
der Partitionen, in denen u und v sind.
Wenn die gleich sind, weiß ich, dass ich die Kante für den minimalen
Spannbaum nicht brauche.
Das war die Grundidee hinter dem Kruskals Algorithmus.
Wenn sie nicht gleich sind, weiß ich, dass ich das als MST-Kante
verwenden kann, gebe das aus und mache union auf uv.
Und das ist natürlich wichtig, dass das hier im Hauptspeicher
passieren kann, weil diese Union-Find-Daten-Struktur, das sind im
Prinzip irgendwelche Pointer, die ich verfolgen muss.
Und das auf der Platte zu machen, wäre sehr toll.
Was gibt es dazu noch zu sagen?
Erstmal nicht viel.
Also es ist eigentlich genau der Kruskal Algorithmus, nur dass ich
noch dazu sage, die Daten liegen halt auf der Platte.
Also einfacher geht es nicht für einen externen Algorithmus.
Und die Gesamtkosten sind jetzt so viel wie sortieren plus einmal
lesen plus die Ausgabe schreiben.
Wer hat eine Idee, wie man das noch weiter reduzieren kann?
Nehmen wir mal an, wir würden multivariable merge sort verwenden für
das Sortieren.
Also was macht multivariable merge sort?
Das liest die RANs und schreibt die Ausgabe in sortierter Reihenfolge.
Die Kanten, die ich da ausgebe, die brauche ich gar nicht erst auf
Platte schreiben.
Die kann ich dann gleich hier in dieser Hauptschleife verwenden, wenn
ich das will.
Zumindest, wenn ich es mir leisten kann, diese Pufferblöcke für das
Multivariable Merging gleichzeitig mit der Union-Find-Daten-Struktur
im Hauptspeicher zu halten.
Dann ist es sogar so, dass das Ganze billiger ist als Sortieren, weil
ich die Ausgabe gar nicht schreiben muss, sondern das Einzige, was ich
schreiben muss, ist der MST und der hat nur N Kanten und nicht M.
Im Endeffekt ist dieser semi-externe Kurskal ein bisschen billiger als
die Kanten-Sortieren.
Und die Union-Find-Daten-Struktur, die ist fast vernachlässigbar, weil
ich da Log-M-Vergleiche habe, die verglichen mit den fast konstant
vielen Operationen für so einen Union-Find vernachlässigbar sind.
Noch Fragen zum semi-externen Kurskal?
Dann ein bisschen Blick über den Tellerrand.
Wenn ich noch größere MSTs berechnen will, brauche ich zusätzliche
Ideen.
Auch Dinge, die darüber hinausgehen, was wir in Algorithmen 1 an
Algorithmen kennengelernt haben.
Der wichtigste Trick ist, wenn ich MST-Kanten identifiziert habe, wie
auch immer, kann ich die kontrahieren.
Das heißt, ich identifiziere die beiden Endpunkte und baue also neuen
Graphen mit weniger Knoten.
Und wenn ich das weit genug treibe, also viele Kanten kontrahieren
kann, kann ich einen Graphen, bei dem das N zu groß ist für meinen
semi -externen Algorithmus, sozusagen schrumpfen zu einem Graphen, der
viel weniger Knoten hat, aber ungefähr gleich viele Kanten und auf dem
dann den semi-externen Kurskal ausführen lassen.
Und was jetzt für diese Vorlesung vielleicht besonders elegant ist,
wenn man das richtig macht, ist dieses Schrumpfen braucht im
Wesentlichen eine externe Priority Queue.
Und die gibt es zum Beispiel auch in der External Memory Algorithmen
Bibliothek STXXL, die ein Doktorand von mir gemacht hat.
Und wenn man das dann verwendet, kann man einen ganz allgemeinen
externen MST-Algorithmus in einer zweistelligen Anzahl Zeilen einen
Code hinschreiben.
Das war damals die Bachelor-Arbeit von Dominik Schultes.
Der hat dann außerdem noch diese allgemeine Priority Queue durch etwas
ersetzt, was irgendwie ausnutzt, dass man da im Wesentlichen
ganzzahlige Prioritäten mitarbeiten kann.
Und da will ich Ihnen jetzt die Messergebnisse zuvorführen.
Ich habe hier erstmal sehr dünn besetzte Graphen mit M ungefähr gleich
2n.
Und hier erstmal die klassischen internen Algorithmen, Kruskals
Algorithmus und Prims Algorithmus.
Und hier die Zeit pro Kante in Mikrosekunden.
Und dann sehen wir hier die internen Algorithmen.
Da ist jetzt bei den sehr dünnen Kruskal deutlich effizienter und dann
hier der Prims Algorithmus und auf der damaligen Maschine war halt bei
20 Millionen Kanten dann Schluss für den internen Algorithmus.
Der externe Algorithmus
da zeige ich jetzt unseren Algorithmus für drei verschiedene
Instanzklassen, Random-Graphen, Geometrische Graphen und Grid-Graphen.
Und was wir da sehen, ist am Anfang der semi-externe Algorithmus.
Dem ist das mehr oder weniger egal, was für Graphen das sind.
Und wir sehen außerdem, das ganze kostet groben Faktor 2 gegenüber
einem internen Kruskal.
Und das ist sehr moderat.
Es war damals mit mehreren Festplatten implementiert.
Und dann ab 320 Millionen Kanten musste man dann diese Kontraktionen
durchführen.
Das kostet dann nochmal einen Faktor 2 und dann differenzieren sich
die Eingabe-Arten hier aus.
Also dieser kontraktionsbasierter Algorithmus der ist bei Grid- und
Geometrischen Graphen funktioniert der ziemlich gut, nicht nur die
Knotenzahl zu reduzieren, sondern auch die Kantenzahl.
Während bei Zufalls-Graphen das dann tatsächlich nochmal ein bisschen
hochgeht.
Aber was wir sehen, es ist tatsächlich so, dass man externe Memory
-MSTs sind eine relativ günstige Operation.
Was für heute allerdings wichtig ist, eine externe Prioritätsliste und
auch Kruskalls-Algorithmus sind irgendwie inherent sequenzielle Dinge.
Also dieses Ergebnis ist nicht ohne weiteres auf parallele Algorithmen
übertragbar.
Deshalb ist es heute eigentlich wieder ein bisschen offen, was der
beste parallele externe Algorithmus für minimale Spannbäume wäre.
Und wenn man will, wäre das auch ein Bachelor-Arbeitsthema oder Master
-Arbeitsthema, das man sich mal wieder anschauen könnte.
Also im Gegensatz zu dieser Priority-Queue, die man trotzdem auch
sequenziell braucht, ist das für Cash-effiziente Queues will man das
für MSTs nicht unbedingt verwenden, sondern echt parallelen
Algorithmus haben.
Da ist das Ergebnis ein bisschen veraltet.
Aber trotzdem ganz interessant, dass man durch Zusammensetzung dieser
Ergebnisse, die wir hier vorgeführt haben, auch einen nicht trivialen
Graphen -Algorithmus kriegt.
So, dann spare ich Ihnen mal die letzte Folge, sondern mache den Wrap
-Up dann beim nächsten Mal.
Und dann gehen wir zum nächsten Kapitel, Approximations-Algorithmus.
Vielen Dank.