Ich habe einen Code geschrieben, der alle Pfade vor einer bestimmten Reichweite in einem dendritischen Stream-Netzwerk findet. Als Beispiel, wenn ich das folgende Netzwerk repräsentiere:
%Vor%als eine Menge von Eltern-Kind-Paaren:
%Vor%Es werden alle Pfade vor einem Knoten zurückgegeben, zum Beispiel:
%Vor%Der Code ist unten enthalten.
Meine Frage ist: Ich wende das auf jede Reichweite in einer sehr großen (z. B. New England) Region an, für die eine bestimmte Reichweite Millionen von Pfaden haben kann. Es gibt wahrscheinlich keine Möglichkeit zu vermeiden, dass dies eine sehr lange Operation ist, aber gibt es eine pythische Art, diese Operation durchzuführen, so dass keine neuen Pfade mit jedem Lauf erzeugt werden?
Wenn ich zum Beispiel get_paths (h, 2) benutze und alle Pfade, die vor 2 liegen, gefunden werden, kann ich später get_paths (h, 1) ausführen, ohne alle Pfade in 2 nachzuverfolgen?
%Vor%BEARBEITEN: Vor ein paar Wochen habe ich eine ähnliche Frage gestellt nach "ALLEN" Upstream-Angeboten in einem Netzwerk und erhielt eine ausgezeichnete Antwort, die sehr schnell war:
%Vor%Ich habe bemerkt, dass der def-upstream (): Teil dieses Codes Upstream-Knoten in sequentieller Reihenfolge hinzufügt, aber da es sich um eine iterative Funktion handelt, kann ich keine gute finden Möglichkeit, sie an eine einzelne Liste anzuhängen. Vielleicht gibt es eine Möglichkeit, diesen Code zu ändern, der die Reihenfolge beibehält.
Ja, Sie können das tun. Ich bin mir nicht ganz sicher, was Ihre Einschränkungen sind. Dies sollte jedoch auf dem richtigen Weg sein. Die Worst-Case-Laufzeit dafür ist O (| E | + | V |), mit dem einzigen Unterschied, dass wir in p.dfsh zuvor ausgewertete Pfade zwischenspeichern, im Gegensatz zu p.dfs nicht.
Dies wird zusätzlichen Speicherplatz-Overhead hinzufügen, also beachten Sie diesen Kompromiss - Sie sparen viele Iterationen (abhängig von Ihrem Datensatz) mit dem teuren von mehr Speicher, egal was passiert. Leider verbessert das Caching nicht die Reihenfolge des Wachstums, sondern nur die praktische Laufzeit:
%Vor% Die Ausgabe für p.dfsh ist die folgende:
Die Ausgabe für nur die reguläre p.dfs ist:
Wie Sie sehen können, mache ich ein DFS, aber ich verfolge die vorherigen Iterationen im Rahmen des Zumutbaren. Ich möchte nicht den Überblick über alle möglichen vorherigen Pfade behalten, denn wenn Sie dies auf einem großen Datensatz verwenden, würde es lächerliche Mengen an Speicher aufnehmen.
In der Ausgabe sehen Sie die Iterationszahl für p.dfsh(2) go von 8 bis 1. Auch die Zahl für p.dfsh(6) wird wegen der vorherigen Berechnung von p.dfsh(9) ebenfalls auf 2 reduziert. Dies ist eine bescheidene Laufzeitverbesserung gegenüber dem Standard-DFS, insbesondere bei signifikant großen Datensätzen.
Sicher, vorausgesetzt, Sie haben genug Speicher, um alle Pfade von jedem Knoten zu speichern, können Sie einfach eine einfache Modifikation des Codes verwenden, den Sie in dieser Antwort erhalten haben:
%Vor% Beachten Sie, dass für 20.000 Zugriffe der erforderliche Speicher für diesen Ansatz in der Größenordnung von Gigabyte liegt. Erforderlicher Speicher ist unter der Annahme eines allgemein ausgewogenen Baums von Reichweiten O (n ^ 2) , wobei n die Gesamtzahl der Reichweiten ist. Das wäre 4-8 GiB für 20.000 erreicht abhängig von Ihrem System. Die benötigte Zeit ist O (1) für jeden Knoten, nachdem die Pfade von h[1] berechnet wurden.