報(bào)表系統(tǒng)中公式依賴關(guān)系分析及計(jì)算性能優(yōu)化

李 軍，曹 震，楊曉光

（1.天津大學(xué) 管理與經(jīng)濟(jì)學(xué)部，天津300072；2.中國(guó)農(nóng)業(yè)銀行，北京100005；3.中國(guó)科學(xué)院 數(shù)學(xué)與系統(tǒng)科學(xué)研究院，北京100190）

0 引 言

Web報(bào)表系統(tǒng)是基于傳統(tǒng)報(bào)表系統(tǒng) （如 Microsoft Excel）的擴(kuò)展，與傳統(tǒng)的報(bào)表系統(tǒng)相比，Web報(bào)表系統(tǒng)具有的顯著優(yōu)點(diǎn)是：用戶可以在具備Web的條件下隨時(shí)隨地開展工作，很大程度上提升了效率，且方便易用。Web報(bào)表系統(tǒng)在商業(yè)銀行也得到了廣泛的應(yīng)用。當(dāng)前，某一報(bào)表的表內(nèi)公式的計(jì)算順序完全依賴于業(yè)務(wù)人員手動(dòng)調(diào)整，沒有相應(yīng)的機(jī)制去自動(dòng)分析公式間依賴關(guān)系，系統(tǒng)只能按照公式先后順序串行的執(zhí)行所有的公式，系統(tǒng)資源得不到充分的利用，公式運(yùn)算的時(shí)間相對(duì)較長(zhǎng)。一些學(xué)者針對(duì)Web報(bào)表系統(tǒng)的表內(nèi)公式的公式間依賴關(guān)系及計(jì)算性能優(yōu)化等問題進(jìn)行了一系列研究并提出了解決辦法，文獻(xiàn) ［1］提出了報(bào)表系統(tǒng)中的公式計(jì)算順序問題，然后描述了公式計(jì)算順序的形式定義，最后給出了用有向圖法解決公式計(jì)算順序的算法。文獻(xiàn) ［2－3］提出一種半監(jiān)督二次劃分聚類算法，在單元格聚類的基礎(chǔ)上，以單元格之間的引用關(guān)系為有向邊建立有向最大無(wú)環(huán)子圖，然后通過協(xié)同計(jì)算各有向最大無(wú)環(huán)子圖的拓?fù)湫蛄?，從而獲得較優(yōu)的計(jì)算順序。文獻(xiàn)［4］主要討論了報(bào)表的公式計(jì)算時(shí)可能因?yàn)楣介g存在循環(huán)依賴而導(dǎo)致計(jì)算失敗，提出了一種解決循環(huán)依賴的方法。同時(shí)，一些有向無(wú)環(huán)圖并行計(jì)算的研究也在逐步開展，文獻(xiàn) ［5］開展了有向無(wú)環(huán)圖的高效計(jì)算的算法研究，針對(duì)頂點(diǎn)帶層次的AOV網(wǎng)絡(luò)，提出了LAOV拓?fù)渑判蛩惴?，在調(diào)度、優(yōu)化等領(lǐng)域。取得了成功。文獻(xiàn) ［6］開展了在網(wǎng)格環(huán)境下遺傳算法在有向無(wú)環(huán)圖運(yùn)算中的應(yīng)用，所提出的算法在特定條件下有良好的效果，但是有時(shí)要達(dá)到預(yù)期性能，迭代次數(shù)過多。文獻(xiàn) ［7］提出了一種新的基于順逆交替迭代技術(shù)的啟發(fā)式調(diào)度算法，很好的解決了有向圖并行計(jì)算問題，提高了計(jì)算的效率。文獻(xiàn) ［8－9］分別在不同的應(yīng)用領(lǐng)域開展了有向圖的并行計(jì)算算法的研究，所提出的算法在各自特定的領(lǐng)域有著顯著的效果。

但是上述這些算法，都沒有提出自適應(yīng)的分析公式之間的依賴關(guān)系的方法，且目前的算法在公式計(jì)算性能優(yōu)化方面還不夠完善。本文提出的解決方案能自動(dòng)分析表內(nèi)公式間的依賴關(guān)系，自適應(yīng)的調(diào)整公式的計(jì)算順序，并且提出了層次化拓?fù)渑判蛩惴ㄟM(jìn)一步減小公式鏈的總計(jì)算時(shí)間。

