如何重新计算电子表格

假设我正在为我的两个朋友在泽西城排队时点玉米煎饼，并想要计算我点的总价：

在这样编写的电子表格中跟踪数据流有点令人困惑，所以我希望您不介意将其表示为图形的等价图：

我们把El Farolito超级素食玉米煎饼的价格四舍五入到8美元，所以假设每个玉米煎饼的送货费用仍然只有2美元，那么我们两个玉米煎饼的总价看起来将是20美元。

哦，不，我完全忘了！我的一个朋友喜欢一次狼吞虎咽地吃下多个玉米煎饼，所以我真的想点三个玉米煎饼。如果我更新num Burritos，一个幼稚的电子表格引擎可能会重新计算整个文档，首先重新计算没有输入的单元格，然后重新计算输入准备就绪的任何单元格，直到我们完成每个单元格。在本例中，我们首先计算玉米煎饼价格和玉米煎饼数量，然后计算玉米煎饼价格w船，然后计算新的最终总计30美元。

这种简单的重新计算整个文档的策略听起来可能很浪费，但实际上已经比VisiCalc更好了。VisiCalc是有史以来第一款电子表格软件，也是第一款所谓的“杀手级应用”，负责推广Apple II。VisiCalc会从左到右、从上到下反复重新计算单元格，一遍又一遍地扫描，直到它们都没有改变。尽管有这种“有趣”的算法，VisiCalc在四年的时间里仍然是占主导地位的电子表格软件。它的统治在1983年结束，当时莲花1-2-3以“自然顺序重新计算”席卷市场，正如Tracy Robnett Licklider在Byte Magazine中所描述的那样：

Lotus1-2-3利用了自然顺序重新计算，尽管它也支持VisiCalc的行顺序和列顺序模式。自然顺序重新计算维护了一个单元格依赖列表，并在重新计算依赖于该单元格的单元格之前重新计算该单元格。

Lotus1-2-3实现了我们上面展示的“重新计算所有内容”策略，对于电子表格的第一个十年来说，这已经是最好的结果了。是的，我们重新计算文档中的每个单元格，但至少我们只重新计算每个单元格一次。

很好，标题2。在我的三个玉米煎饼例子中，没有理由重新计算玉米煎饼的价格，因为改变我们订购的玉米煎饼的数量不可能影响每个玉米煎饼的价格。1989年，莲花的一个竞争对手意识到了这一点，于是创造了SuperCalc5，大概是根据该算法核心的超级玉米煎饼理论命名的。SuperCalc5重新计算了“只有细胞依赖于改变的细胞”，这使得玉米煎饼的更新数量看起来更像这样：

通过只在单元格的一个输入发生变化时更新单元格，我们可以避免重新计算玉米煎饼价格w Ship。在这种情况下，它只节省了一次添加，但在较大的电子表格中，它可以节省相当多的时间！不幸的是，我们现在有了另一个问题。比方说，我的朋友现在想要肉玉米煎饼，价格高出一美元，同时El Farolito还增加了每单2美元的费用，无论你点了多少玉米煎饼。在重新计算任何公式输出之前，我们的图表可能如下所示：

因为这里有两个更新的单元格，所以我们有问题。我们应该先重新计算玉米煎饼价格，还是总价？理想情况下，我们首先计算玉米煎饼价格，注意它的产量发生了变化，然后重新计算玉米煎饼价格w船，最后重新计算总价格。然而，如果我们首先重新计算Total，那么一旦新的9美元玉米煎饼价格向下传播，我们将不得不重新计算它。如果我们没有按正确的顺序计算单元格，这个算法并不比重新计算整个文档更好。在某些情况下，它的速度和VisiCalc一样慢！

显然，找出更新细胞的正确顺序对我们来说很重要。大体上，这个问题有两种解决方案：脏标记和拓扑排序。

第一个解决方案涉及将编辑下游的所有单元格标记为脏。例如，当我们更新Burrito Price时，甚至在执行任何重新计算之前，我们都会将下游单元格Burrito Price w Ship和Total标记为脏：

然后，在循环中，我们找到一个没有脏输入的脏单元格，并重新计算它。当没有肮脏的牢房时，我们就完了！这解决了我们的排序问题。不过，这也有一个缺点--如果重新计算了一个单元格，而我们发现它的新输出与之前的输出相同，那么我们仍然会重新计算下游的单元格！在这种情况下，稍微增加一点逻辑就可以避免实际运行公式的麻烦，但不幸的是，我们仍然浪费时间将许多单元格标记和取消标记为脏的。

