2007年6月17日
#
前些天在做一個(gè)小項(xiàng)目，需要實(shí)現(xiàn)從字符串到XML文件的逆向轉(zhuǎn)換過(guò)程。該字符串由XML文件所得。由于使用環(huán)境對(duì)解析時(shí)間和內(nèi)存使用量有嚴(yán)格的要求，因此必須確保解析速度和所占用內(nèi)存。
下面簡(jiǎn)單敘述一下我的實(shí)現(xiàn)過(guò)程。最開(kāi)始采用的方法是每次從文件字符串里面讀入一個(gè)節(jié)點(diǎn)的值，具體讀取過(guò)程有xml文件各個(gè)節(jié)點(diǎn)屬性決定。再利用一個(gè)stack對(duì)xml文件節(jié)點(diǎn)進(jìn)行管理。大致思路是每讀入一個(gè)字符串，先判斷其類型，如果是Element或者text, comment, cdata類型則入棧，若為EndElement則出棧，這樣就可以順利建立起各個(gè)父子節(jié)點(diǎn)之間的關(guān)系。
采用這樣的方法是思路比較的明確，實(shí)現(xiàn)起來(lái)比較的簡(jiǎn)單，缺點(diǎn)是解析速度太慢了，解析一個(gè)2M左右的XML文件要10多分鐘，而且所費(fèi)時(shí)間與文件的大小成幾何級(jí)別增長(zhǎng)，根本不可能接受。在采用這種方法過(guò)程中，也出現(xiàn)了一個(gè)小插曲。就是在解析比較大的xml文件時(shí)，當(dāng)解析的xml節(jié)點(diǎn)超過(guò)1500個(gè)時(shí)，就會(huì)導(dǎo)致內(nèi)存分配錯(cuò)誤，堆棧溢出，開(kāi)始是百思不得其解，后來(lái)才知道是由于我在解析字符串過(guò)程中，采用了遞歸的方法，因此內(nèi)存消耗很厲害，特別是我開(kāi)始傳入一個(gè)const字符串時(shí)，一個(gè)小小的幾百K(以200k為例)的文件就可能導(dǎo)致內(nèi)存一下子消耗幾百M(fèi)，因?yàn)槊看沃蛔x入一個(gè)節(jié)點(diǎn)字符串，這樣最終大小可以達(dá)到200K+19.96k+....+0 ~=200*(200-1)k/2~ = 200M.因此導(dǎo)致編譯器堆棧溢出，解決方法有幾種，一是將堆棧設(shè)置大些，另外就是改遞歸為循環(huán)。我采用了后者。
在進(jìn)行字符串解析時(shí)，我大量采用了STL的字符串find,find_first_of()，substr等
函數(shù)，但是這通常只在搜索小字符串時(shí)速度較快，在長(zhǎng)達(dá)幾M的字符串時(shí)，由于大塊的內(nèi)存操作，程序運(yùn)行慢如蝸牛。而且我在前面的實(shí)現(xiàn)方法中，每次是提取一個(gè)節(jié)點(diǎn)，然后再進(jìn)行解析，這樣在讀取和解析過(guò)程中，會(huì)導(dǎo)致許多重復(fù)的步驟，嚴(yán)重影響工作效率。 于是我就采用一個(gè)了for循環(huán)對(duì)讀入的一個(gè)個(gè)字節(jié)進(jìn)行處理，這樣速度得到顯著的提高。但是程序在解析大字符串時(shí)還是運(yùn)行很慢，我開(kāi)始 意識(shí)到是長(zhǎng)字符串的問(wèn)題，因此得想方法分段解析才行。于是決定每次從字符串里面提取一定的字符處理。在解析長(zhǎng)達(dá)幾M的字符串時(shí)，我先后試驗(yàn)了每次提取64bit，128bit，256bit,512bit, 1k, 2k, 4k等不同長(zhǎng)度的字符串，發(fā)現(xiàn)在處理大字符串時(shí)，4K的效果最好。在解析一個(gè)8M左右的xml字符串時(shí)，速度可以達(dá)到30S，但是內(nèi)存消耗有點(diǎn)厲害了，達(dá)100M。因此也很難滿足要求。
最后還是采用了一種比較折中的方法，就是在初次解析時(shí)，只解析根節(jié)點(diǎn)以及其下一層子節(jié)點(diǎn)，在保存過(guò)程中再分段解析，主要可以極大的減少內(nèi)存消耗，8M左右的文件可以降低到20M左右內(nèi)存。速度也有所提高,最終耗時(shí)3s左右。
2007年5月3日
#
In these days, I used STL in a project, and met several problems. One was caused by erase method. As we know, when we delete a element in a container in STL, the iterator itself will be changed, so the the iterator should be set correctly. A right method can be used as following:
Typedef list<MyClass*>::Iterator myIter;
for(myIter it = listObj.begin(); it != listObj.end();)
if(true)
it = listObj.erase(it);
else
++it;
最近因?yàn)轫?xiàng)目的需要，將一個(gè)應(yīng)用軟件的底層X(jué)ML處理模塊進(jìn)行重寫，由MSDOM改用xmlLite來(lái)完成。XmlLite是微軟專門針對(duì)C++使用者開(kāi)發(fā)的一個(gè)輕量級(jí)開(kāi)發(fā)包，只具備基本的I/O功能。提供了IXmlReader, IXmlWriter對(duì)XML文件進(jìn)行簡(jiǎn)單的讀寫操作。原理很簡(jiǎn)單，在讀一個(gè)文件時(shí)，循環(huán)讀取各個(gè)節(jié)點(diǎn)，然后根據(jù)不同的節(jié)點(diǎn)類型讀取其相關(guān)屬性數(shù)據(jù)等。XMLLite中的數(shù)據(jù)類型主要封裝在XmlNodeType中，常使用到的有XmlNodeType_None, XmlNodeType_Element,XmlNodeType_EndElement等。在寫數(shù)據(jù)時(shí)，主要根據(jù)不同的節(jié)點(diǎn)類型，調(diào)用相關(guān)的API來(lái)完成。值得注意的是，由于XMLLite只提供順序化寫的功能，因此在寫具有多個(gè)深度的節(jié)點(diǎn)類型時(shí)，需要控制好WriteEndElement()函數(shù)的出現(xiàn)順序等，所以這些都可以通過(guò)函數(shù)的遞歸來(lái)完成。
由于XmlLite只提供簡(jiǎn)單的讀寫等功能，因此，在實(shí)際應(yīng)用中，需要對(duì)XMLLite提供的功能進(jìn)行一定的封裝，從而提供自己的API功能。下面簡(jiǎn)單說(shuō)說(shuō)我們采用的思路。在讀Xml文件時(shí)，需要在加載過(guò)程建立XML文件的內(nèi)部數(shù)據(jù)結(jié)構(gòu)。這可以通過(guò)兩種方式來(lái)完成，一種是在一個(gè)循環(huán)或者遞歸過(guò)程中，將整個(gè)ＸＭＬｌｏａｄ進(jìn)來(lái)；另外一種方法是一次只加載一層節(jié)點(diǎn)，然后遞歸加載其子節(jié)點(diǎn)。前面一種方法是在處理大XML文件時(shí)，可能會(huì)有memory footprint問(wèn)題。所以最終采用了后面的方法。
在實(shí)現(xiàn)過(guò)程中，我們采用了composite模式來(lái)組織XML文件樹(shù)結(jié)構(gòu)。通過(guò)使用list來(lái)建立樹(shù)結(jié)構(gòu)。全部操作封裝在一個(gè)類中。
有關(guān)相關(guān)原因，xmlLite的具體封裝實(shí)現(xiàn)方法就不提及了。開(kāi)發(fā)過(guò)程中，遇到的主要難點(diǎn)是數(shù)據(jù)的讀寫和保存，關(guān)鍵是數(shù)據(jù)結(jié)構(gòu)的處理，其他部分都比較容易。
這我開(kāi)通blog后的第一篇文章，呵呵，也不知道怎么寫好。以后會(huì)盡力寫好點(diǎn)^_^.