1 問題描述與系統(tǒng)模型

1.1 問題描述

一張報(bào)表是由一個(gè)排列如矩陣的表格單元的有限集合，一個(gè)單元格包含4個(gè)主要的因素：①值；②公式；③引用單元格集合；④依賴單元格集合［10］。本文主要解決了報(bào)表系統(tǒng)表內(nèi)公式依賴關(guān)系的自動(dòng)分析，并給出高效的計(jì)算方式，提高公式計(jì)算執(zhí)行效率。

公式依賴關(guān)系概念定義：一張報(bào)表中包含的公式的集合，稱為一張報(bào)表的公式集合，記作F＝｛f1，f2，···fn｝。依賴是集合F上的二元關(guān)系，記作 “－＞”，fi－＞fj，其中fi，fj泛指公式集合中任意兩個(gè)不同的公式。

下面以實(shí)際報(bào)表系統(tǒng)中某一張報(bào)表的表內(nèi)公式來(lái)說(shuō)明問題，為了討論問題方便，我們僅取報(bào)表的前14條表內(nèi)公式，如下所示：

這些公式組成的公式鏈間暗含著公式執(zhí)行的先后順序，如公式f3必須在公式f1、f2執(zhí)行后再執(zhí)行。為了討論問題方便，暫且不考慮公式間執(zhí)行時(shí)間的差別，假定每個(gè)公式的執(zhí)行時(shí)間都為T，執(zhí)行完此報(bào)表的前14條公式，按照目前常規(guī)的計(jì)算方式，公式的計(jì)算順序?yàn)椋篺1，f2，f3，f4，f5…f14，則執(zhí)行完這14個(gè)公式所耗費(fèi)的總時(shí)間是14 T。如果按照某種設(shè)定好的執(zhí)行順序，并行的計(jì)算這些公式，先同時(shí)執(zhí)行公式f1，f7，f8，f11，再同時(shí)執(zhí)行f2，f9，f5，f6，接著執(zhí)行f3，f10，f4，再執(zhí)行f14，f12，最后執(zhí)行f13，此報(bào)表的所有表內(nèi)公式總執(zhí)行時(shí)間為5 T。顯然5 T遠(yuǎn)遠(yuǎn)小于14 T的執(zhí)行時(shí)間，總的計(jì)算時(shí)間大大較少，效率得到很大的提升。隨著公式數(shù)目的增加，這種效果會(huì)更明顯。

從例子可以得到啟示，我們需要設(shè)計(jì)這樣的系統(tǒng)，可以動(dòng)態(tài)的分析公式之間的依賴關(guān)系，自適應(yīng)的調(diào)整公式的計(jì)算順序，找到一種高效的公式計(jì)算執(zhí)行方法，降低每張報(bào)表中所有表內(nèi)公式的總執(zhí)行時(shí)間，下面章節(jié)將詳細(xì)介紹。

1.2 系統(tǒng)模型

報(bào)表系統(tǒng)中公式比較復(fù)雜包含兩層含義；第一層，公式的類型比較復(fù)雜，有行公式、列公式、單元格公式、要素公式、帶時(shí)間切換的公式，帶有維度切換 （如時(shí)間維度切換、機(jī)構(gòu)維度切換）的公式；第二層，公式的排列順序，有先行后列，或先列后行的形式，或先行 （列）后單元格等形式，執(zhí)行順序的不同可能造成某些單元格的值被覆蓋。

鑒于表內(nèi)公式類型比較復(fù)雜，如果采用單元格為基本處理單元［2－4］，找到每個(gè)單元格之間的依賴關(guān)系，則對(duì)于行公式和列公式會(huì)造成大量的冗余。如果采用行或列公式為處理單元，獲得行、列之間的依賴關(guān)系，則單元格形式的公式將會(huì)被遺漏。而且，不管以單元格還是行、列為處理單元，都會(huì)隨著報(bào)表大小，報(bào)表形式的變化，依賴關(guān)系產(chǎn)生很大的改變，這些都給依賴關(guān)系分析和計(jì)算帶來(lái)困難。