第二种解决方案是拓扑排序。如果单元格没有输入，我们将其高度标记为0。如果单元格有输入，我们将其高度标记为其输入高度的最大值加1。这确保了所有单元格的高度都大于它们的任何输入，因此我们只跟踪输入发生更改的所有单元格，始终首先选择高度最低的单元格进行重新计算：

在我们的双重更新示例中，Burrito Price和Total最初将被添加到重新计算堆中。玉米煎饼价格较低，将首先重新计算。由于它的输出发生了变化，因此我们将把Burrito Price w Ship添加到重新计算堆中，并且由于它的高度也小于Total，因此在我们最终重新计算Total之前将重新计算它。

与第一种解决方案相比，这有一个很大的优势：任何细胞都不会被标记为脏的，除非它的一个输入确实发生了变化。但是，它要求我们将所有等待重新计算的单元格按排序顺序保存。如果我们使用堆，这将导致O(Nlogn)减慢，因此在最坏的情况下，比Lotus 1-2-3的重新计算一切的策略渐近慢。

现代的Excel使用脏标记和拓扑排序的组合，你可以在他们的文档中阅读更多关于这一点的内容。

我们现在或多或少已经达到了现代电子表格重新计算中使用的算法。不幸的是，我怀疑基本上没有任何商业理由可以继续改进它。有“我的Excel电子表格太慢”问题的少数人已经编写了足够多的Excel公式，以至于不可能移植到任何其他平台。幸运的是，我对商业一无所知，所以我们无论如何都要考虑进一步的改进。

除了缓存之外，电子表格样式的计算图的一个很酷的方面是，我们只能计算我们感兴趣的单元格。这有时被称为懒惰计算，或需求驱动计算。作为一个更具体的例子，这里有一个略微扩展的玉米煎饼电子表格图表。这个示例与前面的相同，但是我们添加了最恰当的描述为“salsa计算”。每个墨西哥玉米煎饼含有40克萨尔萨酱，我们进行快速乘法，以知道我们整个订单中有多少萨尔萨酱。在这种情况下，因为我们点的是三个玉米煎饼，所以我们整个订单总共有120克辣酱。

当然，精明的读者可能已经在这里发现了问题：知道一份订单中萨尔萨的总重量是一个相当无用的衡量标准。谁会在乎它有120克呢？我该怎么处理这些信息？？不幸的是，一个常规的电子表格会浪费按顺序计算Salsa的周期，即使我们不希望它在大部分时间内重新计算。

这就是需求驱动的重新计算可以提供帮助的地方。如果我们能以某种方式指定我们只对Total的输出感兴趣，那么我们只能重新计算该单元格及其依赖项，并跳过按顺序触及Salsa和按玉米煎饼触及Salsa。让我们称Total为观察到的单元格，因为我们试图查看它的输出。我们也可以称Total及其三个依赖项为必需单元，因为它们是计算某些观察到的单元所必需的。顺序沙拉和玉米煎饼沙拉恰如其分地被描述为不必要的。

Rust团队中的一些人创建了Salsa框架来解决这个问题，显然是根据他们的计算机浪费周期进行的不必要的Salsa计算来命名的。萨尔萨舞真的很酷，我相信他们能比我解释得更好。粗略地说，他们使用修订号来跟踪单元格是否需要重新计算。公式或输入的任何变化都会增加全局修订号，每个单元格都会跟踪两个修订：verized_at跟踪其输出上一次更新的修订，Changed_at跟踪其输出上一次实际更改的修订。

当用户表示他们想要一个新的Total值时，我们首先递归地重新计算Total所需的任何单元格，如果单元格的LAST_UPDATED修订版等于全局修订版，则跳过该单元格。一旦Total的相关性是最新的，如果Burrito Price w Ship或Num Burrito的Changed_at版本大于Total的VERIFIED_AT版本，我们只会重新运行Total中的实际公式。这对于SASA在锈蚀分析仪中的用途非常有用，因为简单很重要，每个细胞都需要大量的时间来计算。然而，我们可以从上面的玉米煎饼图表中看到缺点--如果每个玉米煎饼的萨尔萨不断变化，我们的全球修订号将频繁上升。这将使道达尔的每一次观察都走到它所必需的三个细胞中，即使这些细胞实际上都没有改变。不会重新计算公式，但如果图表很大，重复遍历一个单元格的所有依赖项可能会很昂贵。

与其为需求驱动的电子表格发明新的算法，不如借鉴前面提到的两种经典电子表格算法：脏标记和拓扑排序。正如你可能想象的那样，需求驱动的模式使这两种模式都变得复杂，但这两种模式仍然可行。

