我希望你们中的一个人能解决这个问题。
我有一个包含很多对象的数组。数组中的每个对象包含两件事:
- 一个可以改变的值。
- 我的数组中零个或多个其他对象的列表，如果它们的值发生变化，则此对象需要重新计算它的值。这可以从一个对象级联到另一个对象很多次，但是没有依赖关系循环。
我相信这被称为网络(像树一样，但有多个父节点)。具体来说，这是一个有向无环图。
我现在正在做的是:当我改变一个对象的值时，我检查数组中的每个对象，看看它是否依赖于我刚刚改变的对象。如果是，那么我告诉这个子对象重新计算。然后 child 以同样的方式告诉它的 child ，依此类推。
这行得通(值正确更新)，但是当进行广泛而深入的级联更改时，它会非常非常慢。这是因为如果一个对象有多个更改的父对象，它会为每个对象重新计算一次，并且每次都会告诉它的子对象重新计算，所以它们只从一个父对象那里得到几条消息。这会迅速滚雪球，直到许多对象重新计算数十次。
在所有对象的父对象都重新计算之后，只重新计算每个对象一次的最佳方法是什么？
感谢您的帮助。
最佳答案
听起来您想要一个有向无环图的拓扑排序。参见示例 http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Graph/DAG/
如果您的图表不经常变化，您应该能够简单地对其进行一次排序，然后您可以按照从左到右的顺序执行更新，因为知道在每一步中您将添加到的节点集要计算的列表都在当前位置的右侧。有几种方法可以优化它，也许将它们存储在一个简单的堆中，每次都选择最左边的值，重新计算它并添加回它引用的任何节点，或者如其他人所建议的那样，如果完整的依赖关系图足够小，只需按照需要计算的顺序将其存储在每个节点上(使用拓扑排序找到的)。
关于arrays - 相关值网络 - 如何只重新计算一次它们？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6300540/