



















设想下面这张依赖图。A 变了,B 依赖 A 和 C,C 也依赖 A,D 依赖 B 和 C。
A 变化时先通知 B 和 C。B 依赖 A 和 C,可这时 C 还没更新,B 可能先拿旧的 C 算一次。等 C 更新完再通知 B,B 只能重算,第一次的结果白扔了。D 更惨,A 才变了一次,D 可能收到三次更新通知。
办法是按特定顺序更新。先更新 A,通知 B 和 C。B 发现自己还有另一个依赖 C 没动,先等着。C 更新完通知 B 和 D。B 看到两个依赖都就绪,更新,再通知 D。D 最后更新。这样每个节点只更新一次。
要做到这点,算法需要看到整张依赖图,算出最优更新顺序。这个顺序叫 *拓扑排序(topological sort)*。它把图里的节点排成一个线性序列,每个节点在序列中只出现一次,而且排在它所有依赖的后面。比如 B 依赖 A 和 C,那 A 和 C 必须排在 B 前面。这样从头到尾走一遍,每个节点只访问一次,访问它的时候它依赖的节点都已经更新过了。
不过这里有个根本矛盾。push 的价值在于每个节点只需掌握自己的直接依赖者,局部决策容易,全局分析难。系统一旦有了动态依赖(前面说的那种,依赖关系随运行时值变化,比如 IF 条件为真才依赖某个单元格),全局拓扑排序就变得昂贵甚至不可能。
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。