我希望你们其中一个人可以解决这个问题.
我有一个包含大量对象的数组.数组中的每个对象都包含两件事：
>可以改变的值.
>我的数组中零个或多个其他对象的列表,如果它们的值发生更改,则此对象需要重新计算其值.这可以从对象级联多次,但是没有依赖的循环.
我相信这被称为网络(就像一棵树,但有多个父母).具体来说,这是一个有向无环图.
我现在正在做的是：当我更改对象的值时,我会检查数组中的每个对象,看它是否取决于我刚刚更改的对象.如果是,那么我告诉这个子对象重新计算.然后孩子以同样的方式告诉孩子,依此类推.
这可以正常工作(值正确更新),但是当进行更深和更深的更改时,它会非常慢.这是因为如果一个对象有许多父改变,它会为每一个重新计算,并且还告诉它的孩子每次重新计算,因此他们只从一个父级获得几条消息.这很快就会滚雪球,直到许多物体重新计算了数十次.
只有重新计算每个对象一次后才能重新计算的最佳方法是什么？
谢谢你的帮助.
解决方法
听起来你想要一个有向无环图的拓扑排序.参见例如
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Graph/DAG/
如果您的图表没有经常更改,您应该能够简单地对其进行一次排序,从那时起,您可以按从左到右的顺序执行更新,因为知道在每一步中您将添加到列表中的节点集是计算全部在当前位置的右侧.有几种方法可以优化它,可以将它们存储在一个简单的堆中,每次选择最左边的值,重新计算它并添加它引用的任何节点,或者如同其他人建议的那样,如果完全依赖图足够小,只需按照需要计算的顺序将其存储在每个节点上(使用拓扑排序).
