duanhuan8983 2014-12-16 09:11
浏览 43
已采纳

仅计算一次引用公式的算法

i am looking for a nice algorithm to solve the following problem.

I have the following listing of VARIABLES and FORMULAS (result of var is the sum of all formulas):

var1, result=10
  - 5+5=10

var2, result=15
  - var1+5

var3, result=30
  - var1+var2+5

now i am looking for a nice way to calculate all references. if i am changing var1 and the result is 15 now, i have to calculate all referenced to var1. first i came across var2 and recalc var2, if the result of var2 changed i have to recalc all referenced formulas to var2. therefore i would recalc var3 twice (var2 changed, var1 changed)...

is there any solution to not calc var3 twice in this scenario?

thx!

  • 写回答

2条回答 默认 最新

  • drzfnr0275 2014-12-16 09:23
    关注

    Yes, you can ensure you recalculate each variable only once (at most), by using the fact that there are no cyclic dependencies (no way a variable x needs y in order to be calculated, and in the same time y also needs x).

    This is done by modeling the problem as a graph, where all variables are vertices, and a "needed" relation is a directed edge. (So, if variable x "needs" variable y to be calculated, there is an edge (y,x)).

    Now, since the No-Cyclic dependency, this is actually a Directed Acyclic Graph, which you can do topological sort (This can be done only once in pre-processing). Note that it is very possible that in your case, the graph is already sorted, sine it is given as a chronological sequence of events, and the chronological order is a topological sort.

    Do a topological sort on the graph (if needed), and whenever variables are changed:

    Upon variable change:
    1. Mark all changed variables
    2. From first variable to last (according to topological sort), for each variable x:
          2.1. If there is some dependency `(y,x)` on the graph such that `y` is marked:
               2.1.1. mark x
               2.1.2. recalculate x
    

    It is easy to see that each variable is calculated at most once according to this approach.

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
  • ¥15 ubuntu系统下挂载磁盘上执行./提示权限不够
  • ¥15 Arcgis相交分析无法绘制一个或多个图形
  • ¥15 关于#r语言#的问题:差异分析前数据准备,报错Error in data[, sampleName1] : subscript out of bounds请问怎么解决呀以下是全部代码:
  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
  • ¥30 3天&7天&&15天&销量如何统计同一行
  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型