Wie halten wir abhängige Datenstrukturen auf dem neuesten Stand?

Angenommen, Sie haben einen Analysebaum, einen abstrakten Syntaxbaum und ein Kontrollflussdiagramm, die jeweils logisch von dem vorherigen abgeleitet sind. Im Prinzip ist es einfach, jedes Diagramm anhand des Analysebaums zu erstellen. Wie können wir jedoch die Komplexität der Aktualisierung der Diagramme verwalten, wenn der Analysebaum geändert wird? Wir wissen genau, wie der Baum geändert wurde, aber wie kann die Änderung auf eine Weise auf die anderen Bäume übertragen werden, die nicht schwierig zu verwalten ist?

Natürlich kann das abhängige Diagramm aktualisiert werden, indem es jedes Mal, wenn sich das erste Diagramm ändert, einfach von Grund auf neu rekonstruiert wird. Dann gibt es jedoch keine Möglichkeit, die Details der Änderungen im abhängigen Diagramm zu kennen.

Ich habe derzeit vier Möglichkeiten, um dieses Problem zu lösen, aber jede hat Schwierigkeiten.

1. Knoten des abhängigen Baums beobachten jeweils die relevanten Knoten des ursprünglichen Baums und aktualisieren sich selbst und die Beobachterlisten der ursprünglichen Baumknoten nach Bedarf. Die konzeptionelle Komplexität kann entmutigend werden.
2. Jeder Knoten des ursprünglichen Baums verfügt über eine Liste der abhängigen Baumknoten, die speziell von ihm abhängen. Wenn sich der Knoten ändert, setzt er ein Flag auf die abhängigen Knoten, um sie als fehlerhaft zu markieren, einschließlich der Eltern der abhängigen Knoten ganz unten zur Wurzel. Nach jeder Änderung führen wir einen Algorithmus aus, der dem Algorithmus zum Erstellen des abhängigen Graphen von Grund auf ähnlich ist. Er überspringt jedoch jeden sauberen Knoten und rekonstruiert jeden schmutzigen Knoten, wobei verfolgt wird, ob sich der rekonstruierte Knoten tatsächlich vom schmutzigen Knoten unterscheidet. Dies kann auch schwierig werden.
3. Wir können die logische Verbindung zwischen dem ursprünglichen Diagramm und dem abhängigen Diagramm als Datenstruktur darstellen, wie eine Liste von Einschränkungen, die möglicherweise in einer deklarativen Sprache entworfen wurden. Wenn sich das ursprüngliche Diagramm ändert, müssen wir nur die Liste scannen, um festzustellen, welche Einschränkungen verletzt werden und wie sich der abhängige Baum ändern muss, um die Verletzung zu korrigieren. Alle Daten werden als Daten codiert.
4. Wir können das abhängige Diagramm von Grund auf neu rekonstruieren, als gäbe es kein vorhandenes abhängiges Diagramm, und dann das vorhandene Diagramm und das neue Diagramm vergleichen, um festzustellen, wie es sich geändert hat. Ich bin mir sicher, dass dies der einfachste Weg ist, da ich weiß, dass Algorithmen zum Erkennen von Unterschieden verfügbar sind, aber alle sind recht rechenintensiv und im Prinzip scheint dies unnötig zu sein, sodass ich diese Option absichtlich vermeide.

Was ist der richtige Weg, um mit solchen Problemen umzugehen? Sicherlich muss es ein Designmuster geben, das das Ganze fast einfach macht. Es wäre schön, für jedes Problem dieser allgemeinen Beschreibung eine gute Lösung zu haben. Hat diese Problemklasse einen Namen?

Lassen Sie mich auf die Probleme eingehen, die dieses Problem verursacht. Dieses Problem tritt an verschiedenen Stellen auf, wenn zwei Teile eines Projekts mit Diagrammen arbeiten, wobei jedes Diagramm eine andere Darstellung derselben Änderung darstellt, die sich während der Ausführung der Software ändert. Es ist wie beim Erstellen eines Adapters für eine Schnittstelle, aber anstatt ein einzelnes Objekt oder eine feste Anzahl von Objekten zu verpacken, müssen wir ein ganzes Diagramm beliebiger Größe umbrechen.

Jedes Mal, wenn ich das versuche, bekomme ich ein verwirrendes, nicht zu wartendes Durcheinander. Der Kontrollfluss von Beobachtern kann schwierig zu verfolgen sein, wenn er kompliziert wird, und der Algorithmus zum Konvertieren eines Graphen in einen anderen ist normalerweise schwierig genug, um zu folgen, wenn er klar angelegt und nicht über mehrere Klassen verteilt ist. Das Problem ist, dass es anscheinend keine Möglichkeit gibt, nur einen einfachen, unkomplizierten Graphkonvertierungsalgorithmus zu verwenden, wenn sich der ursprüngliche Graph ändert.

