Was ist neu in Python 3.9 (2) -Sortierte nicht verteilte Diagramme in Python

Einführung

Neue Änderungen in Python 3.9, die voraussichtlich im Oktober 2020 veröffentlicht werden, sind im Artikel [Was ist neu in Python 3.9 (Zusammenfassung)] zusammengefasst (https://qiita.com/ksato9700/items/d5df9d36147796c86c77). Ich bin. Ich habe einen separaten Artikel zu einem Thema, das etwas umfangreich zu sein scheint, aber dies ist der zweite, der sich mit dem Sortieren gerichteter und nicht verteilter Graphen befasst.

Gerichtete unzirkulierte Graphen und topologische Sortierungen

Zunächst ist das Diagramm hier kein Liniendiagramm, Balkendiagramm oder Diagramm, das Daten visuell darstellt, sondern ein Diagramm der Diagrammtheorie. Ein Graph ist eine Art Datenstruktur, die aus Knoten (Eckpunkten) und Kanten (Zweigen) besteht, die sie verbinden. Sie können relevante Informationen darstellen, indem Sie den Knoten oder Kanten eine Bedeutung geben.

Es gibt verschiedene Arten von Diagrammen und ob die erste Gabel eine Richtung am Rand hat. Der mit der Richtung wird als gerichteter Graph (linke Seite) und der ohne Richtung als ungerichteter Graph (rechte Seite) bezeichnet.

Kanten verbinden Knoten, aber Sie können einen gerichteten Graphen verwenden, wenn zwischen den verbundenen Knoten eine Master-Slave-Beziehung besteht, und einen ungerichteten Graphen, wenn stattdessen eine gleiche Beziehung besteht.

Und ob es sich um ein Patrouillendiagramm handelt oder nicht, ist ebenfalls ein Punkt. Wenn es einen Knoten gibt, der zu Ihnen zurückkehrt, indem er der Kante folgt, wird er als zyklischer Graph bezeichnet, und wenn dies nicht der Fall ist, wird er als nicht kreisförmiger Graph bezeichnet. Der gerichtete azyklische Graph (Directed Acyclic Graph, DAG) hat die beiden Eigenschaften, gerichtet und nicht zirkulierend zu sein, und dies ist der Graph, mit dem wir uns diesmal befassen.

Dieser gerichtete nicht kreisförmige Graph (DAG) kann verwendet werden, um eine Vielzahl von Informationen darzustellen. In einem seltsamen Beispiel verwendet IOTA, ein Krypto-Asset, DAG. Gewöhnliche Krypto-Assets verwenden Blockchain, und ich denke, es kann als Einweg-DAG bezeichnet werden, aber IOTA verbindet es mit einer DAG, die mehrere Kanten hat. Es ist interessant.

In einer etwas häufigeren Anwendung gibt es ein Problem bei der Aufgabenplanung mit Abhängigkeiten. Jede Aufgabe ist ein Knoten, und die Abhängigkeit der Aufgabe wird durch eine Kante dargestellt. Wenn beispielsweise A → B, kann B erst gestartet werden, wenn A endet. Selbst wenn Sie eine Liste von Aufgaben mit komplizierten Abhängigkeiten haben, können Sie sehen, dass diese in der DAG ausgedrückt werden können, indem Sie sie in Aufgaben-zu-Aufgaben-Beziehungen aufteilen.

Zum Beispiel können B und C erst starten, wenn A vorbei ist. Und D kann nicht beginnen, bis B und C beendet sind. Eine solche Abhängigkeit wird wie folgt ausgedrückt.

Ein komplizierteres Beispiel wäre ungefähr so:

Etwas abseits der ausgetretenen Pfade gibt es ein Tool zur Visualisierung der DAG namens Graphviz. Dies beschreibt DAG in einem eindeutigen Format namens Punktformat, zeichnet es und konvertiert es in ein Bildformat wie PNG. Interessant ist, dass mehrere Zeichenalgorithmen verfügbar sind, mit denen Sie mit derselben Eingabe völlig unterschiedliche Ausgaben erhalten.

Wenn Sie beispielsweise das zweite Beispiel oben im Punktformat schreiben, sieht es so aus.

digraph example {
  graph [
    labeljust = "c"
  ];
  7, 5, 3, 11, 8, 2, 9, 10;
  7 -> 11;
  7 -> 8;
  5 -> 11;
  3 -> 8;
  3 -> 10;
  11 -> 2;
  11 -> 9;
  11 -> 10;
  8 -> 9;
}

Wenn Sie versuchen, dies mit dem Zeichenwerkzeug von Graphviz auszugeben, können Sie so viele Variationen vornehmen.

Es ist interessant. Es sieht nicht sehr gleich aus wie DAG, aber sie stammen alle aus derselben Punktdatei.

Jetzt besteht eine Ordnungsbeziehung zwischen den in der DAG ausgedrückten Aufgaben. Sie möchten also wissen, in welcher Reihenfolge Sie sie weglegen sollten. Das ist ein Zeitplanproblem. Zu diesem Zweck ist es notwendig, sie eindimensional anzuordnen und gleichzeitig die Abhängigkeiten zu erfüllen, was als ** topologische Sortierung ** bezeichnet wird.

Obwohl die Einführung verlängert wurde, hat Python 3.9 dem Modul "functools" eine Funktion namens "TopologicalSorter" hinzugefügt, mit der diese topologische Sortierung standardmäßig durchgeführt werden kann.

Versuchen Sie es mit Topological Sorter

Versuchen wir das Beispiel mit den am Anfang gezeigten Knoten A, B, C, D.

>>> from functools import TopologicalSorter
>>> ts = TopologicalSorter()
>>> ts.add('B', 'A')
>>> ts.add('C', 'A')
>>> ts.add('D', 'B', 'C')
>>> tuple(ts.static_order())
('A', 'B', 'C', 'D')

Nachdem ich mit TopologySorter () einen leeren Sortierer erstellt habe, füge ich nacheinander Knoten hinzu. TopologySorter.add () listet die Knoten auf, die im ersten Argument registriert werden sollen, und die Knoten, die von den nachfolgenden Argumenten abhängig sind. Knoten, die keine abhängigen Knoten haben (in diesem Fall "A"), können die Registrierung überspringen (da sie bei der Registrierung anderer Knoten als abhängig angezeigt werden). Dann wird das nach "TopologySorter.static_order ()" sortierte Ergebnis vom Generator zurückgegeben. Da es schwer zu sehen ist, wird es in einen Taple umgewandelt und angezeigt.

Wenn das Diagramm von Anfang an festgelegt ist, können Sie es dem Konstruktor geben und alles auf einmal erstellen.

>>> from functools import TopologicalSorter
>>> graph = {'B': {'A'}, 'C': {'A'}, 'D': {'B', 'C'}}
>>> ts = TopologicalSorter(graph)
>>> tuple(ts.static_order())
('A', 'B', 'C', 'D')

Hier werden dem Konstruktor Daten vom Wörterbuchtyp gegeben, bei denen der Schlüssel ein Knoten ist und der Wert von (einer Menge von) Knoten abhängt. Wenn Sie mehrere angeben, wird hier der Set-Typ verwendet, aber es scheint, dass es sich um ein Taple oder eine Liste handeln kann.

Dies ist alles, was Sie tun müssen, um zu sortieren, aber es gibt auch einige Methoden, wenn Sie etwas mehr Kontrolle wünschen. Zuallererst "was kann im Moment getan werden". Es wird eine Liste von Aufgaben sein, für die die Abhängigkeit mit get_ready () erfüllt ist.

Verwenden wir als Beispiel das etwas komplizierte Beispiel oben.

>>> from functools import TopologicalSorter
>>> graph = {
...    2: {11},
...    8: {7, 3},
...    9: {11, 8},
...   10: {11, 3},
...   11: {7, 5},
... }
>>> ts = TopologicalSorter(graph)
>>> ts.prepare()
>>> ts.get_ready()
(3, 7, 5)

Nachdem Sie TopologySorter erstellt haben, indem Sie die Abhängigkeitsdaten des Diagramms im Konstruktor angeben, müssen Sie zunächst "prepare ()" ausführen. Dies ist eine Methode, die eine Vorverarbeitung für die nachfolgende Verarbeitung durchführt. Wir prüfen auch, ob es sich bei dem hier registrierten Diagramm um eine Patrouille handelt. Wenn es sich um eine Patrouille handelt, wird "CycleError" angezeigt. Im obigen Beispiel wurde dieses prepare () nicht aufgerufen, aber es wird automatisch instatic_order ()aufgerufen (tatsächlich wird es beim Abrufen des ersten Wertes des Generators aufgerufen).

Nachfolgende Aufrufe von "get_ready ()" geben "(3, 7, 5)" zurück. Es wird als "ausführbar" unter den im Diagramm enthaltenen Knoten aufgeführt, die keine Abhängigkeiten aufweisen. Wenn Sie prepare () erneut aufrufen, wird diesmal()zurückgegeben. Es bedeutet: "(Im Moment) gibt es nichts anderes."

Ich werde die Grafik oben ausmalen. Hellgrün zeigt an, dass der Knoten funktionsfähig ist.

Was ist, wenn die "5" und "7" der möglichen Aufgaben erledigt sind? Die Methode "done ()" lehrt dies dem Sortierer. Wenn Sie die erledigten Aufgaben nebeneinander als Argumente aufrufen, ändert sich der interne Status. Wenn Sie also "get_ready ()" erneut ausführen, wird diesmal "(11,)" zurückgegeben.

>>> ts.done(5,7)
>>> ts.get_ready()
(11,)

Die Figur wird in eine dunklere Farbe geändert, um anzuzeigen, dass "5" und "7" vollständig sind. Und 11 ist betriebsbereit, da alle abhängigen Aufgaben abgeschlossen wurden. Es stimmt mit dem Ergebnis von ts.get_ready () oben überein.

Wir werden dies wiederholen, aber lassen Sie es uns in der Reihenfolge "11" → "3" → "8" vervollständigen.

>>> ts.done(11)
>>> ts.get_ready()
(2,)
>>> ts.done(3)
>>> ts.get_ready()
(8, 10)
>>> ts.done(8)
>>> ts.get_ready()
(9,)

Mit is_active () können Sie überprüfen, ob das Diagramm nicht ausgeführte Aufgaben enthält. Im obigen Zustand wurden "2", "9" und "10" noch nicht ausgeführt, sodass Sie sehen können, dass sich der Rückgabewert von "is_active ()" vor und nach ihrer Ausführung "() ändert.

>>> ts.is_active()
True
>>> ts.done(2, 9 ,10)
>>> ts.is_active()
False

Zusammenfassung

Ich habe die neue Funktion "ToplogicalSorter" untersucht und verwendet, die dem Modul "functools" von Python 3.9 hinzugefügt wurde. Ich dachte, es könnte nützlich sein, um die Reihenfolge der Stapelverarbeitung mit Abhängigkeiten zu bestimmen.