Was ist der beste Ansatz (Algorithmus) kontinuierlich zu berechnen Kaskadierung Beziehungen zwischen Objekten?
-
09-10-2019 - |
Frage
Zum Beispiel A + B = C C + D = E E + F = G wie Änderungen an jeden Knoten aus werden die zugehörigen Knoten neu berechnet. Das Bild unten ist ein einfaches Beispiel dafür, was ich zu tun versuchen.
Eine weitere Klärung Die Struktur für jedes Objekt identisch ist. die Eingänge würden die Preise als jeder Preisänderungen würde es stromabwärts einen Kaskadeneffekt auf die Preise haben. so in dem obigen Beispiel A + B = C 5 würde worden + 6 = 11. etc.
Die Änderungen werden ständig (möglicherweise jede Sekunde), da jeder Wert geändert ich benachrichtigt werden muß (Ereignis gefeuert).
Lösung
Solange Ihr Diagramm nicht verändert, nur die Werte, können Sie eine topologische Sortierung Ihr Diagramms. Dann gehen Sie die Grafik in topologischen Sortierreihenfolge auf den Wert Start (n), die sich geändert. Wenn die Änderungen ein spärlicher Teil des Graphen sein werden, weisen Sie jeden Knoten einen Index in topologischen Sortierreihenfolge und die Verwendung ein Prioritätswarteschlange zu entscheiden, welche Knoten als nächstes zu tun.
Andere Tipps
Der einfachste Weg wäre jsut ein Ereignis basierte Methode. Jeder Knoten verfügt über einen „OnChanged“ Ereignis und etwas, dass Anwendungen, daß der Knoten auf dieses Ereignis abonnieren. Nachdem ein Knoten selbst aktualisiert hat dann hebt es dieses Ereignis und lässt alles andere, das wissen muss.
Wenn Sie Ihre Abhängigkeiten komplexer sind dann müssen Sie etwas anderes haben, um die Updates zu optimieren Dinge zu verwalten. zB wenn eine Wirkung B und C und C auch Effekte B (zB B = A + C und C = A + 1), dann wird ein einfaches Verfahren kann eine aktualisieren, dann b, dann C, dann B wieder. Dies funktioniert aber ist offensichtlich ein mroe Update als erforderlich. Die genaue Art und Weise, das Updates zu optimieren, hängt davon ab, wie komplex Ihr dependancy Baum ist.