报表系统中公式依赖关系分析及计算性能优化

李 军，曹 震，杨晓光

（1.天津大学 管理与经济学部，天津300072；2.中国农业银行，北京100005；3.中国科学院 数学与系统科学研究院，北京100190）

0 引 言

Web报表系统是基于传统报表系统 （如 Microsoft Excel）的扩展，与传统的报表系统相比，Web报表系统具有的显著优点是：用户可以在具备Web的条件下随时随地开展工作，很大程度上提升了效率，且方便易用。Web报表系统在商业银行也得到了广泛的应用。当前，某一报表的表内公式的计算顺序完全依赖于业务人员手动调整，没有相应的机制去自动分析公式间依赖关系，系统只能按照公式先后顺序串行的执行所有的公式，系统资源得不到充分的利用，公式运算的时间相对较长。一些学者针对Web报表系统的表内公式的公式间依赖关系及计算性能优化等问题进行了一系列研究并提出了解决办法，文献 ［1］提出了报表系统中的公式计算顺序问题，然后描述了公式计算顺序的形式定义，最后给出了用有向图法解决公式计算顺序的算法。文献 ［2－3］提出一种半监督二次划分聚类算法，在单元格聚类的基础上，以单元格之间的引用关系为有向边建立有向最大无环子图，然后通过协同计算各有向最大无环子图的拓扑序列，从而获得较优的计算顺序。文献［4］主要讨论了报表的公式计算时可能因为公式间存在循环依赖而导致计算失败，提出了一种解决循环依赖的方法。同时，一些有向无环图并行计算的研究也在逐步开展，文献 ［5］开展了有向无环图的高效计算的算法研究，针对顶点带层次的AOV网络，提出了LAOV拓扑排序算法，在调度、优化等领域。取得了成功。文献 ［6］开展了在网格环境下遗传算法在有向无环图运算中的应用，所提出的算法在特定条件下有良好的效果，但是有时要达到预期性能，迭代次数过多。文献 ［7］提出了一种新的基于顺逆交替迭代技术的启发式调度算法，很好的解决了有向图并行计算问题，提高了计算的效率。文献 ［8－9］分别在不同的应用领域开展了有向图的并行计算算法的研究，所提出的算法在各自特定的领域有着显著的效果。

但是上述这些算法，都没有提出自适应的分析公式之间的依赖关系的方法，且目前的算法在公式计算性能优化方面还不够完善。本文提出的解决方案能自动分析表内公式间的依赖关系，自适应的调整公式的计算顺序，并且提出了层次化拓扑排序算法进一步减小公式链的总计算时间。

1 问题描述与系统模型

1.1 问题描述

一张报表是由一个排列如矩阵的表格单元的有限集合，一个单元格包含4个主要的因素：①值；②公式；③引用单元格集合；④依赖单元格集合［10］。本文主要解决了报表系统表内公式依赖关系的自动分析，并给出高效的计算方式，提高公式计算执行效率。

公式依赖关系概念定义：一张报表中包含的公式的集合，称为一张报表的公式集合，记作F＝｛f1，f2，···fn｝。依赖是集合F上的二元关系，记作 “－＞”，fi－＞fj，其中fi，fj泛指公式集合中任意两个不同的公式。

下面以实际报表系统中某一张报表的表内公式来说明问题，为了讨论问题方便，我们仅取报表的前14条表内公式，如下所示：

这些公式组成的公式链间暗含着公式执行的先后顺序，如公式f3必须在公式f1、f2执行后再执行。为了讨论问题方便，暂且不考虑公式间执行时间的差别，假定每个公式的执行时间都为T，执行完此报表的前14条公式，按照目前常规的计算方式，公式的计算顺序为：f1，f2，f3，f4，f5…f14，则执行完这14个公式所耗费的总时间是14 T。如果按照某种设定好的执行顺序，并行的计算这些公式，先同时执行公式f1，f7，f8，f11，再同时执行f2，f9，f5，f6，接着执行f3，f10，f4，再执行f14，f12，最后执行f13，此报表的所有表内公式总执行时间为5 T。显然5 T远远小于14 T的执行时间，总的计算时间大大较少，效率得到很大的提升。随着公式数目的增加，这种效果会更明显。

从例子可以得到启示，我们需要设计这样的系统，可以动态的分析公式之间的依赖关系，自适应的调整公式的计算顺序，找到一种高效的公式计算执行方法，降低每张报表中所有表内公式的总执行时间，下面章节将详细介绍。

