Erstellen eines minimalen Graphen, der alle Kombinationen von 3-Bit-Binärzeichenfolgen darstellt
Ich habe einen Algorithmus, der ein Diagramm erstellt, das alle Darstellungen von 3-Bit-Binärzeichenfolgen in der Form der kürzesten Diagrammpfade codiert, wobei eine gerade Zahl im Pfad 0 bedeutet, während eine ungerade Zahl 1 bedeutet:
%Vor% Ausgabepfade, die 3-Bit-Binärzeichenfolgen aus added :
Dies sind also Darstellungen von 3-Bit-Binärzeichenfolgen:
%Vor% Wo im Schritt h = 0 die ersten 4 Unterlisten gefunden wurden und im Schritt h = 1 die letzten beiden Unterlisten hinzugefügt wurden.
Wie Sie sehen können, gibt es natürlich keine Reflexionen der gespiegelten Strings, weil ein solcher Graph in einem ungerichteten Graphen nicht benötigt wird.
Diagramm:
Die obige Lösung erstellt ein minimales Diagramm und die eindeutigen kürzesten Pfade. Dies bedeutet, dass eine Kombination einer binären Zeichenfolge nur eine Darstellung in dem Diagramm in Form des kürzesten Pfads aufweist. Die Auswahl eines bestimmten Pfades ist also ein einzelner Hinweis auf eine gegebene Binärsequenz.
Nun würde ich gerne Multiprocessing in der for m in c -Schleife verwenden, weil die Reihenfolge der gefundenen Elemente hier keine Rolle spielt.
Ich versuche Multiprocessing auf diese Weise zu verwenden:
%Vor% Die Mehrfachverarbeitung findet in der while-Schleife statt, und in der Funktion foo wird die Liste ' added ' erstellt. In jedem nachfolgenden Schritt h in der Schleife sollte die Liste added um nachfolgende Werte erhöht werden, und die aktuelle Liste added sollte in der Funktion foo verwendet werden. Ist es möglich, den aktuellen Inhalt der Liste in jedem nachfolgenden Schritt der Schleife an die Funktion zu übergeben? Da im obigen Code die Funktion foo den neuen Inhalt der added -Liste jedes Mal neu erstellt. Wie kann das gelöst werden?
Was in der Folge zu schlechten Ergebnissen führt:
%Vor% Weil für solch ein Diagramm, Knoten und Kanten, die Bedingung nx.shortest_path (graph, i, j) == added[k] für jeden endgültigen Knoten i, j von added[k] for k in added list nicht erfüllt ist.
Wofür h = 0 auf die Elemente [0, 2, 4], [0, 2, 1], [2, 1, 3], [1, 3, 5] gut sind, während die im Schritt h = 1 hinzugefügten Elemente, also [0, 1, 2], [1, 0, 3] , offensichtlich gefunden werden, ohne die Elemente aus dem vorherigen Schritt zu beeinflussen.
Wie kann das gelöst werden?
Ich stelle fest, dass dies eine Art sequentieller Algorithmus ist, aber ich interessiere mich auch für Teillösungen, d. h. für parallele Prozesse sogar für Teile des Algorithmus. Zum Beispiel, dass die Schritte von h beim Schleifen sequenziell ausgeführt werden, aber die for m in c Schleife ist Multiprozessing. Oder andere Teillösungen, die den gesamten Algorithmus für größere Kombinationen verbessern.
Ich bin dankbar, dass ich eine Idee für die Verwendung von Multiprocessing in meinem Algorithmus gezeigt und umgesetzt habe.
2 Antworten
Ich glaube nicht, dass Sie den Code parallelisieren können, wie er es derzeit ist. Der Teil, den Sie parallelisieren möchten, die for m in c -Schleife greift auf drei Listen zu, die global good , added und index und das Diagramm g selbst sind. Sie könnten ein multiprocessing.Array für die Listen verwenden, aber das würde den ganzen Punkt der Parallelisierung als multiprocessing.Array ( docs ) ist synchronisiert, so dass die Prozesse nicht parallel laufen würden.
Also muss der Code refaktoriert werden. Meine bevorzugte Methode zur Parallelisierung von Algorithmen besteht darin, eine Art Erzeuger / Verbraucher-Muster zu verwenden
- Initialisierung zum Einrichten einer Jobwarteschlange, die ausgeführt werden muss (wird nacheinander ausgeführt)
- haben einen Pool von Arbeitern, die alle Jobs aus dieser Warteschlange ziehen (läuft parallel)
- nachdem die Jobwarteschlange erschöpft ist, aggregieren Sie die Ergebnisse und erstellen Sie die endgültige Lösung (wird sequenziell ausgeführt)
In diesem Fall wäre 1. der Setup-Code für list_1 , count und wahrscheinlich für h == 0 case. Danach würden Sie eine Warteschlange von " Arbeitsaufträgen " erstellen, dies wäre die c -Liste - & gt; diese Liste an einen Haufen Arbeiter weitergeben - & gt; Holen Sie sich die Ergebnisse zurück und aggregieren Sie. Das Problem ist, dass jede Ausführung der for m in c -Schleife Zugriff auf den globalen Zustand hat und der globale Status ändert sich nach jeder Iteration. Dies bedeutet logisch, dass Sie den Code nicht parallel ausführen können, da die erste Iteration den globalen Status ändert und beeinflusst, was die zweite Iteration tut. Das ist definitionsgemäß ein sequentieller Algorithmus. Sie können nicht, zumindest nicht leicht, einen Algorithmus parallelisieren, der iterativ ein Diagramm erstellt.
Sie könnten multiprocessing.starmap und multiprocessing.Array verwenden, aber das löst das Problem nicht. Sie haben immer noch das Diagramm g , das auch von allen Prozessen gemeinsam genutzt wird. Also müsste das Ganze so refaktoriert werden, dass jede Iteration über die for m in c -Schleife unabhängig von jeder anderen Iteration dieser Schleife ist. oder die gesamte Logik muss geändert werden, damit die for m in c loop wird nicht benötigt, um damit zu beginnen.
AKTUALISIEREN
Ich dachte, dass Sie den Algorithmus vielleicht mit den folgenden Änderungen in eine etwas weniger sequenzielle Version umwandeln könnten. Ich bin mir ziemlich sicher, dass der Code schon etwas Ähnliches macht, aber der Code ist ein wenig zu dicht für mich und Graphalgorithmen sind nicht gerade meine Spezialität.
Derzeit generieren Sie für ein neues Tripel (z. B. '101' ) alle möglichen Verbindungspunkte im vorhandenen Diagramm, fügen dann das neue Tripel zum Diagramm hinzu und eliminieren Knoten basierend auf kürzesten Wegen. Dies erfordert die Suche nach kürzesten Pfaden auf dem Graph und Modifizieren, was eine Parallelisierung verhindert.
HINWEIS: Was folgt, ist ein ziemlich grober Überblick darüber, wie der Code refaktoriert werden kann. Ich habe das nicht getestet oder mathematisch verifiziert, dass es tatsächlich korrekt funktioniert.
HINWEIS 2: In der folgenden Diskussion '101' (beachten Sie, dass die Anführungszeichen '' eine binäre Zeichenkette sind, also '00' und '1' wo als 1 , 0 , 4 usw. (ohne Anführungszeichen) sind Scheitelpunkte im Diagramm.
Was wäre, wenn Sie stattdessen eine Art Teilstringsuche im vorhandenen Graphen durchführen würden? Ich werde das erste Triple als Beispiel verwenden. So initialisieren Sie
- erzeuge ein
job_queue, das alle Tripel enthält - nimm das erste Beispiel und füge das ein, zum Beispiel
'000'was wäre (0,2,4) - das ist trivial, du musst nichts überprüfen, weil das Diagramm beim Start leer ist Der kürzeste Pfad ist per definitionem derjenige, den Sie einfügen.
An dieser Stelle haben Sie auch Teilpfade für '011' , '001' , '010' und umgekehrt ( '110' und '001' , da der Graph ungerichtet ist). Wir werden die Tatsache nutzen, dass das bestehende Diagramm Unterlösungen zu verbleibenden Tripeln in job_queue enthält. Nehmen wir an, das nächste Triple ist '010' , Sie durchlaufen die binäre Zeichenkette '010' oder list('010')
- wenn ein Pfad / Scheitelpunkt für
'0'bereits in der Grafik existiert - & gt; weiter - wenn ein Pfad / Scheitelpunkte für
'01'bereits in der Grafik vorhanden ist - & gt; weiter - Wenn ein Pfad / Scheitelpunkte für
'010'vorhanden sind, sind Sie fertig, Sie müssen nichts hinzufügen (dies ist tatsächlich ein Fehlerfall:'010'hätte nicht mehr in der Jobwarteschlange sein sollen, weil sie bereits gelöst wurde).
Der zweite Aufzählungspunkt schlägt fehl, weil '01' nicht im Diagramm vorhanden ist. Fügen Sie '1' ein, was in diesem Fall der Knoten 1 des Graphen wäre und verbinden Sie ihn mit einem der drei even Knoten, ich glaube nicht, dass es wichtig ist, welche Sie müssen notieren Sie, mit wem Sie verbunden waren, nehmen wir an, Sie haben 0 ausgewählt.Das Diagramm sieht nun ungefähr wie
Die optimale Kante zum Vervollständigen des Pfads ist 1 - 2 (markiert mit Sternen), um einen Pfad 0 - 1 - 2 für '010' zu erhalten. Dies ist der Pfad, der die Anzahl der codierten Tripel maximiert, wenn die Kante 1-2 ist zum Diagramm hinzugefügt. Wenn Sie 1-4 hinzufügen, codieren Sie nur '010' triple, wobei 1 - 2 für '010' codiert, aber auch '001' und '100' .
Lassen Sie uns so tun, als hätten Sie zuerst 1 mit 2 verbunden, anstatt 0 (die erste Verbindung wurde zufällig ausgewählt), jetzt haben Sie ein Diagramm
und Sie können 1 entweder mit 4 oder mit 0 verbinden, aber Sie erhalten wieder ein Diagramm, das die maximale Anzahl der verbleibenden Tripel in job_queue codiert.
Wie überprüfen Sie also, wie viele Tripel ein potenzieller neuer Pfad codiert? Sie können dies relativ leicht überprüfen und noch wichtiger die Prüfung kann parallel durchgeführt werden, ohne das Diagramm g zu ändern, für 3-Bit-Strings sind die Einsparungen von Parallelen nicht so groß, aber für 32bit-Strings sie wäre. So funktioniert es.
- (sequenziell) generiert alle möglichen vollständigen Pfade vom Unterpfad
0-1- & gt;(0-1-2), (0-1-4). - (parallel) für jeden möglichen vollständigen Pfad prüfen, wie viele andere Tripel dieser Weg löst, d. h. für jeden Pfadkandidaten alle Tripel, die der Graph löst, und prüfen, ob diese Tripel immer noch in
job_queuesind.-
(0-1-2)löst zwei andere Tripel'001' (4-2-1) or (2-0-1)und'100' (1-0-2) or (1-2-4). -
(0-1-4)hat nur die dreifache'010', d. h. selbst , gelöst
-
Die Kante / der Pfad, der die meisten in job_queue verbleibenden Tripel löst, ist die optimale Lösung (ich habe keinen Beweis dafür).
Sie führen 2. oben parallel aus und kopieren das Diagramm in jeden Worker. Da Sie den Graphen nicht verändern und nur überprüfen, wie viele Tripel er löst, können Sie dies parallel tun. Jeder Arbeiter sollte eine Signatur wie
path ist entweder (0-1-2) oder (0-1-4) , copy_of_job_queue sollte eine Kopie der verbleibenden Pfade auf der job_queue sein. Für K-Worker erstellen Sie K-Kopien der Warteschlange. Sobald der Arbeitspool abgeschlossen ist, wissen Sie, welcher Pfad (0-1-2) oder (0-1-4) die meisten Tripel löst.
Sie then fügen diesen Pfad hinzu und ändern das Diagramm und entfernen die gelösten Pfade aus der Jobwarteschlange.
SPÜLEN - WIEDERHOLEN, bis die Auftragswarteschlange leer ist.
Es gibt ein paar offensichtliche Probleme mit dem oben genannten, für einen, der eine Menge von Kopieren und Schleifen von job_queue macht, wenn Sie mit großen Bitbereichen arbeiten, sagen wir 32 Bits, dann ist job_queue ziemlich lang Vielleicht möchten Sie nicht alle Mitarbeiter kopieren.
Für den parallelen Schritt über (2.) möchten Sie job_queue tatsächlich ein dict sein, wobei der Schlüssel das Tripel ist, sagen wir '010' , und der Wert ist ein boolesches Flag, das besagt, ob das Triple ist bereits in der Grafik codiert.
Gibt es einen schnelleren Algorithmus? Betrachte diese zwei Bäume, (ich habe die Zahlen im Binärformat dargestellt, um die Pfade einfacher zu sehen). Um nun diese von 14 Knoten auf 7 Knoten zu reduzieren, können Sie die erforderlichen Pfade von einem Baum auf den anderen legen? Sie können eine beliebige Kante zu einem der Bäume hinzufügen, solange sie keinen Knoten mit ihren Vorfahren verbindet.
%Vor%können Sie beispielsweise sehen, 01 bis 00 zu verbinden, wäre ähnlich dem Ersetzen des Kopfes des Baumes 0 durch 01, und damit mit einer Kante haben Sie 100, 101 und 110 hinzugefügt.
Tags und Links python algorithm python-3.x parallel-processing multiprocessing