基于上述因素考慮，本文采用以公式自身為處理單元，設(shè)公式集合F ＝ ｛f1，f2，f3，f4，···fn｝，要分析公式集合F中任意fi，與集合中其他公式間的依賴關(guān)系，構(gòu)建依賴關(guān)系圖進(jìn)而來(lái)完成公式計(jì)算順序的優(yōu)化。公式依賴關(guān)系圖G 是一種有向無(wú)環(huán)圖 DAG （directed acyclic graph），G ＝（V，E），其中頂點(diǎn)集合V用于表示公式集合，V＝｛vi｜1in｝；有向邊集合E＝｛eij｜1in，1jn｝表示公式之間的依賴關(guān)系。任務(wù)vi＝（ti，Ωi），其中ti表示任務(wù)的執(zhí)行時(shí)間，ΩiV表示任務(wù)i的前驅(qū)任務(wù)集合，依賴關(guān)系圖中，頂點(diǎn)內(nèi)部的數(shù)字表示公式編號(hào)，頂點(diǎn)邊上的數(shù)值表示公式執(zhí)行時(shí)間，有向邊eij上數(shù)值cij表示。

本文提出的報(bào)表中公式依賴關(guān)系分析及計(jì)算順序優(yōu)化系統(tǒng)包含：公式解析拆分模塊，公式間依賴關(guān)系分析模塊，公式依賴關(guān)系圖創(chuàng)建與分析模塊 ，計(jì)算順序優(yōu)化算法實(shí)現(xiàn)模塊。如圖1所示。

圖1 系統(tǒng)框架

在依賴關(guān)系圖中，一方面，圖中邊對(duì)應(yīng)的數(shù)據(jù)依賴關(guān)系表示邊終點(diǎn)必須在邊始點(diǎn)計(jì)算完畢之后才能開始計(jì)算，并且需要引用這條邊始點(diǎn)的最新計(jì)算結(jié)果；另一方面，沒有數(shù)據(jù)依賴關(guān)系的節(jié)點(diǎn)間可以并行計(jì)算。依賴關(guān)系圖并行計(jì)算的核心就是如何設(shè)計(jì)并行計(jì)算的算法，充分挖掘依賴關(guān)系圖中隱藏的內(nèi)在并行度，縮短依賴關(guān)系圖并行計(jì)算時(shí)間。

2 系統(tǒng)的具體實(shí)現(xiàn)

2.1 公式解析拆分模塊

系統(tǒng)自動(dòng)獲取報(bào)表內(nèi)的表內(nèi)公式，將公式鏈交付給公式解析拆分模塊。需要解析、拆分的公式類型，包含單元格、行、列公式。對(duì)每個(gè)公式進(jìn)行解析拆分，將提取到的公式中包含的行、列、單元格等元素以字符串的形式保存，最終每個(gè)公式中包含的元素形成一個(gè)字符串?dāng)?shù)組，字符串?dāng)?shù)組的第一項(xiàng)為公式的左端元素，字符串?dāng)?shù)組的其他項(xiàng)為公式的右端元素。

形如行公式R4＝R5＋R8＋R9＋R12＋R13，經(jīng)過拆分后要得到字符串?dāng)?shù)組為 ｛R4，R5，R8，R9，R12，R13｝，第一項(xiàng)R4為公式的左端元素，第二項(xiàng)及后面各項(xiàng)為公式的右端元素。再如單元格形式的公式R7C4＝R7C3＊100／（R7C1－R7C2），要提取出字符串?dāng)?shù)組 ｛R7C4，R7C3，R7C1，R7C2｝。

具體實(shí)現(xiàn)時(shí)還要考慮去重的問題，如果簡(jiǎn)單的從公式C5＝3＊C4／（C1－C4），提取元素集合為 ｛C5，C4，C1，C4｝，會(huì)出現(xiàn)兩個(gè)C4，這種情況，要對(duì)字符串?dāng)?shù)組進(jìn)行去重操作。

2.2 動(dòng)態(tài)構(gòu)建公式依賴關(guān)系

利用第一步公式解析模塊得到的字符串?dāng)?shù)組，如果一個(gè)公式f1的左端元素是另一個(gè)公式f2的右端某一元素或者某一元素的一部分時(shí)，則說(shuō)明公式f2依賴于f1，記為f2－＞f1，以此類推，這樣可以建立起公式間兩兩依賴的關(guān)系。

