Eq-Test für große DAG-Strukturen in Haskell

Question

Ich bin neu in Haskell (ein paar Monate). Ich habe ein Haskell-Programm, das einen großen Ausdruck DAG (kein Baum, ein DAG), möglicherweise tief und mit mehreren zusammenführenden Pfaden (dh die Anzahl der verschiedenen Pfade von der Wurzel zu Blättern ist riesig) assembliert. Ich brauche einen schnellen Weg, um diese dags auf Gleichheit zu testen. Die Standard-Ableitung von Eq wird nur recurse, die gleichen Knoten mehrmals erforschend. Momentan verursacht dies, dass mein Programm 60 Sekunden für relativ kleine Ausdrücke benötigt und nicht einmal für größere. Der Profiler zeigt an, dass er die meiste Zeit damit beschäftigt ist, die Gleichheit zu prüfen. Ich möchte eine benutzerdefinierte EQ implementieren, die dieses Problem nicht hat. Ich habe keine Möglichkeit, dieses Problem zu lösen, das nicht viel Umschreiben erfordert. Ich möchte deine Gedanken hören.

Mein erster Versuch war, Baumknoten mit einem Hash zu instrumentieren, den ich inkrementell berechne, indem ich Data.Hashable.hash benutze, während ich den Baum baue. Dieser Ansatz gab mir eine einfache Möglichkeit zu testen, zwei Dinge sind nicht gleich, ohne tief in die Struktur zu schauen. Aber oft in dieser DAG, wegen der Wege in der DAG Fusion, sind die Strukturen in der Tat gleich. Die Hashes sind also gleich, und ich gehe wieder zum vollständigen Gleichheitstest über.

Wenn ich einen Weg zur physischen Gleichheit hätte, dann würden viele meiner Probleme hier verschwinden: Wenn sie physisch gleich sind, dann ist es das. Ansonsten, wenn der Hash anders ist, dann ist es das. Gehen Sie nur tiefer, wenn sie physisch nicht gleich sind, aber ihr Hash stimmt zu.

Ich könnte auch Git imitieren, und berechnen Sie eine SHA1 pro Knoten, um zu entscheiden, ob sie gleiche Periode sind (keine Notwendigkeit zu recurse). Ich weiß genau, dass dies helfen würde, denn wenn ich die Gleichheit vollständig in Bezug auf die Hash-Gleichheit entscheiden lasse, dann läuft das Programm in Zehn-Millisekunden für die größten Ausdrücke. Dieser Ansatz hat auch den schönen Vorteil, dass, wenn aus irgendeinem Grund zwei gleiche dags physikalisch nicht gleich aber inhaltsgleich sind, ich in der Lage wäre, sie auch in diesem Fall schnell zu erkennen. (Mit Ids muss Id an diesem Punkt noch eine Traversierung durchführen). Also ich mag die Semantik mehr.

Dieser Ansatz beinhaltet jedoch viel mehr Arbeit als nur den Aufruf der Data.Hashable.hash-Funktion, weil ich es für jede Variante des dag-Knotentyps ableiten muss. Und außerdem habe ich mehrere dag-Darstellungen mit etwas anderen Knotendefinitionen, also müsste ich diese Hashing-Trick-Sache zweimal oder öfter machen, wenn ich mich dazu entscheide, mehr Repräsentationen hinzuzufügen.

Was würden Sie tun?

Answer 1

Ein Teil des Problems hier ist, dass Haskell kein Konzept der Objektidentität hat, also, wenn Sie sagen, Sie haben eine DAG, wo Sie zweimal auf den gleichen Knoten beziehen, was Haskell betrifft nur zwei Werte an verschiedenen Stellen ein Baum. Dies unterscheidet sich grundlegend von dem OO-Konzept, bei dem ein Objekt durch seinen Ort im Speicher indiziert wird, so dass die Unterscheidung zwischen "demselben Objekt" und "verschiedenen Objekten mit gleichen Feldern" sinnvoll ist.

Um Ihr Problem zu lösen, müssen Sie erkennen, wenn Sie das gleiche Objekt besuchen, das Sie zuvor gesehen haben, und um dies zu tun, müssen Sie ein Konzept des "gleichen Objekts" haben, das unabhängig vom Wert ist. Es gibt zwei grundlegende Möglichkeiten, dies zu attackieren:

• Speichern Sie alle Ihre Objekte in einem Vektor (das heißt ein Array) und den Vektorindex als Objekt Identität nutzen. Ersetzen Sie die Werte durch Indizes in Ihrer Datenstruktur.

• Geben Sie jedem Objekt ein eindeutiges "Identitäts" -Feld, damit Sie feststellen können, ob Sie dieses Objekt schon einmal beim Durchlaufen der DAG gesehen haben.

Ersteres ist, wie das Data.Graph Modul in den Verpackungsbehältern es tut. Ein Vorteil ist, dass, wenn Sie eine einzige Zuordnung von DAG zu Vektor haben, die DAG-Gleichheit nur Vektorgleichheit wird.

Answer 2

Jede effiziente Methode zum Testen auf Gleichheit wird mit der Art und Weise, wie Sie die DAG-Werte aufbauen, verflochten sein.

Hier ist eine Idee, die alle Knoten verfolgt, die jemals in einer Karte erstellt wurden. Wenn der Karte neue Knoten hinzugefügt werden, erhalten sie eine eindeutige ID.

Das Erstellen von Knoten wird jetzt monadisch, da Sie diese Karte (und die nächste verfügbare ID) während Ihrer Berechnung einfädeln.

In diesem Beispiel sind die Knoten als Rose Bäume umgesetzt und die Reihenfolge der Kinder ist nicht signifikant - daher der Aufruf sort in den Schlüssel in der Karte abzuleiten.

Ein Vorbehalt - dieser Ansatz erfordert, dass Sie alle untergeordneten Knoten eines Knotens kennen, wenn Sie es erstellen.