Natürlich können wir einen gewöhnlichen Graphkonvertierungsalgorithmus nicht direkt verwenden, da dieser nicht anders als von vorne anfangen auf Änderungen reagieren kann. Welche Alternativen gibt es also? Möglicherweise könnte der Algorithmus in einem Continuation-Passing-Stil geschrieben werden, bei dem jeder Schritt des Algorithmus als Objekt mit einer Methode für jeden Knotentyp im Originaldiagramm dargestellt wird, wie ein Besucher. Dann kann der Algorithmus zusammengestellt werden, indem verschiedene einfache Besucher zusammengesetzt werden.

Ein weiteres Beispiel: Angenommen, Sie haben eine GUI, die wie in Java Swing mit JPanels und Layout-Managern angelegt ist. Sie können diesen Prozess vereinfachen, indem Sie verschachtelte JPanels anstelle komplexer Layout-Manager verwenden. So erhalten Sie einen Baum mit verschiedenen Containern, der Knoten enthält, die nur für Layoutzwecke vorhanden und ansonsten bedeutungslos sind. Angenommen, derselbe Baum, der zum Generieren Ihrer GUI verwendet wird, wird auch in einem anderen Teil Ihrer Anwendung verwendet. Anstatt den Baum grafisch darzustellen, arbeitet er mit einer Bibliothek, die einen abstrakten Repräsentationsbaum als Ordnersystem generiert. Um diese Bibliothek verwenden zu können, benötigen wir eine Version des Baums, die nicht über die Layoutknoten verfügt. Die Layoutknoten müssen in ihre übergeordneten Knoten abgeflacht werden.

Eine andere Sichtweise: Das Konzept, mit veränderlichen Bäumen zu arbeiten, verstößt gegen das Gesetz von Demeter . Es wäre nicht wirklich ein Verstoß gegen das Gesetz, wenn der Baum ein Wert wäre, wie es Analysebäume und Syntaxbäume normalerweise sind, aber in diesem Fall wäre dies kein Problem, da nichts auf dem neuesten Stand gehalten werden müsste. Dieses Problem besteht also als direkte Folge eines Verstoßes gegen das Demeter-Gesetz. Wie können Sie dies jedoch generell vermeiden, wenn es in Ihrer Domain anscheinend darum geht, Bäume oder Grafiken zu manipulieren?

Das zusammengesetzte Muster ist ein wunderbares Werkzeug, um ein Diagramm in ein einzelnes Objekt zu verwandeln und das Gesetz von Demeter zu befolgen. Ist es möglich, das zusammengesetzte Muster zu verwenden, um eine Baumart effektiv in eine andere zu verwandeln? Können Sie einen zusammengesetzten Analysebaum so erstellen, dass er sich wie ein abstrakter Syntaxbaum und sogar wie ein Kontrollflussdiagramm verhält? Gibt es eine Möglichkeit, dies zu tun, ohne das Prinzip der Einzelverantwortung zu verletzen ? Das zusammengesetzte Muster führt dazu, dass Klassen jede Verantwortung übernehmen, die sie berühren, aber vielleicht könnte es irgendwie mit dem Strategiemuster kombiniert werden .

Ich denke, Ihre Szenarien diskutieren Variationen des Beobachtermusters . Jeder ursprüngliche Knoten (" Subjekt ") hat (mindestens) die folgenden zwei Methoden:

• registerObserver(observer) - fügt der Liste der Beobachter einen abhängigen Knoten hinzu.
• notifyObservers()- ruft x.notify(this)jeden Beobachter auf

Und jeder abhängige Knoten (" Beobachter ") hat eine notify(original)Methode. Vergleichen Sie Ihre Szenarien:

1. Die notifyMethode erstellt sofort einen abhängigen Teilbaum neu.
2. Die notifyMethode setzt ein Flag, die Neuberechnung erfolgt nach jedem Satz von Aktualisierungen.
3. Die notifyObserversMethode ist intelligent und benachrichtigt nur diejenigen Beobachter, deren Einschränkungen ungültig sind. Dies würde wahrscheinlich das Besuchermuster verwenden , damit die abhängigen Knoten eine Methode anbieten können, die dies entscheidet.
4. (Dieses Muster hat nichts mit dem Wiederaufbau von Brute-Force zu tun.)