1.2 系统模型

报表系统中公式比较复杂包含两层含义；第一层，公式的类型比较复杂，有行公式、列公式、单元格公式、要素公式、带时间切换的公式，带有维度切换 （如时间维度切换、机构维度切换）的公式；第二层，公式的排列顺序，有先行后列，或先列后行的形式，或先行 （列）后单元格等形式，执行顺序的不同可能造成某些单元格的值被覆盖。

鉴于表内公式类型比较复杂，如果采用单元格为基本处理单元［2－4］，找到每个单元格之间的依赖关系，则对于行公式和列公式会造成大量的冗余。如果采用行或列公式为处理单元，获得行、列之间的依赖关系，则单元格形式的公式将会被遗漏。而且，不管以单元格还是行、列为处理单元，都会随着报表大小，报表形式的变化，依赖关系产生很大的改变，这些都给依赖关系分析和计算带来困难。

基于上述因素考虑，本文采用以公式自身为处理单元，设公式集合F ＝ ｛f1，f2，f3，f4，···fn｝，要分析公式集合F中任意fi，与集合中其他公式间的依赖关系，构建依赖关系图进而来完成公式计算顺序的优化。公式依赖关系图G 是一种有向无环图 DAG （directed acyclic graph），G ＝（V，E），其中顶点集合V用于表示公式集合，V＝｛vi｜1in｝；有向边集合E＝｛eij｜1in，1jn｝表示公式之间的依赖关系。任务vi＝（ti，Ωi），其中ti表示任务的执行时间，ΩiV表示任务i的前驱任务集合，依赖关系图中，顶点内部的数字表示公式编号，顶点边上的数值表示公式执行时间，有向边eij上数值cij表示。

本文提出的报表中公式依赖关系分析及计算顺序优化系统包含：公式解析拆分模块，公式间依赖关系分析模块，公式依赖关系图创建与分析模块 ，计算顺序优化算法实现模块。如图1所示。

图1 系统框架

在依赖关系图中，一方面，图中边对应的数据依赖关系表示边终点必须在边始点计算完毕之后才能开始计算，并且需要引用这条边始点的最新计算结果；另一方面，没有数据依赖关系的节点间可以并行计算。依赖关系图并行计算的核心就是如何设计并行计算的算法，充分挖掘依赖关系图中隐藏的内在并行度，缩短依赖关系图并行计算时间。

2 系统的具体实现

2.1 公式解析拆分模块

系统自动获取报表内的表内公式，将公式链交付给公式解析拆分模块。需要解析、拆分的公式类型，包含单元格、行、列公式。对每个公式进行解析拆分，将提取到的公式中包含的行、列、单元格等元素以字符串的形式保存，最终每个公式中包含的元素形成一个字符串数组，字符串数组的第一项为公式的左端元素，字符串数组的其他项为公式的右端元素。

形如行公式R4＝R5＋R8＋R9＋R12＋R13，经过拆分后要得到字符串数组为 ｛R4，R5，R8，R9，R12，R13｝，第一项R4为公式的左端元素，第二项及后面各项为公式的右端元素。再如单元格形式的公式R7C4＝R7C3＊100／（R7C1－R7C2），要提取出字符串数组 ｛R7C4，R7C3，R7C1，R7C2｝。

具体实现时还要考虑去重的问题，如果简单的从公式C5＝3＊C4／（C1－C4），提取元素集合为 ｛C5，C4，C1，C4｝，会出现两个C4，这种情况，要对字符串数组进行去重操作。

2.2 动态构建公式依赖关系

利用第一步公式解析模块得到的字符串数组，如果一个公式f1的左端元素是另一个公式f2的右端某一元素或者某一元素的一部分时，则说明公式f2依赖于f1，记为f2－＞f1，以此类推，这样可以建立起公式间两两依赖的关系。

设公式fi拆分后生成字符串数组的第一个元素fi［0］，设fk∈｛F－fi｝，为公式链集合中除去fi的任一公式，N为公式数目，即集合F的大小。公式依赖关系分析的核心思想：

公式间依赖关系分析算法如图2所示。

图2 公式间依赖关系分析算法

