Ich implementiere R7RS-small Scheme und ich habe das folgende Problem mit der Implementierung von gleich ?: (wie sollte offensichtlich sein) gleich? testet value equality und ist darüber hinaus in der Lage, die Gleichheit zyklischer Datenstrukturen zu testen, ohne in Endlosschleifen zu geraten. Da ich jedoch Scheme in Haskell implementiere, habe ich keinen Zugriff auf zugrunde liegende Zeigerwerte, die in Ganzzahlen umgewandelt werden können, um in einer Hash-Tabelle * oder einer Suchbaumstruktur zu verfolgen, welche Knoten ich bereits verfolgt habe Pfade effizient zurückschneiden, die zu unendlichen Schleifen führen würden.)
Vielmehr muss ich mit der Gleichheit der Identität (gemessen durch (==) auf IOArrays zugrunde liegenden Paaren, Vektoren und Datensätzen) arbeiten, und daher kann ich scheinbar nur Listen erstellen, die markieren, welche Knoten ich habe gefolgt (getrennt durch den Typ), und dann suche ich für jeden weiteren Knoten die entsprechende Liste nach Knoten, denen ich bereits gefolgt bin, was von mir aus in O (n log n) in der Zeit und O (n) im Raum skaliert .
Habe ich recht, dass mir unter diesen Umständen der einzige verfügbare Algorithmus zur Verfügung steht oder gibt es andere effizientere Implementierungen, die ich vermisse?
Ich habe darüber nachgedacht, jeden Wert, der Referenzen enthalten kann, mit einem Tag zu markieren, das in einem Suchbaum oder einer Hash-Tabelle * verwendet werden könnte. Das Problem hierbei ist jedoch, dass dies für Listen besonders Platz-ineffizient wäre zwei Wörter für das Tag für jeden Knoten, wobei einer die ThreadId und einer eine eindeutige Thread-ID ist (die ThreadId ist notwendig, weil ich sonst eine Multithread-Implementierung von Scheme hätte) um einen gemeinsamen eindeutigen ID-Zähler hinter einer MVar oder TMVar zu schützen, der in vielen Anwendungsfällen schreckliche Konflikte hätte).
* Da ich alles in einem Monad-Transformer implementiere, der MonadIO implementiert, stehen mir traditionelle imperative Hash-Tabellen zur Verfügung.
Hier ist der Algorithmus, mit dem ich das umgesetzt habe. Es ist eine Variation von Brents "Teleporting Turtle" -Algorithmus, modifiziert, um nicht eine lineare Liste von Knoten, sondern einen N-Verzweigungsbaum von Knoten zu behandeln.
(Dies berücksichtigt nicht den tatsächlichen Vergleich. Es wird zwei Kopien des Zustands darunter geben, einen für jede Datenstruktur, der auf Gleichheit getestet wird, und wenn etwas nicht gleichwertig gefunden wird, ist der Vergleich kurz -circuited und false wird zurückgegeben.)
Ich verwalte zwei Stapel, einen Stapel von Knoten, denen ich bei der ersten Traversierung gefolgt vom nächsten Knoten in der gleichen Tiefe und einem aktuellen Tiefenwert gefolgt bin, und einem Stapel von Knoten, die die Schildkröte erreichen soll positioniert sein, bei welcher Aufzeichnung die Tiefe der Schildkröte ist und die Entfernung tiefer als die Schildkröte die nächste Schildkröte sein wird. (In meiner tatsächlichen Implementierung sind die Stapel so vereinheitlicht, dass jeder Stapelrahmen auf ein Paar Knoten und eine Schildkröte zeigt (die auf ein Paar Knoten zeigt), was die Verwaltung der Schildkröten vereinfacht.)
Wenn ich die Tiefe der Datenstruktur zuerst durchquere, baue ich den ersten Stapel auf, und in Intervallen steigender Potenzen von zwei Abständen füge ich neue Rahmen zum Turtle-Stapel hinzu, wo die Turtle auf den aktuellen Knoten zeigt der erste Stapel.
Wenn ich einen Knoten erreiche, an dem ich nicht tiefer gehen kann, weil es noch keine Geschwisterknoten gibt, die noch nicht erreicht sind, steige ich den ersten Stapel ab, bis ich einen Knoten erreiche, der ein nicht geprüftes Geschwister hat, und dann diesen Knoten ersetze mit dem nächsten Geschwisterknoten zu folgen; Wenn es keine Geschwisterknoten mehr gibt, die irgendwo im Stapel folgen können, enden wir mit der Gleichheit von Wahr für den Wert.
Beachten Sie, dass beim Abstieg des ersten Stapels, wenn der obere Teil des ersten Stapels, der abgepickt wird, die gleiche Tiefe (oder den gleichen Knoten) wie der oberste des Turtle-Stapels hat, der obere Teil des Turtle-Stapels entfernt wird.
Wenn nach dem Drücken eines Rahmens auf den ersten Stapel der aktuelle Knoten gleich dem Knoten an der Spitze des Turtle-Stapels ist, trete ich zurück. Der Unterschied in der Tiefe zwischen der Spitze des ersten Stapels und der Oberseite des Turtle-Stapels entspricht der Größe des Zyklus. Ich führe einen vollständigen Zyklus zurück, zeichne jeden Knoten, den ich passiere, und die entsprechenden Stapelzustände und Geschwister auf. Dann teste ich die Knoten in dem Rahmen auf dem ersten Stapel unter dem obersten Rahmen. Wenn sie in den aufgezeichneten Knoten nicht sind, weiß ich, dass der Knoten, bei dem ich bin, der Beginn des Zyklus ist; dann ziehe ich die aufgezeichneten Stapel und Geschwister für diesen Knoten und fahre von dort fort, so dass ich alternative Wege innerhalb des Zyklus nehmen kann (erinnere dich daran, dass es sich um einen N-Verzweigungsbaum handelt) oder sonst aus dem Zyklus absinke. Wenn sie in den aufgezeichneten Knoten sind, aktualisiere ich die aufgezeichneten Knoten so, dass sie die Stapel unter den obersten Rahmen und die Geschwister des aktuellen Knotens enthalten, und öffne dann die Oberseiten der Stapel und fahre fort.
Hier ist mein Code für eine Test-Implementierung des Algorithmus. Der Code sollte jetzt funktionieren.
%Vor%Hier ist eine naive Version des vom Testprogramm verwendeten Algorithmus.
%Vor% Hier ist der Code des Testprogramms. Beachten Sie, dass dies gelegentlich beim Not-Equals-Test fehlschlägt, da es Knotengruppen mit einem signifikanten Grad an Gemeinsamkeit erzeugt, wie von commonPortionRange gesteuert.
Würde Schildkröte und Hase in der Lage sein, das zu beheben?
In einer einzigen Liste ist es trivial. Du lässt den Hasen zweimal so schnell wie die Schildkröte treten und 1 vor dem ersten Element starten. Wenn der Hase jemals mit der Schildkröte übereinstimmt, haben Sie einen Zyklus.
Bei Cons-Zellen ist es im Grunde ein binärer Baum, und Sie können den Baum in einer bestimmten Reihenfolge mit beiden Bäumen überqueren und der Hase folgt dem ersten mit doppelter Geschwindigkeit. Wenn Elemente eq? Sind, Atome nicht-eqv? Du hast die Schaltung geschossen. Wenn Landschildkröte und Hase mit dir zusammenpassen
Tags und Links haskell performance scheme