Da die ersten drei Ideen nur Variationen des Beobachtermusters sind, wird ihr Design eine ähnliche Komplexität aufweisen (zufällig werden sie tatsächlich in zunehmender Komplexität geordnet - ich denke, I'd1 ist am einfachsten zu implementieren).

Ich kann mir eine Verbesserung vorstellen: die abhängigen Bäume träge bauen . Jeder abhängige Knoten hätte dann ein boolesches Flag, das entweder auf validoder gesetzt ist invalid. Jede Zugriffsmethode würde dieses Flag überprüfen und gegebenenfalls den Teilbaum neu berechnen. Der Unterschied zu №2 besteht darin, dass die Neuberechnung beim Zugriff und nicht bei Änderungen erfolgt. Dies würde wahrscheinlich zu den wenigsten Berechnungen führen, kann jedoch zu erheblichen Schwierigkeiten führen, wenn sich der Typ eines Knotens beim Zugriff ändern müsste.

Ich möchte auch die Notwendigkeit mehrerer abhängiger Bäume in Frage stellen. Zum Beispiel strukturiere ich meine Parser immer so, dass sie sofort einen AST ausgeben. Informationen, die nur während der Erstellung dieses Baums relevant sind, müssen nicht in einer permanenten Datenstruktur gespeichert werden. Ebenso können Sie Ihre Objekte so auswählen, dass der AST als Kontrollflussdiagramm interpretiert wird.

Für ein Beispiel aus der Praxis führt der Compilerteil im perlInterpreter Folgendes aus: Der AST wird von unten nach oben erstellt, wobei einige Knoten konstant weggefaltet werden. In einem zweiten Durchlauf werden die Knoten in Ausführungsreihenfolge verbunden, wobei einige Knoten durch Optimierungen übersprungen werden. Das Ergebnis ist eine sehr schnelle Analyse (und wenige Zuordnungen), aber nur sehr begrenzte Optimierungen. Es sollte beachtet werden, dass ein solches Design zwar möglich ist , aber wahrscheinlich nicht angestrebt werden sollte: Es ist einberechneter Kompromiss vollständiger Verstoß gegen das Prinzip der Einzelverantwortung .

Wenn Sie tatsächlich mehrere Bäume benötigen, sollten Sie auch überlegen, ob diese wirklich gleichzeitig gebaut werden müssen. In den meisten Fällen ist ein Analysebaum nach der Analyse konstant. Ebenso wird ein AST wahrscheinlich konstant bleiben, nachdem Makros aufgelöst und Optimierungen auf AST-Ebene ausgeführt wurden.

Sie scheinen an einen allgemeinen Fall von 2 Graphen zu denken, bei dem der zweite vollständig vom ersten abgeleitet werden kann, und Sie möchten den zweiten Graphen effizient neu berechnen, wenn sich ein Teil des ersten ändert.

Dies scheint konzeptionell nicht anders zu sein als das Problem der Minimierung der Neuberechnung nur im ersten Diagramm, obwohl ich annehme, dass es sich bei der Implementierung in einem bestimmten System wahrscheinlich um unterschiedliche Typen in jedem Diagramm handelt.

Es geht so ziemlich darum, Abhängigkeiten sowohl innerhalb als auch zwischen Diagrammen zu verfolgen. Aktualisieren Sie für jeden geänderten Knoten alle abhängigen Knoten rekursiv.

Bevor Sie Aktualisierungen vornehmen, möchten Sie natürlich Ihr Abhängigkeitsdiagramm topologisch sortieren. Auf diese Weise wissen Sie, ob Sie kreisförmige Abhängigkeiten haben, die eine potenziell unendliche Welle von Aktualisierungen erzeugen, und stellen außerdem sicher, dass Sie für jeden Knoten alle seine abhängigen Elemente aktualisieren, bevor Sie diesen Knoten aktualisieren. Auf diese Weise wird eine sinnlose Berechnung vermieden, die später wiederholt werden muss.

Sie müssen die Abhängigkeiten nicht besonders in einer deklarativen Sprache ausdrücken, aber Sie können, das ist ein völlig unabhängiges Problem.

Dies ist ein allgemeiner Algorithmus, und in bestimmten Fällen können Sie möglicherweise mehr tun, um ihn zu beschleunigen. Es kann sein, dass ein Teil der Arbeit, die Sie zum Aktualisieren einer Abhängigkeit ausführen, auch zum Aktualisieren anderer Abhängigkeiten nützlich ist, und ein guter Algorithmus würde dies ausnutzen.

Soweit der Graphkonvertierungsalgorithmus ein nicht zu wartendes Durcheinander ist, ist die Lösung etwas sprachspezifisch, aber ein objektorientierter Ansatz könnte darin bestehen, einige Klassen zu haben, die sich ausschließlich mit der Aktualisierung von Abhängigkeiten im Allgemeinen befassen - Abhängigkeiten darstellen, eine topologische Sortierung durchführen und Berechnungen auslösen . Um die Berechnung durchzuführen, delegieren sie an Ihre tatsächlichen Klassen, möglicherweise mithilfe einer erstklassigen Funktion, die ihnen beim Erstellen übergeben wurde, möglicherweise weil die Klassen, an die sie übergeben, eine Schnittstelle implementieren müssen (wie üblich, wenn sie dies nicht können, z Beispiel, Sie haben sie nicht erstellt, Sie können einen Adapter verwenden). Ich nehme an, in einigen Fällen könnten Sie Reflexion verwenden, um die Diagramminformationen aus dem Diagramm der Objektbeziehungen zu sammeln und die Methoden auf diese Weise aufzurufen, wenn dies einfacher einzurichten ist und Sie dies nicht tun.

Sie haben erwähnt, dass Sie genau wissen, wie der Baum geändert wurde. Würden Sie wissen, wann?

Wie wäre es das Experimentieren mit HashTrees oder Hash - Ketten ( Merkle - Baum ) oder allgemein das Konzept der Fehlererkennung . Wenn die Bäume riesig sind, können Sie beispielsweise das erste Diagramm in N / 2- oder Root-N-Zonen unterteilen und diesen Zonen Hashes / Prüfsummen zuweisen. Die abhängigen Bäume würden ihren eigenen Satz von N / 2- oder Wurzel-N-Zonen beibehalten, die von den Zonen der ersten Bäume abhängig sind. Wenn im ersten Baum Änderungen festgestellt werden, aktualisieren Sie die entsprechenden Knoten im abhängigen Baum mithilfe einer einfachen Suche (da Sie wissen, was sich geändert hat, und anschließend den Hash / die Prüfsumme für diese Zone).

Eine weitere Darstellung des Problems - Sie haben einige Daten (Grafik) und verschiedene Darstellungen davon (z. B. Layoutfelder / Baumansicht). Sie möchten sicher sein, dass jede Darstellung mit anderen Darstellungen übereinstimmt.

Warum versuchen Sie nicht, die grundlegendste Darstellung zu finden und sich gegenseitig in eine grundlegende Darstellung umzuwandeln? Dann reicht es aus, die grundlegende zu ändern, und die Ansichten bleiben erhalten.

Ein Beispiel für ein Layout: Die erste Darstellung lautet beispielsweise:

panelA(
    panelB(
        panelC(
            widget1
            widget2
        )
        panelD(
            widget3
        )
    )
    widget4
)

Sie wenden sich also einer "einfacheren" Darstellung zu, einer Liste der folgenden Tupel:

[
    (panelA, panelB, panelC, widget1),
    (panelA, panelB, panelC, widget2),
    (panelA, panelB, panelD, widget3),
    (panelA, widget4),
]

Wenn Sie dieses Diagramm mit Swing verwenden, erstellen Sie eine Ansicht, die die Darstellung oben in einen speziellen Baum umwandelt. Bei Verwendung mit der Baumansicht haben Sie eine Ansicht, die nur die Liste der letzten Elemente des Tupels zurückgibt.

Was bedeutet "einfach" oder "grundlegend"? Am wichtigsten ist, dass es einfach sein muss, sich einer Ansicht zuzuwenden (damit das Berechnen jeder Ansicht billig ist). Außerdem muss es von jeder Ansicht aus leicht zu ändern sein.

Nehmen wir an, wir möchten diese Struktur jetzt mithilfe der Layoutansicht ändern. Der Aufruf "panelC.parent = panelD" muss übersetzt werden, um "eine Liste mit panelD zu finden, alle Listen zu finden, die panelC enthalten, alle Elemente dieser Liste zu ersetzen, die vor panelC stehen, und einen Teil der ersten Liste vor panelD". .

Wie andere Leute betonten - Beobachter kann nützlich sein.

Wenn es sich um Analysebäume / AST / Kontrollflussdiagramme handelt, müssen wir keine Ansicht benachrichtigen, die das Diagramm geändert hat, da Sie es bei Verwendung überprüfen und bei der Überprüfung die "grundlegende" Darstellung dynamisch in die Ansichtsdarstellung umwandeln.

Wenn wir über Swing sprechen, muss der Wechsel zu einer Ansicht in anderen Ansichten benachrichtigt werden, damit sich für den Benutzer Änderungen ändern können.

Am Ende - das ist eine sehr fallspezifische Frage. Ich würde sagen, dass sich die vollständige Lösung stark unterscheidet, wenn Sie sie für das Layout und für die Sprachanalyse verwenden, und dass eine vollständig generische Lösung höllisch hässlich und teuer sein wird.

PS. Die obige Darstellung ist hässlich, ad-hoc erstellt usw. Sie soll nur das Konzept zeigen, nicht die reale Lösung.