例如f1：R1＝R2＋R3，f2：R5＝R1＋R7，公式f1解析出来的结果为 ｛R1，R2，R3｝，由上述的规则知，公式f1的左端R1，公式的右端为R2，R3。假设公式f2解析的结果为｛R2，R1，R7｝。用f1的左端R1去匹配公式f2的右端字符串数组｛R1，R7｝，匹配成功说明f1－＞f2。另一种情况，某一公式的左端元素，是另一公式某元素的子串。例如f1：R1＝R2＋R3，f3：R7C8＝R1C2＋R3C4如果公式f1的左端R1，去匹配公式f2的右端集合 ｛R1C2，R3C4｝，R1分别检验是否为R1C2，R3C4的子串，如果有一项匹配成功就终止继续比较，R1是R1C2的子串，说明f1－＞f2。

在实际系统的实现时，要考虑到特殊情况的处理，如公式f1左端为R1，公式f2右端为｛R11C1，R13C4｝的情况，单纯的利用字符串匹配会造成这种情况的误判。因为公式解析结果程序处理时为R1在计算机系统中被保存为R1，R11C1被保存为R11C1，R1是R11C1的子串，但这种情况匹配成功是不正确的，要增加特殊处理机制，如判断R1后的字符是不是 “09”之间的字符，来过滤这类误判的情况。

2.3 公式依赖关系图建立

采用本文的公式依赖关系分析方法，单元格公式会天然的形成单元格公式簇 （RC簇）、行公式天然的形成行公式簇 （R簇）、列公式天然的形成列公式簇 （C簇），如图3所示。单元格公式簇可能会把行公式簇与列公式簇联系起来。

以2.1节的例子为例，实际报表系统中一张报表的14个表内公式的公式间依赖关系图如图4所示。

要保证公式的计算顺序能正常获取，必须保证公式依赖关系图中不存在循环依赖，否则将不能得到正确的计算顺序。

公式循环依赖的判定

循环依赖：设有公式集合F及依赖关系ψ（F），F′F，ψ′＝ψ（F′），称依赖ψ′是循环依赖当且仅当图G′（F′，ψ′）是G（F，ψ）中的一条有向回路［4］。

非循环图：若有向图G无回路，则称其为非循环图。更进一步，若图G中没有有向回路，那么称其为严格非循环图［4］。

判断图G中是否存在循环依赖等价于判定G＝G（F，ψ）是否为严格的非循环依赖图，也就是判断图G中是否存在有向回路。首先根据公式集合F来构造公式间依赖关系，再判断是否存在有向回路。具体算法及实现细节，文献［4］已经详细阐述，本文不再赘述。

2.4 公式计算顺序优化算法

得到各公式间依赖关系，建立公式依赖关系图后，最大的好处就是，没有依赖关系的结点之间可以并行计算。本节首先介绍了传统的拓扑排序算法，然后详细介绍了本文提出的层次化拓扑排序算法。

2.4.1 基于拓扑排序的公式计算性能优化

如果公式集合中不存在循环依赖关系，那么公式的依赖关系图为严格非循环图。此时，利用拓扑排序算法就能获得合理的计算顺序。根据图论知识可知，有向无环图必存在入度为0的节点，所以采用没有前驱的节点优先的拓扑排序算法，对依赖关系图进行拓扑排序，进而得到公式的计算顺序。

设定图G是根据公式集合构造的有向图，对一个普通的依赖关系图进行拓扑排序时，需要建立一个入度为0的顶点栈S（当然也可用队列来存储，入度为0的顶点是不依赖任何其他公式的顶点。该算法的核心思想是：每一次输出当前没有前驱的顶点。具体的拓扑排序算法实现参见文献 ［2］。

例如，对图4所示的依赖关系图进行拓扑排序后，得到的一个拓扑排序的序列为f1，f7，f8，f11，f2，f9，f5，f6，f3，f10，f4，f14，f12。当 然 ， 一 个 依 赖 关 系 图 的 拓 扑有序序列往往不是唯一的，例如对图4而言，它的另一个拓扑序列为：f1，f7，f8，f11，f2，f9，f5，f3，f10，f4，f14，f12，f6。

在对依赖关系图进行分析时，如果算法执行完毕 （也就是找不到入度为0的顶点时），还有顶点没有输出，说明依赖关系图中存在着有向回路，这在实际的报表公式计算中是不允许的。

2.4.2 基于层次化拓扑排序的公式计算顺序优化