設(shè)公式fi拆分后生成字符串?dāng)?shù)組的第一個(gè)元素fi［0］，設(shè)fk∈｛F－fi｝，為公式鏈集合中除去fi的任一公式，N為公式數(shù)目，即集合F的大小。公式依賴關(guān)系分析的核心思想：

公式間依賴關(guān)系分析算法如圖2所示。

圖2 公式間依賴關(guān)系分析算法

例如f1：R1＝R2＋R3，f2：R5＝R1＋R7，公式f1解析出來(lái)的結(jié)果為 ｛R1，R2，R3｝，由上述的規(guī)則知，公式f1的左端R1，公式的右端為R2，R3。假設(shè)公式f2解析的結(jié)果為｛R2，R1，R7｝。用f1的左端R1去匹配公式f2的右端字符串?dāng)?shù)組｛R1，R7｝，匹配成功說(shuō)明f1－＞f2。另一種情況，某一公式的左端元素，是另一公式某元素的子串。例如f1：R1＝R2＋R3，f3：R7C8＝R1C2＋R3C4如果公式f1的左端R1，去匹配公式f2的右端集合 ｛R1C2，R3C4｝，R1分別檢驗(yàn)是否為R1C2，R3C4的子串，如果有一項(xiàng)匹配成功就終止繼續(xù)比較，R1是R1C2的子串，說(shuō)明f1－＞f2。

在實(shí)際系統(tǒng)的實(shí)現(xiàn)時(shí)，要考慮到特殊情況的處理，如公式f1左端為R1，公式f2右端為｛R11C1，R13C4｝的情況，單純的利用字符串匹配會(huì)造成這種情況的誤判。因?yàn)楣浇馕鼋Y(jié)果程序處理時(shí)為R1在計(jì)算機(jī)系統(tǒng)中被保存為R1，R11C1被保存為R11C1，R1是R11C1的子串，但這種情況匹配成功是不正確的，要增加特殊處理機(jī)制，如判斷R1后的字符是不是 “09”之間的字符，來(lái)過濾這類誤判的情況。

2.3 公式依賴關(guān)系圖建立

采用本文的公式依賴關(guān)系分析方法，單元格公式會(huì)天然的形成單元格公式簇 （RC簇）、行公式天然的形成行公式簇 （R簇）、列公式天然的形成列公式簇 （C簇），如圖3所示。單元格公式簇可能會(huì)把行公式簇與列公式簇聯(lián)系起來(lái)。

以2.1節(jié)的例子為例，實(shí)際報(bào)表系統(tǒng)中一張報(bào)表的14個(gè)表內(nèi)公式的公式間依賴關(guān)系圖如圖4所示。

要保證公式的計(jì)算順序能正常獲取，必須保證公式依賴關(guān)系圖中不存在循環(huán)依賴，否則將不能得到正確的計(jì)算順序。

公式循環(huán)依賴的判定

循環(huán)依賴：設(shè)有公式集合F及依賴關(guān)系ψ（F），F(xiàn)′F，ψ′＝ψ（F′），稱依賴ψ′是循環(huán)依賴當(dāng)且僅當(dāng)圖G′（F′，ψ′）是G（F，ψ）中的一條有向回路［4］。

非循環(huán)圖：若有向圖G無(wú)回路，則稱其為非循環(huán)圖。更進(jìn)一步，若圖G中沒有有向回路，那么稱其為嚴(yán)格非循環(huán)圖［4］。

判斷圖G中是否存在循環(huán)依賴等價(jià)于判定G＝G（F，ψ）是否為嚴(yán)格的非循環(huán)依賴圖，也就是判斷圖G中是否存在有向回路。首先根據(jù)公式集合F來(lái)構(gòu)造公式間依賴關(guān)系，再判斷是否存在有向回路。具體算法及實(shí)現(xiàn)細(xì)節(jié)，文獻(xiàn)［4］已經(jīng)詳細(xì)闡述，本文不再贅述。

2.4 公式計(jì)算順序優(yōu)化算法

得到各公式間依賴關(guān)系，建立公式依賴關(guān)系圖后，最大的好處就是，沒有依賴關(guān)系的結(jié)點(diǎn)之間可以并行計(jì)算。本節(jié)首先介紹了傳統(tǒng)的拓?fù)渑判蛩惴?，然后詳?xì)介紹了本文提出的層次化拓?fù)渑判蛩惴ā?/p>

