Ich möchte die Inzidenzstruktur eines Graphen in Haskell rekonstruieren, die durch die Ausgabe einer breiten ersten Traversierung gegeben ist. Explizit besteht die Ausgabe aus einem Wurzelvertex und einer Liste von Nachbarschaften (eine Nachbarschaft ist eine Liste von Vertices, die als neu oder alt (= bereits besucht) markiert sind), wobei jede Nachbarschaft dem kleinsten Vertex entspricht, der keiner Nachbarschaft zugewiesen wurde , noch.
In jeder imperativen Sprache würde ich das Problem lösen, indem ich eine Warteschlange verwende:
%Vor%Ich habe versucht, diesen naiven Algorithmus in Haskell zu implementieren (indem ich eine Liste verwende oder Data.Sequence als Warteschlange verwende), aber ghci hat immer keinen Speicher mehr. Dies sollte nicht passieren, denn obwohl die Eingabe aus 300MB Daten besteht, sollten 16GB RAM eindeutig ausreichen.
Daher scheint die naive Implementierung einen Speicherverlust zu verursachen. Wie würden Sie diesen Algorithmus in Haskell implementieren?
Bearbeiten: Hier sind die (leicht vereinfachten) Datentypen, die ich verwende:
%Vor%Der Datentyp "Output" enthält die bereits analysierte BFS-Ausgabe, die aus dem Wurzelknoten und den Nachbarschaftslisten besteht. BFSNode entspricht einem Knoten in dem BFS-Baum, der entweder zu einem neuen Eckpunkt gehört, der zum ersten Mal besucht wird, oder zu einem alten Eckpunkt, der bereits besucht wurde und der daher durch seine eindeutige Nummer bezeichnet wird. Beachten Sie, dass der Analyseprozess ordnungsgemäß funktioniert und nur wenig Speicher belegt.
Mein Ziel ist es, "Output" in den Datentyp "Graph" zu konvertieren, der aus den Listen der Vertices und einer Inzidenzliste besteht.
Hier ist eine vereinfachte Version meiner Implementierung:
%Vor%"nbs" ist die Liste der Nachbarschaften, "qs" ist die Warteschlange. Die Funktion "nodeNr" extrahiert die eindeutige Identifikationsnummer aus einem Vertex, "isNew" testet, ob ein Vertex neu ist und "unNew" entpackt einen neuen Vertex aus dem Datentyp "BFSNode".
Bearbeiten2: Ich glaube, ich habe das Problem jetzt lokalisiert. Vielleicht hat es nichts mit meiner Umsetzung des Konvertierungsprozesses zu tun. Mein Fehler war, die eingebaute Funktion "read" zu benutzen, um den Datentyp "Output" aus einer Datei zu lesen. Ich erkannte jetzt, dass Haskell Probleme mit dem Lesen großer Dateien hat. Selbst wenn es nur darum ging, eine Liste von ganzen Zahlen zu lesen, z.B.
%Vor%Das Programm hat keinen Speicher mehr, wenn die Datei "test" groß genug ist. Ich verstehe jetzt, dass es keine gute Idee ist, Daten auf diese Weise zu analysieren, da "lesen" alle Daten in den Speicher lädt, bevor eine Ausgabe angezeigt wird, aber ich verstehe immer noch nicht, warum es 16 GB RAM füllt, obwohl die Datei nicht reicht sogar 500 MB. Hast du eine Idee was mit "lesen" nicht stimmt? Hat Haskell das gleiche Verhalten auf Ihren Maschinen?
Bearbeiten3: Jetzt habe ich eine stream-basierte Parsing-Funktion "readOutput" implementiert, die einen String übernimmt und den Datentyp "Output" zurückgibt. Diese Funktion ist faul, daher erhalte ich sofort eine Ausgabe, wenn ich sie anrufe. Aber wenn ich es mit meiner Konvertierungsfunktion "readTree" (die eindeutig tail-rekursiv ist) komponiere, bekomme ich überhaupt keine Ausgabe und die Speicherbelegung steigt wie üblich. Was mache ich falsch?
Bearbeiten4: Das Problem in Edit3 kam von einigen Einschränkungen, die ich jetzt entfernt habe.
In dieser Frage wird keine Schlüsselkomponente angegeben - wie wird das Diagramm in Haskell dargestellt? Funktionale Programme erfordern sorgfältig durchdachte Datenstrukturen, um die gemeinsame Nutzung zu maximieren und effizient zu arbeiten. Normalerweise bedeutet dies, dass sie rekursiv aus dem Nichts aufgebaut sind (induktiv). Es gibt ein Papier auf induktive Grafiken und funktionale Graphenalgorithmen das gibt eine Darstellung:
%Vor% Das heißt, ein Graph ist entweder Empty oder ein (kleinerer) Graph, der um einen Knoten erweitert ist. Das ist genau, wie Listen verwenden Cons in funktionalen Sprachen aufgebaut, mit der Ausnahme, dass der zusätzliche Knoten der kleineren Graphen zu spezifizieren, die Vorgänger-Links ([Int]) und die neue Knotennummer und Daten, (Int, a). Beachten Sie, dass sie dies auch aus Gründen der Effizienz als Abstraktionstyp implementiert haben.
Ein Graph mit einem Knoten kann durch Erweitern des leeren Graphen erzeugt werden.
%Vor%Mit dieser Struktur, es ist einfach eine rekursive Parsing-Algorithmus für Ihren BFS Baum zu definieren.
%Vor%Testen Sie es,
%Vor%Aus Gründen der Effizienz könnten Sie Folgendes tun:
Das news und seen Funktionen kombiniert let (ns,sn) = newseen nbr ([],[]) werden konnte und machte Schwanz rekursive (vorbei an ihre teilweise konstruierten Listen und Rückkehr sofort) für Effizienz.
Ihre Eingabe könnte den Knoten in der Mitte jeder Nachbarliste verfolgen. Dies würde die Listenverkettung in dem Stapel von Nachbarn vermeiden. Alternativ könnten Sie eine funktionale Warteschlange verwenden, um diesen Stapel zu halten.
Wenn Sie es nicht gesehen haben, würde ich Okasaki Buch über rein funktionale Datenstrukturen .
Tags und Links haskell breadth-first-search