網(wǎng)格劃分是有限元計(jì)算的前提條件，而目前有限元計(jì)算精度要求越來越高，與之相應(yīng)的，網(wǎng)格劃分的數(shù)目也越來越多。數(shù)據(jù)量劇增后，與這部分?jǐn)?shù)據(jù)相關(guān)的操作就很有可能成為程序性能的瓶頸。

以這款水利分析軟件為例，軟件需要用到二維三角網(wǎng)格剖分。當(dāng)需要較高的計(jì)算精度時(shí)，網(wǎng)格的數(shù)量很可能會(huì)在十萬乃至五十萬以上，如果網(wǎng)格的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)不合理，這時(shí)候與網(wǎng)格相關(guān)的繪圖、選取等操作就可能會(huì)非常耗時(shí)，以至于影響用戶體驗(yàn)。

下面，筆者從與網(wǎng)格相關(guān)的操作需求出發(fā)，以stl標(biāo)準(zhǔn)模板庫中常用容器為載體，來分析網(wǎng)格應(yīng)當(dāng)具有怎樣的數(shù)據(jù)結(jié)構(gòu)。

首先羅列stl中常用的容器及其對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)：

（1）動(dòng)態(tài)數(shù)組：vector。

（2）鏈表：list。

（3）紅黑樹：set、map。

（4）哈希表/散列表：hash_map、hash_set。

下文中將以容器英文名稱進(jìn)行敘述。

1.繪圖

繪圖需要分別繪制網(wǎng)格結(jié)點(diǎn)、網(wǎng)格邊和網(wǎng)格單元。其中，網(wǎng)格單元有時(shí)需要以填充的方式進(jìn)行繪制，以顯示云圖、動(dòng)畫等計(jì)算結(jié)果。繪圖是頻繁進(jìn)行的一個(gè)操作，必須保證效率，因此要求網(wǎng)格結(jié)點(diǎn)、網(wǎng)格邊和網(wǎng)格單元都必須能以線性時(shí)間進(jìn)行遍歷。vector、list、set、map、hash_map、hash_set都能保證以線性時(shí)間進(jìn)行遍歷，但其中數(shù)組的遍歷速度最快。

2.元素拾取

元素拾取是用戶與網(wǎng)格交互的基礎(chǔ)，元素拾取主要指的是結(jié)點(diǎn)的拾取，根據(jù)網(wǎng)格的拓?fù)潢P(guān)系，網(wǎng)格單元和網(wǎng)格邊的拾取都可以依賴網(wǎng)格結(jié)點(diǎn)的拾取。元素拾取一般是通過判斷元素是否在一給定矩形選框中來實(shí)現(xiàn)的，要實(shí)現(xiàn)高效的拾取操作，需要將元素按某種規(guī)律（如按坐標(biāo)）進(jìn)行排序。set和map可以保證其中元素總是按一定規(guī)律排列，而vector則需要調(diào)用排序算法來維持其中元素的有序性。相應(yīng)的，set和map因?yàn)橐３衷氐挠行蛐裕栽跇?gòu)建容器時(shí)速度會(huì)比無序容器慢。list因?yàn)椴惶峁╇S機(jī)訪問迭代器，因此排序意義不大，需要需要借助其他容器完成拾取操作。hash_map、hash_set本身無法排序，需要借助別的容器。

3.元素刪除和插入

vector的刪除和插入操作代價(jià)是十分昂貴的，因?yàn)関ector中的元素都在內(nèi)存中連續(xù)排序，刪除和插入操作都可能影響到其他的元素，一般都需要移動(dòng)所操作元素后面所有的元素，而最壞的情況下，可能插入和刪除需要移動(dòng)整個(gè)容器中的所有的元素。而list、set、map和hash_map的刪除和插入操作都比較高效。但在刪除元素前，可能需要一次查找操作，而list的查找時(shí)間復(fù)雜度是線性時(shí)間，而set和map是對(duì)數(shù)時(shí)間，hash_map、hash_set是常數(shù)時(shí)間。

此外，考慮到網(wǎng)格的拓?fù)浣Y(jié)構(gòu)，元素刪除還有一些附帶的操作。刪除網(wǎng)格結(jié)點(diǎn)時(shí)，依賴該結(jié)點(diǎn)的網(wǎng)格邊和網(wǎng)格單元都將失效，需要一并刪除。同理，刪除網(wǎng)格邊時(shí)，需要同時(shí)刪除對(duì)應(yīng)的網(wǎng)格單元。因此，在元素刪除的操作中，還需要進(jìn)行查找關(guān)聯(lián)元素的操作。

4.查找關(guān)聯(lián)元素

查找關(guān)聯(lián)元素至少可以有三種實(shí)現(xiàn)方式：

（1）元素中儲(chǔ)存關(guān)聯(lián)元素的編號(hào)。

（2）元素中儲(chǔ)存關(guān)聯(lián)元素的指針。

（3）動(dòng)態(tài)的計(jì)算元素拓?fù)浣Y(jié)構(gòu)。