让我们先来看看肮脏的标记。与以前一样，当我们更改单元格的公式时，我们将所有下游单元格标记为脏。因此，如果我们按玉米煎饼更新Salsa，它将如下所示：

然而，我们并不是立即重新计算所有脏的细胞，而是等待用户观察一个细胞。然后，我们在观察到的单元格上运行Salsa的算法，但不是用过时的VERIFIED_AT修订号来验证依赖关系，而是只验证标记为脏的单元格。这是Adapton使用的技术。您会注意到，当我们观察Total时，我们会发现它并不脏，因此我们可以跳过Salsa执行的图形遍历！

如果我们决定按顺序观察Salsa，我们会发现它被标记为脏的，因此我们将重新检查并重新计算每玉米煎饼的Salsa和按顺序计算的Salsa。即使在这里，只使用修订号也有好处，因为我们可以跳过在仍然干净的Num Burritos单元格上的递归遍历。

当我们试图观察的一组细胞频繁变化时，需求驱动的脏标记表现出惊人的效果。不幸的是，这与以前的脏标记算法有相同的缺点。如果一个包含许多下游单元的单元发生变化，我们可能会浪费大量时间来标记和取消标记为脏的单元，即使当我们重新计算它们时，它们的输入实际上并没有改变。在最坏的情况下，每一次更改都会导致我们将整个图标记为脏的，这将给我们带来与Salsa算法相同的~数量级的性能。

除了肮脏的标记，我们还可以调整拓扑排序以适应需求驱动的计算。这是Jane Street的增量图书馆使用的技术，需要一些重要技巧才能正确使用。在添加需求驱动的计算之前，我们的拓扑排序算法使用堆来确定下一步将重新计算哪个单元。但现在，我们只想重新计算必要的单元格。多么?。我们不想从Adapton这样的观察到的单元遍历整棵树，因为完整的树遍历违背了拓扑排序的全部目的，并且会给出与Adapton类似的性能特征。

相反，增量维护一组用户已标记为观察到的单元格，以及任何观察到的单元格所必需的一组单元格。每当单元格被标记为观察到或未观察到时，增量遍历该单元格的依赖项以确保正确应用必要的标记。然后，我们只在单元格被标记为必需时才将其添加到重新计算堆中。在我们的玉米煎饼图中，如果只有Total是观察集的一部分，则按顺序更改Salsa不会导致图的任何遍历，因为只重新计算必要的单元格：

这解决了我们的问题，而无需急于遍历图表将单元格标记为脏！我们仍然必须记住，每玉米煎饼的萨尔萨是肮脏的，因为如果以后有必要的话，我们将需要重新计算它。但与Adapton的算法不同的是，我们不需要在整个图表中压下这个单一的污点。

Adapton和Incremental都在图中走动，即使不重新计算单元。当观察到的单元格集合改变时，增量遍历图形的上游，而当公式改变时，Adapton遍历图形的下游。使用这些小图表，可能不会立即看出这种图表遍历是昂贵的。但是，如果您的图表很大，而单元格的计算成本相对较低(通常是电子表格的情况)，您会发现大部分成本来自浪费的图表遍历！当电池价格便宜时，在电池上打上一点记号的成本与从零开始重新计算电池的成本大致相同。因此，理想情况下，如果我们希望我们的算法比从头开始计算的速度快得多，我们必须尽可能避免不必要的遍历图形。

我越是思考这个问题，就越是意识到他们浪费时间在大相径庭的情况下走马观花。在我们的玉米煎饼图中，让我们设想细胞公式几乎不会改变，但我们会在首先观察Total，然后按顺序观察Salsa之间快速切换。

在这种情况下，Adapton将永远不会在树上行走。没有任何输入会改变，因此我们永远不需要将任何东西标记为脏的。因为没有东西是脏的，所以每个观察也很便宜，因为我们只需从干净的单元格立即返回缓存值。但是，在本例中，增量的性能很差。即使不重新计算任何值，增量也会反复标记和取消标记许多必要和不必要的单元格。

在相反的情况下，让我们想象一个图表，其中我们的公式正在迅速改变，但我们没有改变我们正在观察的细胞。例如，我们可以想象我们正在观察Total，同时将玉米煎饼价格从4+4快速调整为2*4。

