Der vollständige Titel des Artikels hätte "Nachhaltige" topologische "Sortierung eines Graphen mit Zyklen in
O(|V| + |e| log |e|) in der Zeit und
O(|V|) im Speicher ohne Rekursion" lauten sollen, aber mir wurde gesagt Was ist es übertrieben.
Haftungsausschluss: Ich bin ein Programmierer, kein Mathematiker, daher ist an Orten, für die Sie treten können und sollten, eine ungenaue Sprache möglich.
Essenz der Aufgabe
Ich werde den Wortlaut des Problems, dessen Lösung ich teilen möchte, in Teilen analysieren.
Topologische Sortierung ist die Reihenfolge der Scheitelpunkte eines gerichteten azyklischen Graphen, in dem jeder der Scheitelpunkte, aus denen die Kante herauskommt, früher kommt als der Scheitelpunkt, in den diese Kante eintritt. Hier gibt es zwei wichtige Nuancen: Ein Graph kann
mehr als eine solche Reihenfolge haben und ist nur auf
azyklische Graphen anwendbar. Mathematiker kümmern sich nicht darum, aber Programmierer wollen manchmal Determinismus und ein bisschen mehr als "Es tut mir leid, Sie haben hier einen Zyklus, Sie werden keine Sortierung haben."
Daher fügen wir die
Stabilitätsanforderung hinzu : Ein Scheitelpunktpaar, dessen Reihenfolge nicht durch die Kanten des Diagramms angegeben wird, sollte durch die Reihenfolge bestimmt werden, in der diese Scheitelpunkte am Eingang des Algorithmus angekommen sind. Infolgedessen ändern wiederholte Sortierungen die Reihenfolge der Scheitelpunkte nicht.
Mit der fehlenden
Rekursion ist alles einfach, der Computer ist deutlich schwächer als die Turing-Maschine und der Speicher (und insbesondere der Stapel) ist begrenzt. Daher sind bei der angewandten Programmierung normalerweise iterative Algorithmen rekursiven vorzuziehen.
Und schließlich werde ich definieren, was ich als "topologische" Sortierung bezeichne, wenn das Diagramm
Zyklen enthält . Dies ist die Reihenfolge der Scheitelpunkte, die mit der tatsächlichen topologischen Sortierung übereinstimmt, wenn jeder der Zyklen durch einen Scheitelpunkt ersetzt wird und die Scheitelpunkte des Zyklus selbst gemäß der Stabilitätsanforderung in der ursprünglichen Reihenfolge relativ zueinander angeordnet sind.
Und jetzt,
mit all dem Müll, werden wir versuchen, ihn zu entfernen. Ich werde alles im Rahmen der zu Beginn des Beitrags angegebenen Zeit- und Speicherbeschränkungen tun.
Suche nach einer Lösung
Wenn Sie sich die vorhandenen Algorithmen für die topologische Sortierung ansehen (
Kahn-Algorithmus ,
Deep Search ), stellt sich heraus, dass alle, wenn es einen Zyklus gibt, "Ich kann nicht" sagen und aufhören zu arbeiten.
Lassen Sie uns daher auf der anderen Seite Algorithmen verwenden, die mit Zyklen etwas Verständliches bewirken können.
Finden Sie sie zum Beispiel. Unter den in Wikipedia aufgeführten
Algorithmen zum Auffinden von Zyklen in Diagrammen wurde auf
den Taryan-Algorithmus hingewiesen . Es enthält eine interessante Bemerkung, dass der Algorithmus als Nebenprodukt die
inverse topologische Sortierung des Graphen erzeugt:
Während die Reihenfolge der Knoten in jeder stark verbundenen Komponente nichts Besonderes ist, besteht eine nützliche Eigenschaft des Algorithmus darin, dass vor keinem seiner Nachfolger eine stark verbundene Komponente identifiziert wird. Daher stellt die Reihenfolge, in der die stark verbundenen Komponenten identifiziert werden, eine umgekehrte topologische Art der DAG dar, die von den stark verbundenen Komponenten gebildet wird .
Der Algorithmus ist zwar rekursiv und es ist nicht klar, was er mit Stabilität hat, aber dies ist eindeutig eine Bewegung in die richtige Richtung. Eine genauere Lektüre von Wikipedia zeigt einen Verweis auf den Artikel
Ein platzsparender Algorithmus zum Auffinden stark verbundener Komponenten , verfasst von Genosse David Pierce, in dem nicht nur ein zwingender Algorithmus vorhanden ist, sondern auch der Speicherbedarf im Vergleich zum Klassiker reduziert ist Tarjans Algorithmus. Der Bonus ist die
Implementierung des Algorithmus in Java . Muss nehmen!
Algorithmus PEA_FIND_SCC3 (V, E) aus Pierces Artikel Wir haben also eine Liste von Scheitelpunkten am Eingang und (dank Pierce) einen bestimmten Index der Komponente starker Konnektivität, zu der dieser Scheitelpunkt am Ausgang gehört. Der nächste Schritt besteht darin, die Eckpunkte stabil nach der Seriennummer ihrer Komponente zu sortieren. Für eine solche Aufgabe gibt es einen Algorithmus, der als Zählsortierung bezeichnet wird und dies in
O(n) Zeit ausführt.
Beim Sammeln des Algorithmus zu einem Haufen stellte sich heraus, dass die Tatsache, dass es natürlich ist, ihm die
umgekehrte topologische Sortierung zu geben, von Taryan aus sehr äußerlich ist - dann werden die benachbarten Zweige des Graphen (ohne eine Ordnungsbeziehung zwischen ihnen) rückwärts nummeriert, die Teile des Graphen jedoch nicht Wenn Sie Verbindungen untereinander haben, stellen Sie sich in umgekehrter Reihenfolge heraus ...
Die Antwort
Also die endgültige Lösung:
- Wir nummerieren die Eckpunkte der ursprünglichen Liste.
O(|V|) - Wir sortieren die Kanten jedes Scheitelpunkts nach der Nummer des Scheitelpunkts, zu dem die Kante gehört.
O(|e| log |e|) - Mit dem Pierce-Algorithmus finden und nummerieren wir die Komponenten einer starken Verbindung.
O(|V|) - Mithilfe der Sortierung durch Zählen sortieren wir die Scheitelpunkte anhand der Anzahl der stark verbundenen Komponenten, die sie empfangen haben.
O(|V|)
GitHub-Code, Java, gemeinfrei . Es kann angemerkt werden, dass der Pierce-Algorithmus, um die Stabilität der Sortierung sicherzustellen, leicht modifiziert ist und die Eckpunkte in umgekehrter Reihenfolge umgeht.
Aber warum ???
Und jetzt der Hintergrund, warum das alles gebraucht wurde. Beim Laden / Entladen dynamischer Bibliotheken (.so) muss glibc entscheiden, in welcher Reihenfolge die statischen Variablen initialisiert werden sollen. Variablen hängen voneinander ab, hängen von verschiedenen Funktionen ab usw. Im Allgemeinen bildet dies alles den Graphen, in dem es Zyklen gibt und der sortiert werden muss.
Es war einmal ein ziemlich suboptimaler Code, der die Aufgabe für
O(n^2) ausführte. Und im Allgemeinen hat dies niemanden wirklich gestört, bis 2012 festgestellt wurde
, dass der Code nicht richtig funktionierte und in einigen Fällen falsch war.
Die harten Männer von RedHat dachten, dachten und vermasselten noch ein paar Zyklen von oben. Problemfälle wurden repariert, aber der Algorithmus begann für
O(n^3) zu funktionieren, und dies machte sich bereits bemerkbar und bei einigen Anwendungen dauerte es einige zehn Sekunden, was 2013 ein
Fehler war . Außerdem entdeckte der Autor des Fehlers Fälle, in denen der Algorithmus mit
O(n^3) ebenfalls falsch war . Er schlug vor, den Taryan-Algorithmus zu verwenden, obwohl der Patch mit Korrekturen nie entworfen wurde.
Und die Zeit verging, glibc verlangsamte sich gnadenlos und 2015 gab
es einen weiteren Versuch, den Algorithmus zu reparieren . Leider wurde der Algorithmus erfolglos als
O(n^2) , abgesehen von der Verwirrung der Zweige des Graphen, zwischen denen die Reihenfolge nicht definiert ist.
Heute ist das Jahr 2019, glibc verlangsamt sich immer noch. Gemessen daran, wie viel Zeit ich gebraucht habe, um das Problem zu beheben, sind die Chancen, dass ich es zum Ende bringe, deutlich geringer als 100%. Dies wird durch die Tatsache weiter verschärft, dass Dinge in C ohne IDE-Unterstützung im GNU-Codierungsstilcode, verrückter Testläufer, geschehen („Wenn Sie den Test erneut ausführen möchten, löschen Sie einfach die entsprechende .out-Datei“). Und damit glibc einen Blick auf Ihren Patch werfen kann, müssen Sie das Verfahren zur
Zuweisung von Urheberrechten durchlaufen, den Patch ordnungsgemäß ausstellen und der Teufel weiß, was noch alles. Um das Problem der Erfindung eines Algorithmus, der das Problem löst, zumindest zu beseitigen, wurde dieser Beitrag verfasst.