儲(chǔ)存關(guān)聯(lián)元素編號(hào)需要根據(jù)編號(hào)進(jìn)行一次查找操作。對(duì)于vector，如果簡(jiǎn)單的將數(shù)組下標(biāo)作為元素編號(hào)，則其能提供常數(shù)時(shí)間的查找操作。但這樣編號(hào)方式在元素變動(dòng)時(shí)難以維護(hù)編號(hào)的有效性，所以一般采取的方式是將編號(hào)內(nèi)置于元素本身。這種情況下，vector查找的時(shí)間復(fù)雜度為線性時(shí)間，與list相同。set和map能實(shí)現(xiàn)對(duì)數(shù)時(shí)間的查找，而hash_map、hash_set能實(shí)現(xiàn)常數(shù)時(shí)間的查找。此外，如果對(duì)vector按編號(hào)進(jìn)行排序，則其可以進(jìn)行對(duì)數(shù)時(shí)間的查找。

儲(chǔ)存指針則可以直接訪問關(guān)聯(lián)元素，效率很高，但指針的維護(hù)確比較繁瑣。

動(dòng)態(tài)的計(jì)算元素拓?fù)浣Y(jié)構(gòu)雖然可以節(jié)省儲(chǔ)存空間，但速度太慢，以時(shí)間換空間得不償失。

5.元素修改

網(wǎng)格元素屬性（如坐標(biāo)）應(yīng)當(dāng)是可修改的，而元素修改是在元素拾取的基礎(chǔ)上完成的。元素屬性修改除修改排序關(guān)鍵字外一般不會(huì)影響其他操作，而修改排序關(guān)鍵字會(huì)影響到元素的拾取。例如，當(dāng)修改某結(jié)點(diǎn)坐標(biāo)后，如果不更新用于元素拾取的序列，那么該對(duì)該結(jié)點(diǎn)的拾取操作就會(huì)出錯(cuò)。

對(duì)于vector而言，無論是直接修改后再重新排序還是先刪除元素再插入修改后的元素效率都比較低下。list本身刪除和插入操作都很快，但要找到刪除元素的位置卻依然需要線性時(shí)間的復(fù)雜度。另外list的拾取操作需要借助別的容器實(shí)現(xiàn)，所以元素修改的耗時(shí)需要根據(jù)完成拾取的排序容器來判斷。map和set都可以快速的刪除后再在特定位置快速插入新元素，僅需要對(duì)數(shù)時(shí)間的復(fù)雜度。需要注意的是，不能直接修改set中元素排序關(guān)鍵字，否則會(huì)出現(xiàn)未定義行為。hash_map、hash_set與list情況類似。

6總結(jié)

根據(jù)上述分析，我們首先可以確定實(shí)現(xiàn)查找關(guān)聯(lián)元素的方法：元素中儲(chǔ)存關(guān)聯(lián)元素的指針。這種方法保證了與網(wǎng)格拓?fù)浣Y(jié)構(gòu)相關(guān)操作的高效性，雖然過多的使用指針造成了程序易出錯(cuò)難維護(hù)的問題，但為了得到優(yōu)良的運(yùn)行效率，這些代價(jià)是值得的。

其次，可以排除map、hash_map。map、hash_map提供了鍵和值的映射結(jié)構(gòu)，但網(wǎng)格數(shù)據(jù)結(jié)構(gòu)中除了編號(hào)—元素映射以外，并不需要用到這種映射關(guān)系。而因?yàn)槲覀儾捎昧藘?chǔ)存關(guān)聯(lián)元素指針的方法，所以也不會(huì)用到編號(hào)—元素這一映射關(guān)系。

剩下的幾種容器，各有優(yōu)缺點(diǎn)，我們來用表格進(jìn)行對(duì)比。

從表中各項(xiàng)數(shù)據(jù)對(duì)比來看，set擁有最好的綜合性能。但set也有一些需要處理的問題。首先是排序關(guān)鍵字的選取。假定我們以結(jié)點(diǎn)橫坐標(biāo)為關(guān)鍵字，那么因?yàn)橥粰M坐標(biāo)下可能會(huì)有很多點(diǎn)，所以需要使用mutiset，以確保可以出現(xiàn)重復(fù)元素。選用橫坐標(biāo)為排序關(guān)鍵字，還會(huì)有另一個(gè)問題，因?yàn)榫W(wǎng)格數(shù)據(jù)是二維的，所以在極端情況下，僅有橫坐標(biāo)排序來完成元素拾取可能會(huì)出現(xiàn)效率問題，此時(shí)需要用另外一個(gè)容器來輔助拾取。其次，因?yàn)樵氐氖叭『驮匦薷亩贾饕窃诰W(wǎng)格結(jié)點(diǎn)上進(jìn)行的，網(wǎng)格邊和網(wǎng)格單元的相應(yīng)操作可以通過和網(wǎng)格節(jié)點(diǎn)的拓?fù)潢P(guān)系來完成，所以在不考慮這兩項(xiàng)操作時(shí)，set并不一定是最好的選擇。

最終，我們根據(jù)以上分析，可以設(shè)計(jì)出一個(gè)較優(yōu)的二維三角網(wǎng)格的數(shù)據(jù)結(jié)構(gòu)：

最后，用一個(gè)實(shí)際例子來測(cè)試軟件性能。下圖所示為對(duì)某流域的仿真計(jì)算結(jié)果，網(wǎng)格數(shù)目約為五十萬，淺綠色部分是選中的網(wǎng)格。實(shí)測(cè)軟件繪圖流暢，網(wǎng)格增加、刪除、修改、選取等操作均無頓卡現(xiàn)象。