就像前面的例子一样，我们并没有真正重新计算很多单元。4+4和2*4都等于8，所以理想情况下，当用户进行此更改时，我们只重新计算一位算术。然而，与前一个示例不同的是，增量现在是避免树遍历的库。使用Incremental，我们缓存了这样一个事实，即Burrito Price是一个必要的单元格，因此当它发生变化时，我们可以重新计算它，而不需要遍历图表。使用Adapton，我们浪费时间将Burrito Price w Ship和Total标记为脏，即使Burrito Price的输出不会改变。

考虑到每种算法在彼此退化的情况下都表现良好，如果我们只检测那些退化的情况，然后切换到速度更快的算法，那不是很理想吗？这就是我试图用我自己的图书馆Anchors做的事情。Anchors在同一张图上同时运行这两种算法！如果这听起来很疯狂、不必要而且过于复杂，那很可能是因为它确实如此。

在许多情况下，Anchors完全遵循Incremental的算法，避免了Adapton的上述退化情况。但当细胞被标记为未被观察到时，其行为略有不同。让我们来看看发生了什么。我们首先将Total标记为观察到的：

如果我们随后将Total标记为未观察到，并将Salsa标记为观察到的顺序，则传统的增量算法会将图表更改为如下所示，遍历过程中的每个单元格：

锚点还会遍历此更改的每个单元格，但会生成如下所示的图形：

注意“干净”的旗帜！当一个细胞不再需要时，我们将其标记为“干净”。让我们看看从观察Salsa转换到Total时会发生什么：

没错，我们的图表现在没有必要的单元格。如果一个单元格有一个“干净”的标志，我们永远不会把它标记为观察到的。此时，无论我们将哪个单元格标记为观察到或未观察到，Anchors都不会浪费时间遍历图表-它知道所有输入都没有更改。

看来El Farolito有折扣！我们把墨西哥卷饼降价一美元吧。主播如何知道需要重新计算总数？在重新计算任何公式之前，让我们先看看Anchors在我们只更改了Burrito Price之后，在重新计算任何东西之前将如何查看图表：

如果单元格有干净标志，我们就会对其运行传统的Adapton算法，急切地将下游单元格标记为脏的。当我们稍后运行增量算法时，我们可以快速判断出有一个观察到的单元格被标记为脏，并且知道我们需要重新计算它的依赖项。完成后，最终的图形将如下所示：

我们只在必要的时候重新计算单元格，所以每当我们重新计算脏乱的单元格时，我们也会将其标记为必要的。在较高级别上，您可以想象这三个单元状态形成一个循环状态机：

对于需要的单元格，我们运行增量的拓扑排序算法。对于不必要的单元格，我们运行Adapton算法。

最后，我想回答最后一个问题：到目前为止，我们一直在讨论需求驱动模式给我们的重新计算策略带来的许多问题。但问题不仅仅在于算法：还有语法问题需要解决。例如，让我们制作一个电子表格，为我们的客户选择一个玉米煎饼表情符号。我们会在电子表格中编写一条if语句，如下所示：

因为传统的电子表格不是需求驱动的，所以我们可以按任何顺序计算B1、B2和B3，只要我们在所有三个输入都准备好之后计算IF单元即可。然而，在一个需求驱动的世界里，如果我们能先计算B1的值，我们就可以窥视它的值，从而知道我们需要重新计算B2或B3中的哪一个。不幸的是，传统电子表格的IF无法表达这一点！

问题：B2同时引用单元格B2并检索其值🥦。这篇文章中提到的大多数需求驱动库都明确区分了对单元的引用和检索其实际值的行为。在Anchors中，我们将此单元格引用称为Anchor。就像现实生活中的玉米煎饼一样，Anchor<；T>；T型玉米煎饼包裹着T--我想这就是我们的素食玉米煎饼细胞Ancho<；Burrito>；，一种可笑的玉米煎饼。函数可以随心所欲地传递Anchor<；Burrito&>-只有当它们真正打开玉米煎饼以访问其中的玉米煎饼时，我们才会在图中创建依赖边，向重新计算算法表明该单元格可能是必需的，需要重新计算。

Salsa和Adapton采取的方法是使用函数调用和正常控制流作为展开这些值的一种方式。例如，在Adapton中，我们可能会将“Burrito for Customer”单元格写成这样：

通过区分单元格引用(这里是vegi_burrito)和展开其值的行为(get！)，Adapton可以利用Rust的控制流运算符(如if)。这是一个很棒的解决方案！然而，需要一点神奇的全局状态才能正确连接GET！给手机打电话！当素食改变时，这需要重新计算。我对Anchors采取的方法，灵感来自增量，是一个稍微不那么神奇的系统。与预异步/等待未来类似，Anchors允许您使用MAP等操作，然后在Anchor<；T>；上使用。例如,。

.