2.4.1 基于拓?fù)渑判虻墓接?jì)算性能優(yōu)化

如果公式集合中不存在循環(huán)依賴關(guān)系，那么公式的依賴關(guān)系圖為嚴(yán)格非循環(huán)圖。此時(shí)，利用拓?fù)渑判蛩惴ň湍塬@得合理的計(jì)算順序。根據(jù)圖論知識(shí)可知，有向無(wú)環(huán)圖必存在入度為0的節(jié)點(diǎn)，所以采用沒有前驅(qū)的節(jié)點(diǎn)優(yōu)先的拓?fù)渑判蛩惴?，?duì)依賴關(guān)系圖進(jìn)行拓?fù)渑判颍M(jìn)而得到公式的計(jì)算順序。

設(shè)定圖G是根據(jù)公式集合構(gòu)造的有向圖，對(duì)一個(gè)普通的依賴關(guān)系圖進(jìn)行拓?fù)渑判驎r(shí)，需要建立一個(gè)入度為0的頂點(diǎn)棧S（當(dāng)然也可用隊(duì)列來(lái)存儲(chǔ)，入度為0的頂點(diǎn)是不依賴任何其他公式的頂點(diǎn)。該算法的核心思想是：每一次輸出當(dāng)前沒有前驅(qū)的頂點(diǎn)。具體的拓?fù)渑判蛩惴▽?shí)現(xiàn)參見文獻(xiàn) ［2］。

例如，對(duì)圖4所示的依賴關(guān)系圖進(jìn)行拓?fù)渑判蚝?，得到的一個(gè)拓?fù)渑判虻男蛄袨閒1，f7，f8，f11，f2，f9，f5，f6，f3，f10，f4，f14，f12。當(dāng) 然 ， 一 個(gè) 依 賴 關(guān) 系 圖 的 拓 撲有序序列往往不是唯一的，例如對(duì)圖4而言，它的另一個(gè)拓?fù)湫蛄袨椋篺1，f7，f8，f11，f2，f9，f5，f3，f10，f4，f14，f12，f6。

在對(duì)依賴關(guān)系圖進(jìn)行分析時(shí)，如果算法執(zhí)行完畢 （也就是找不到入度為0的頂點(diǎn)時(shí)），還有頂點(diǎn)沒有輸出，說(shuō)明依賴關(guān)系圖中存在著有向回路，這在實(shí)際的報(bào)表公式計(jì)算中是不允許的。

2.4.2 基于層次化拓?fù)渑判虻墓接?jì)算順序優(yōu)化

普通的拓?fù)渑判蛏傻男蛄惺且环N串行的計(jì)算序列，沒有減小報(bào)表系統(tǒng)中表內(nèi)公式總的計(jì)算時(shí)間，公式之間的依賴關(guān)系分析沒有得到充分的利用。下面提出的新的算法－層次化拓?fù)渑判蛩惴?，可以在很大程度上減小表內(nèi)公式總的計(jì)算時(shí)間。通過層次拓?fù)溆?jì)算算法可以得到多層次的公式計(jì)算序列，每層次的沒有依賴關(guān)系的公式可以并行計(jì)算，相鄰層次之間的頂點(diǎn)間可能有依賴關(guān)系。圖5示例了有9個(gè)公式的層次化拓?fù)渑判蛩惴ǖ挠?jì)算過程示意圖，這9個(gè)公式經(jīng)過依賴關(guān)系分析后，被分成三層，每一層中包含的公式并行執(zhí)行計(jì)算過程。

圖5 層次化拓?fù)渑判?/p>

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

以圖1為例，采用層次化拓?fù)渑判蛩惴ǖ玫焦降挠?jì)算序列，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示例了采用層次化拓?fù)渑判蛩惴ú⑿杏?jì)算的執(zhí)行時(shí)間，以圖5包含9個(gè)節(jié)點(diǎn)的公式為例，每層公式之間并行執(zhí)行及不同層之間串行執(zhí)行的情況。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 系統(tǒng)分析

