在电子表格中查找循环引用的算法 [英] Algorithm for finding circular references in a spreadsheet

问题描述

我有一个包含公式的电子表格应用程序。我正在寻找公式中检测循环引用的最佳算法。目前的方法是缓慢的，并且使用太多的记忆，当长的计算链与公式一起使用时。它涉及保留每个公式的所有依赖的集合。因此，如果第一列单元格具有一个具有引用它的单元格的公式，则第一个单元格的集合将为空。第二个单元格的集合将仅包含第一个单元格，第三个单元格的集合将包含单元格1和2，...，第1000个单元格的集合将包含999个单元格。当引入新的公式时，其依赖集合被构建，并且如果集合包含新的公式，则存在循环引用。但是显然，在这种情况下，所需的时间和内存将呈指数增长。

解决方案

您需要对单元格进行拓扑排序无论如何，为了能够快速计算某些事物改变时细胞的值。拓扑排序过程也会检测周期作为副产品。

请参阅 http://en.wikipedia.org/wiki/Topological_sorting

I have a spreadsheet application with formulas. I am looking for the best algorithm for detecting circular references among the formulas. The current approach I have is slow and uses too much memory when long chains of calculations are in place with the formulas. It involves keeping sets of all dependents for each formula. So if the first column of cells each had a formula with a reference to the cell before it, the first cell's set would be empty. The 2nd cell's set would only contain the first cell, the 3rd cell's set would contain cells 1 and 2, ..., the 1000th cell's set would contain the 999 cells before it. When a new formula was introduced, its dependents set is built and if the set contains the new formula, there is a circular reference. But obviously, for this scenario, the time and memory required grows exponentially.

解决方案

You need to do a topological sorting of the cells anyway in order to be able to rapidly calculate the values of cells when something is changed. The topological sorting procedure also detect cycles as a byproduct.

See http://en.wikipedia.org/wiki/Topological_sorting

这篇关于在电子表格中查找循环引用的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！