算法寻找循环引用作为preadsheet [英] Algorithm for finding circular references in a spreadsheet

问题描述

我与公式preadsheet应用。我在寻找用于检测公式中的循环引用最好的算法。目前的方法我已经很慢，并且使用了太多的内存计算时长链到位的公式。它包括保持集中的所有家属对每个配方。因此，如果细胞的第一列各有一个参考之前的小区的公式中，第一单元的集将是空的。第二单元的集将只包含第一个单元格，第三单元的集将包含单元1和2，...，第1000个细胞的集将包含999细胞之前。当引入一个新的配方，其依赖置是建立并且如果集包含新配方，有一个圆形的参考。但很明显，这种情况下，所需要的时间和内存呈指数级增长。

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.

请参阅<一href="http://en.wikipedia.org/wiki/Topological_sorting">http://en.wikipedia.org/wiki/Topological_sorting

这篇关于算法寻找循环引用作为preadsheet的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！