對(duì)于報(bào)表系統(tǒng)中一張實(shí)際的報(bào)表，假設(shè)表內(nèi)公式的總數(shù)為N，任一公式fi的計(jì)算時(shí)間為t（fi）（0iN－1），不進(jìn)行任何優(yōu)化時(shí)，采用普通拓?fù)渑判虻姆椒?，即所有公式按照先后順序一條條串行的執(zhí)行，一張報(bào)表的包含的表內(nèi)公式的總計(jì)算時(shí)間為

報(bào)表中公式間的依賴關(guān)系決定了必須保證依賴關(guān)系圖中靠前的公式先執(zhí)行，后繼任務(wù)后執(zhí)行，對(duì)于同一層的公式并行執(zhí)行，不同層的公式串行執(zhí)行，為了滿足這個(gè)條件，使用level的概念產(chǎn)生公式計(jì)算順序。一個(gè)公式的level被定義為，沒有依賴關(guān)系的，可以并行執(zhí)行的公式集合。設(shè)總的層數(shù)為level＿num，假設(shè)每層含有的公式數(shù)目為level（i）（0＝＜i＜level＿num），設(shè)每層level（i）包含的元素分別為a［i］［k］，其中0＝＜k＜ level＿num

根據(jù)木桶效應(yīng)，每層的公式的實(shí)際計(jì)算時(shí)間 由該層性能最差的公式?jīng)Q定的，即由計(jì)算時(shí)間最長(zhǎng)的決定的。

采用層次化拓?fù)渑判蛩惴?，由上述描述知道層的最大?shù)目為lmax（其中l(wèi)max＝level＿num－1），一張報(bào)表的公式鏈的總計(jì)算時(shí)間為：

當(dāng)level＿num＞1時(shí)

當(dāng)level＿num＝1，即所有公式之間沒有依賴關(guān)系，可以一起并行執(zhí)行，此時(shí)有

設(shè)η為優(yōu)化后所耗費(fèi)的執(zhí)行時(shí)間占原執(zhí)行時(shí)間的百分比，進(jìn)一步可以得到

很明顯η＜＝1，當(dāng)level＿num＞1，如果每個(gè)公式的執(zhí)行時(shí)間相同，則

如果一張報(bào)表內(nèi)所有公式之間都沒有依賴關(guān)系時(shí)，即level＿num＝1，設(shè)N為公式鏈中公式的數(shù)目

如果公式之間本身的依賴關(guān)系少，且一張報(bào)表中表內(nèi)公式的數(shù)目很多時(shí) （一般N取50以上，就可以認(rèn)為N很大），則公式鏈的總計(jì)算時(shí)間會(huì)很小。

3.2 實(shí)驗(yàn)驗(yàn)證

文獻(xiàn) ［11］提出了評(píng)價(jià)Web服務(wù)質(zhì)量最直觀的一個(gè)參數(shù)－Web服務(wù)的響應(yīng)時(shí)間，并利用Apache axis和實(shí)際需要，設(shè)計(jì)并實(shí)現(xiàn)了一套Web服務(wù)響應(yīng)時(shí)間測(cè)試系統(tǒng)，取得了比較好的效果。文獻(xiàn) ［12］提出了分析分布式實(shí)時(shí)數(shù)據(jù)傳輸系統(tǒng)，如何評(píng)估其性能是很重要的，并給出了系統(tǒng)的性能不同的評(píng)估驗(yàn)證方法［3］。

本文模擬了Web報(bào)表系統(tǒng)的實(shí)際運(yùn)行環(huán)境，對(duì)實(shí)際商業(yè)銀行報(bào)表系統(tǒng)的報(bào)表進(jìn)行了性能測(cè)試，測(cè)試每張報(bào)表表內(nèi)公式計(jì)算的響應(yīng)時(shí)間。第一種方案采用普通的拓?fù)渑判蚍椒ǎ匆来斡?jì)算Web報(bào)表的每張報(bào)表表內(nèi)的每個(gè)公式，此時(shí)計(jì)算順序沒有做任何優(yōu)化；第二種方案，采用了層次化拓?fù)渑判虻姆椒?。在?shí)驗(yàn)時(shí)，針對(duì)每一個(gè)特定的N值，采用30次計(jì)算響應(yīng)時(shí)間的平均值作為該報(bào)表的響應(yīng)時(shí)間Ti，時(shí)間單位為毫秒 （ms）。普通方法的平均時(shí)間用Tnormal表示，采用本文優(yōu)化方法的平均時(shí)間用Toptimize表示，η含義與上一節(jié)相同，為采用層次化拓?fù)渑判蛩惴ㄋ馁M(fèi)的執(zhí)行時(shí)間與普通拓?fù)渑判蛩惴ㄋ馁M(fèi)時(shí)間的比，測(cè)試結(jié)果見表1。