普通的拓扑排序生成的序列是一种串行的计算序列，没有减小报表系统中表内公式总的计算时间，公式之间的依赖关系分析没有得到充分的利用。下面提出的新的算法－层次化拓扑排序算法，可以在很大程度上减小表内公式总的计算时间。通过层次拓扑计算算法可以得到多层次的公式计算序列，每层次的没有依赖关系的公式可以并行计算，相邻层次之间的顶点间可能有依赖关系。图5示例了有9个公式的层次化拓扑排序算法的计算过程示意图，这9个公式经过依赖关系分析后，被分成三层，每一层中包含的公式并行执行计算过程。

图5 层次化拓扑排序

算法的核心思想如图6所示。

以图1为例，采用层次化拓扑排序算法得到公式的计算序列，level［0］包含的公式为f5，f6；level［1］的包含的公式为：f1，f7，f8，f11；level［2］的包含公式为f2，f9；level［3］包含的公式为f3，f4，f10；level［4］包含的公式为：f12，f14；level［5］包含的公式为f13。

图7示例了采用层次化拓扑排序算法并行计算的执行时间，以图5包含9个节点的公式为例，每层公式之间并行执行及不同层之间串行执行的情况。

3 实验结果与分析

3.1 系统分析

对于报表系统中一张实际的报表，假设表内公式的总数为N，任一公式fi的计算时间为t（fi）（0iN－1），不进行任何优化时，采用普通拓扑排序的方法，即所有公式按照先后顺序一条条串行的执行，一张报表的包含的表内公式的总计算时间为

报表中公式间的依赖关系决定了必须保证依赖关系图中靠前的公式先执行，后继任务后执行，对于同一层的公式并行执行，不同层的公式串行执行，为了满足这个条件，使用level的概念产生公式计算顺序。一个公式的level被定义为，没有依赖关系的，可以并行执行的公式集合。设总的层数为level＿num，假设每层含有的公式数目为level（i）（0＝＜i＜level＿num），设每层level（i）包含的元素分别为a［i］［k］，其中0＝＜k＜ level＿num

根据木桶效应，每层的公式的实际计算时间 由该层性能最差的公式决定的，即由计算时间最长的决定的。

采用层次化拓扑排序算法，由上述描述知道层的最大数目为lmax（其中lmax＝level＿num－1），一张报表的公式链的总计算时间为：

当level＿num＞1时

当level＿num＝1，即所有公式之间没有依赖关系，可以一起并行执行，此时有

设η为优化后所耗费的执行时间占原执行时间的百分比，进一步可以得到

很明显η＜＝1，当level＿num＞1，如果每个公式的执行时间相同，则

如果一张报表内所有公式之间都没有依赖关系时，即level＿num＝1，设N为公式链中公式的数目

如果公式之间本身的依赖关系少，且一张报表中表内公式的数目很多时 （一般N取50以上，就可以认为N很大），则公式链的总计算时间会很小。

3.2 实验验证

文献 ［11］提出了评价Web服务质量最直观的一个参数－Web服务的响应时间，并利用Apache axis和实际需要，设计并实现了一套Web服务响应时间测试系统，取得了比较好的效果。文献 ［12］提出了分析分布式实时数据传输系统，如何评估其性能是很重要的，并给出了系统的性能不同的评估验证方法［3］。

本文模拟了Web报表系统的实际运行环境，对实际商业银行报表系统的报表进行了性能测试，测试每张报表表内公式计算的响应时间。第一种方案采用普通的拓扑排序方法，即依次计算Web报表的每张报表表内的每个公式，此时计算顺序没有做任何优化；第二种方案，采用了层次化拓扑排序的方法。在实验时，针对每一个特定的N值，采用30次计算响应时间的平均值作为该报表的响应时间Ti，时间单位为毫秒 （ms）。普通方法的平均时间用Tnormal表示，采用本文优化方法的平均时间用Toptimize表示，η含义与上一节相同，为采用层次化拓扑排序算法所耗费的执行时间与普通拓扑排序算法所耗费时间的比，测试结果见表1。

表1 实验结果

实验结果验证了η一定小于等于1，本实验中的η＜0.5。从实验结果也可以得到这样的结论：本文所采用的层次化拓扑排序算法很好的提高了系统的性能，大大的缩短了公式链的执行时间，采用层次化拓扑排序算法所花费的时间比采用普通方法花费时间的50%还少。从实验结果也可以发现，当公式数目即N越大，同时层数level＿num越小时，系统的性能越好。由于在实际系统中，行公式、列公式、单元格公式的执行时间不同，即使同一种类型公式，公式长度等不同，也会造成每个公式的执行时间不同，所以η只能接近但不能等于（level＿num－1）／N。

