報表系統中公式依賴關系分析及計算性能優化

李 軍，曹 震，楊曉光

（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.