V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
GrapeCityChina
V2EX  ›  程序员

揭秘你处理数据的“底层逻辑”,详解公式引擎计算(二)

  •  
  •   GrapeCityChina ·
    GrapeCity · 2021-09-22 14:04:19 +08:00 · 529 次点击
    这是一个创建于 1156 天前的主题,其中的信息可能已经有所发展或是发生改变。

    上篇中我们介绍了计算公式引擎的计算原理,本期我们继续带着大家了解在 Excel 表格中公式引擎的实现原理。

    背景

    在上节中解决了基本运算的逻辑之后,在一些实际业务场景中,公式计算并不是单一公式进行的独立运算。我们经常需要将一个很大的运算分解成前后依赖的小运算;同时这些单元格之间的计算会出现很多相互依赖,计算顺序也是要考虑的一个关键问题,我们需要将一系列具有先后顺序的同类运算管理起来依次执行。

    为了实现这种计算关系之间的管理,出现了计算链,用以对公式之间的依赖和先后顺序进行管理,处理在电子表单中错综复杂的依赖。涉及到图的处理,脏值计算等内容。接下来我们将从图计算出发,介绍不同图的计算、按需计算和脏值处理的问题,更加深层次的了解 Excel 表格计算中计算链相关问题。

    计算链

    让我们先从两个表格计算问题出发。

    • 第一种简单情况:

    在这一串计算公式之中,当 C1 赋值为 1 时,A1 的结果为 3 。但此时如果修改 C1 的值,C1=10,此时 B1 的内容还没有修改,A1 依旧是 3,然后 B1=10+1=11,这里就会发现 A1 内容计算出错。

    • 第二种更加复杂一些的情况:

    我们用图的结点表示单元格的计算内容,箭头代表依赖关系。入度为零的节点,完全不依赖其他节点内容,所以计算的顺序应该是从不依赖其他节点的节点内容开始。单元格 A 依赖 F 、E,D 依赖 C 、B,C 、B 又分别依赖 F 、E,唯二不依赖其他节点的内容是 E 、F 。

    这样就得到了一个稳定正确的计算顺序,这个顺序被称之为计算链。在这个例子中计算链是:F,C,E,A,D,B 。

    有向无环图和有向有环图的计算

    在一张图中,如果从一个节点出发,最后能回到这个节点,我们称之为有向有环图,反之被称作有向无环图。

    左图中不论从任意一个节点出发都不能再回到该节点,所以左图是有向无环图。

    右图中 A 点可以出发后回到 A 节点,所以右图是有向有环图。

    我们将计算节点和计算节点之间的关系拆解成有向图后,就可以使用计算有向图的标准方法得到一个可靠的计算链。

    有向无环图的计算

    对于每一个节点存在入度和初度的概念,入度:多少箭头指向当前节点,例如对于 A 节点,入度为 1 ;出度:当前箭头有多箭头指出,例如对于 B 节点,入度为 2 。

    在对有向无环图进行计算的时候,就利用了图中入度作为优先级排序,每次运算入度为 0 的节点,然后移除。

    以上图为例,完整的计算过程如下:

    1.初始化,统计入度:A:1 B:2 C:1 D:2 E:0 F:0

    2. 计算 E 节点,更新入度: A:1 B:2 C:0 D:2 F:0

    3. 计算 F 节点,更新入度: A:1 B:2 C:0 D:1

    4. 计算 C 节点,更新入度: A:1 B:1 D:0

    5. 计算 D 节点,更新入度: A:1 B:0

    6. 计算 B 节点,更新入度: A:0

    7. 计算 A 节点,计算结束有向有环图的计算

    有向有环图的计算

    解决了有向无环图的计算问题,如果此时把上图中 B-C 之间的箭头反向调换,情况就会变的截然不同起来。此时 B-C-D 之间组成了一个环。

    这时候依旧进行计算:

    1. 初始化,统计入度: A:1 B:1 C:2 D:2 E:0 F:0

    2. 计算 E 节点,更新入度: A:1 B:1 C:1 D:2 F:0

    3. 计算 F 节点,更新入度: A:1 B:1 C:1 D:1

    4. 没有入度为 0 的节点,开始迭代计算

    (迭代计算:把上一步的计算结果代入这一步的运算中去,经过多步这样的计算,可以得出一个更为接近的结果。)

    按需计算

    解决这种互相依赖的复杂单元格的运算时,除了图计算还可以采用按需计算的方法。在这里使用到的是 calcOnDemand 这个函数。这个函数的核心工作原理是:压栈并且计算所需要的节点内容,该节点可以是任意内容。

    以该图内容来说明这一计算的过程:这里选择 A 作为我们需要的节点

    1. 压栈并计算 A,需要计算 B 的结果

    2. 压栈并计算 B,需要计算 C 的结果

    3. 压栈并计算 C,需要计算 E 的结果

    4. 压栈并计算 E,E 计算完毕后出栈

    5. 计算 C,C 计算完毕后出栈

    6. 计算 B,还需要计算 D 的结果

    7. 压栈并计算 D,拿到 C 的结果,还需要 F 的结果

    8. 压栈并计算 F,F 计算完毕后出栈

    9. 计算 D,D 计算完毕后出栈

    10. 计算 B,B 计算完毕后出栈

    11. 计算 A,A 计算完毕后出栈

    12. 栈空,计算完毕

    这个例子取了最复杂的 A 作为需求节点,如果需要 D 节点,变为 D 节点入栈,C 节点入栈,E 节点入栈,计算后出栈,C 节点计算后出栈,F 节点入栈计算后出栈,D 节点入栈,这样就得到了正确的 D 的值,这种运算方式只计算需要的内容。

    图计算 VS 按需计算

    在这里对图计算和按需计算做一个对别,这两种算法在不同情况下效率不同。

    左图中是一个从上到下的累加,使用按需计算计算的很顺畅,从上向下按顺序计算即可,堆栈中存在的待计算元素不超过两个,按需计算比图的计算更加快。

    右图中是是一个逆向计算,上一行单元格的内容依赖下一行单元格的内容,按需计算需要计算 1000 步,这时按需计算会比图计算慢很多。

    总体来说,图计算比按需计算更加稳定,而按需计算在不同情况下会有不同的表现,实际使用中我们可以根据具体的使用场景采用不同的计算策略。

    脏值计算

    在这个图中,如果此时修改了某节点的值,这个时候就需要根据传播途径,标记所有需要重算的节点。

    举例:修改了 E 的内容

    1. 根据传播依次将 E C B D A 标记

    2. 删去未标记的节点

    3. 开始计算剩余的节点

    标记完成之后,我们就不再需要关注未标记节点,计算完成。

    整个过程如下图所示:

    拓展:关于运算内容几个问题

    已经介绍完计算链的全部内容,为了帮助大家更好地理解,这里有几个思考问题:

    1. 示例中的图计算,可否可改用按需计算?

    2. 可不可以先计算 E 的值,再标记并重算 C B D A?

    3. 根据传播途径标记需要重算节点的优势?

    解答部分:

    1. 该图可以进行按需计算,因为按需计算和图计算都可以对图内容进行正确计算。

    2. 该图中不可以先算 E,然后重标 CBDA,因为一旦我们一但先计算 E,此时 C 依旧依赖 E 的内容,而 C 又不能先于 E 计算,这时 ABCD 节点数值都会变得不可靠,这个计算引用链就会被完全破坏。

    3. 脏数据的处理中只对传播路径上的节点进行处理,在实际应用场景下,几百个单元格数据处理使,可以大大减少运算的内容。

    总结

    所有的单元格计算内容就全部为大家介绍完毕了,我们一起回顾一下本章节内容:计算链就是将一个个单元格计算串联起来,分为普通计算和迭代计算。而这里我们介绍了两种不同的计算方式——图计算和按需计算,在面对不同情需要选择采用不同的计算策略。计算链在整个计算过程中不像单元格的计算那么明显,但是却比单元格的计算更加复杂。

    在了解了计算公式如何进行词法、语法分析对公式进行快速运算,计算链是如何进行多单元格大数据量的处理,接下来将继续为大家介绍异步函数在前后算计算中的花式用法。

    看到这里了点个赞吧~后续本葡萄也会为大家带来更多严肃或有趣的内容。

    转载请注明出处:葡萄城官网,葡萄城为开发者提供专业的开发工具、解决方案和服务,赋能开发者。

    目前尚无回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2424 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 16:04 · PVG 00:04 · LAX 08:04 · JFK 11:04
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.