4 结束语

本文所提出的方法，能自动分析报表系统的公式依赖关系，并根据依赖关系图进一步调整公式的计算顺序，利用层次化拓扑排序的方法，很大程度上减小报表系统公式链中公式的计算时间。本文还进一步推导出了系统总的执行时间，及每张报表所包含的表内公式的总计算时间的极限情况，并在实际商业银行系统中进行了应用。理论分析和实验的结果均表明所提出的算法给系统性能带来显著的提升。目前仅考虑了表内公式，下一步将推广到表间公式的计算性能优化中。当然系统总的执行时间还不能达到最小，因为目前不能精细的得到依赖图的边上的权值，即每个公式具体的执行时间。如果可以获悉每个公式的具体执行时间，每层之间需要进一步的协作，可以借鉴遗传算法，粒子群算法等，使系统总的时间达到最小。

：

［1］HE Fengling，LIU Lei，ZHANG Xiaozhi.Solve the problem of formula evaluation seguence by directed graph ［J］.Computer Engineering and Applications，2003，39 （36）：87－89 （in Chinese）.［赫枫龄，刘磊，张孝志.用有向图法确定报表系统中的公式计算顺序 ［J］.计算机工程与应，2003，39（36）：87－89.］

［2］Zhao Chongchong，Zhao Liyong，Zhang Xiaoming.Research on enterprise spreadsheet model based－on semantic ［C］／／The Sixth International Conference on Fuzzy Systems and Knowledge Discovery，2009：441－446.

［3］ZHAO Liyong，ZHAO Chongchong，SHI Peng，et al.Semisupervised quadratic partitional clustering algorithm and its application in spreadsheet system ［J］.Journal of Chinese Computer Systems，2011，3 （3）：499－505 （in Chinese）. ［赵立永，赵冲冲，时鹏，等.半监督二次划分聚类算法及其报表系统应用 ［J］.小型微型计算机系统，2011，3 （3）：499－505.］

［4］MA Weiqin，LI Juanzi，JIN Zhengye，et al.Algorithm for dependent cell recomputation in report system ［J］.Computer Engineering，2006，32 （13）：49－51 （in Chinese）. ［马伟勤，李涓子，金正晔，等.报表系统中依赖表格的重新计算算法［J］.计算机工程，2006，32 （13）：49－51.］

［5］WANG Guiping，ZHANG Shuai.The LAOV network and its topological sorting algorithm ［J］.Computer Engineering＆Science，2012，34 （3）：170－175 （in Chinese）. ［王桂平，张帅.LAOV网络及其拓扑排序算法 ［J］.计算机工程与科学，2012，34 （3）：170－175.］

［6］Pop F，Dobre C，Cristea V.Genetic algorithm for DAG scheduling in grid environments ［C］／／Proceedings of IEEE 5th International Conference on Intelligent Computer Communication and Processing，2009：299－305.

［7］ZHANG Aiqing，MO Zeyao.A new scheduling algorithm for digraph－based parallel computing ［J］.Chinese Journal of Computers，2009，32 （11）：2178－2186 （in Chinese）. ［张爱清，莫则尧.有向图并行计算中一种新的结点调度算法 ［J］.计算机学报，2009，32 （11）：2178－2186.］

［8］Cao H J，Jin H，Wu X X，et al.DAGMap：Efficient and dependable scheduling of DAG workflow job in grid ［J］.The Journal of Supercomputing，2010，51 （2）：201－223.

［9］Chen H，Ku W S，Sun M T，et al.The partial sequenced route query with traveling rules in road networks ［J］.GeoInformatica，2010，15 （3）：541－569.

［10］Juta Pichilamken，Supasit kajkamhaeng，Putchong Utha－yopas.High performance spreadsheet simulation on a desktop grid ［C］／／Proceedings of the Winter Simulation Conference，2008：663－670.

［11］LI Qiao，QIN Feng，ZHENG Xiao.Testing on web services response time ［J］.Computer Engineering and Design，2007，28 （19）：4070－4673 （in Chinese）.［李乔，秦锋，郑啸.Web服务响应时间测试 ［J］.计算机工程与设计，2007，28 （19）：4670－4673.］

［12］Saiedian H，Mulkey S.Performance evaluation of eventing web services in real－time applications ［J］.IEEE Communication Magazine，2008，46 （3）：106－111.