表1 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)結(jié)果驗(yàn)證了η一定小于等于1，本實(shí)驗(yàn)中的η＜0.5。從實(shí)驗(yàn)結(jié)果也可以得到這樣的結(jié)論：本文所采用的層次化拓?fù)渑判蛩惴ê芎玫奶岣吡讼到y(tǒng)的性能，大大的縮短了公式鏈的執(zhí)行時(shí)間，采用層次化拓?fù)渑判蛩惴ㄋㄙM(fèi)的時(shí)間比采用普通方法花費(fèi)時(shí)間的50%還少。從實(shí)驗(yàn)結(jié)果也可以發(fā)現(xiàn)，當(dāng)公式數(shù)目即N越大，同時(shí)層數(shù)level＿num越小時(shí)，系統(tǒng)的性能越好。由于在實(shí)際系統(tǒng)中，行公式、列公式、單元格公式的執(zhí)行時(shí)間不同，即使同一種類型公式，公式長(zhǎng)度等不同，也會(huì)造成每個(gè)公式的執(zhí)行時(shí)間不同，所以η只能接近但不能等于（level＿num－1）／N。

4 結(jié)束語(yǔ)

本文所提出的方法，能自動(dòng)分析報(bào)表系統(tǒng)的公式依賴關(guān)系，并根據(jù)依賴關(guān)系圖進(jìn)一步調(diào)整公式的計(jì)算順序，利用層次化拓?fù)渑判虻姆椒?，很大程度上減小報(bào)表系統(tǒng)公式鏈中公式的計(jì)算時(shí)間。本文還進(jìn)一步推導(dǎo)出了系統(tǒng)總的執(zhí)行時(shí)間，及每張報(bào)表所包含的表內(nèi)公式的總計(jì)算時(shí)間的極限情況，并在實(shí)際商業(yè)銀行系統(tǒng)中進(jìn)行了應(yīng)用。理論分析和實(shí)驗(yàn)的結(jié)果均表明所提出的算法給系統(tǒng)性能帶來(lái)顯著的提升。目前僅考慮了表內(nèi)公式，下一步將推廣到表間公式的計(jì)算性能優(yōu)化中。當(dāng)然系統(tǒng)總的執(zhí)行時(shí)間還不能達(dá)到最小，因?yàn)槟壳安荒芫?xì)的得到依賴圖的邊上的權(quán)值，即每個(gè)公式具體的執(zhí)行時(shí)間。如果可以獲悉每個(gè)公式的具體執(zhí)行時(shí)間，每層之間需要進(jìn)一步的協(xié)作，可以借鑒遺傳算法，粒子群算法等，使系統(tǒng)總的時(shí)間達(dá)到最小。

：

［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）.［赫楓齡，劉磊，張孝志.用有向圖法確定報(bào)表系統(tǒng)中的公式計(jì)算順序 ［J］.計(jì)算機(jī)工程與應(yīng)，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）. ［趙立永，趙沖沖，時(shí)鵬，等.半監(jiān)督二次劃分聚類算法及其報(bào)表系統(tǒng)應(yīng)用 ［J］.小型微型計(jì)算機(jī)系統(tǒng)，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）. ［馬偉勤，李涓子，金正曄，等.報(bào)表系統(tǒng)中依賴表格的重新計(jì)算算法［J］.計(jì)算機(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網(wǎng)絡(luò)及其拓?fù)渑判蛩惴?［J］.計(jì)算機(jī)工程與科學(xué)，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）. ［張愛清，莫?jiǎng)t堯.有向圖并行計(jì)算中一種新的結(jié)點(diǎn)調(diào)度算法 ［J］.計(jì)算機(jī)學(xué)報(bào)，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服務(wù)響應(yīng)時(shí)間測(cè)試 ［J］.計(jì)算機(jī)工程與設(shè)計(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.