沈春元,張曉峰,李華君
(1.海軍駐南京地區(qū)雷達(dá)系統(tǒng)軍事代表室,南京 210003;2.中國船舶重工集團(tuán)公司第七二四研究所,南京 210003)
隨著計(jì)算機(jī)的不斷升級(jí),關(guān)于信息的插入大多數(shù)采用的是遍歷方式,在通常情況下很符合條件,其原理為:
(1)在信息庫中查找是否有相同標(biāo)識(shí)的信息,如果有轉(zhuǎn)到(3),否則轉(zhuǎn)到(2);
(2)查找是否有空閑的位置,如果有轉(zhuǎn)到(3),否則轉(zhuǎn)到(4);
(3)更新數(shù)據(jù)信息;
(4)滿信息后,采用處理方式。
此算法的時(shí)間復(fù)雜度為O(2n)。在實(shí)際處理過程中,信息量越來越大,在一些強(qiáng)實(shí)時(shí)情況下,采用上述的算法很難達(dá)到要求。
本文提出的快速插入與搜索算法(Quick Insert and Search Algorithm,簡寫QISA)QISA算法主要包括快速插入算法(QIA)和快速搜索算法(QSA)。
本文提出的快速插入算法(見圖1),主要是基于雙索引之上實(shí)時(shí)變化索引關(guān)系,快速達(dá)到空閑位置,其時(shí)間復(fù)雜度為O(1)。
圖1中,索引表A 存放索引表B的位置信息,索引表B 存放索引表A 對(duì)應(yīng)的位置信息,指針p為讀指針指向當(dāng)時(shí)可以寫的位置,指針q為寫指針指向索引表A中所要修改的位置。
圖1 快速插入算法
圖2 算法關(guān)系圖
算法流程如下:
(1)初始化p和q 指向索引表A中的A1的位置,索引表A與索引表B 一一對(duì)應(yīng),如圖1(b)所示;
(2)有信息輸入時(shí),直接索引到p所指定的位置,對(duì)應(yīng)的索引表B中的信息為B[p];
(3)第3個(gè)信息需要?jiǎng)h除時(shí)(圖2(a)),交換A[q]與A[Bi]中的位置信息,更新索引表A的值,其結(jié)果如圖2(b)所示。
搜索算法實(shí)際上是根據(jù)初始條件和擴(kuò)展規(guī)則構(gòu)造一顆“解答樹”并尋找符合目標(biāo)狀態(tài)的節(jié)點(diǎn)的過程。
圖3 樹形關(guān)系圖
由圖3所知,形成的一棵樹為搜索樹。初始狀態(tài)對(duì)應(yīng)著根節(jié)點(diǎn),目標(biāo)狀態(tài)對(duì)應(yīng)著目標(biāo)節(jié)點(diǎn),圖中的實(shí)線則為我們需要尋找的路徑。
本文采用的快速搜索算法(QSA)同樣是基于樹的關(guān)系之上,實(shí)時(shí)計(jì)算樹信息,為之后搜索的信息提供必要條件。
信息不同構(gòu)建搜索樹的方式也會(huì)不同,本文處理的信息主要是關(guān)于點(diǎn)跡、航跡的信息。根據(jù)此特征選取一個(gè)標(biāo)識(shí),確定此標(biāo)識(shí)為關(guān)鍵字,最后通過此標(biāo)識(shí)來檢索相關(guān)信息。其時(shí)間復(fù)雜度為O(L),其中L為標(biāo)識(shí)的復(fù)雜度,例如用4 位的標(biāo)識(shí)來確定關(guān)鍵字,那么L=4。
圖4 標(biāo)識(shí)分解樹
由圖4 可知,標(biāo)識(shí)為“知419”,在樹中表示為用實(shí)線箭頭表示的成功路徑。
算法流程如下:
(1)初始化樹的根節(jié)點(diǎn)、標(biāo)識(shí)有效信息;
(2)分解標(biāo)識(shí)信息;
(3)查找搜索樹,如果尋找到目標(biāo)節(jié)點(diǎn)轉(zhuǎn)到到(4),否則轉(zhuǎn)到到(5);
(4)更新目標(biāo)節(jié)點(diǎn)信息;
(5)添加目標(biāo)節(jié)點(diǎn)信息。
仿真環(huán)境配置:
CPU:Core i5系列、內(nèi)存:4G、操作系統(tǒng):Windows XP。
本文的仿真測試主要對(duì)20000 批內(nèi)的批數(shù)進(jìn)行抽樣測試,測試結(jié)果如圖5所示。
圖5 測試結(jié)果圖
由圖5(a)所知,如果信息的批數(shù)在1000 批以內(nèi)時(shí),通用的算法優(yōu)于本文的QISA,時(shí)間主要消耗在搜索樹的構(gòu)建上,其時(shí)間差也是控制在0.5 ms 以內(nèi)。由圖5(b)所知,當(dāng)批數(shù)大于1000 批時(shí),通用的算法時(shí)間會(huì)直線上升,QISA的耗時(shí)仍然是穩(wěn)步上升;如果把批數(shù)提高到20000 批時(shí),通用算法需要消耗約為477 ms,而QISA 則只需消耗約為20 ms的時(shí)間,如圖5(c)所示。詳細(xì)的數(shù)據(jù)對(duì)比結(jié)果如表1所示。
表1 QISA與通用結(jié)果對(duì)比
QISA 主要是采用了雙索引技術(shù),并構(gòu)建搜索樹的方式,實(shí)時(shí)為目標(biāo)信息分配索引位置,減少了重復(fù)遍歷搜索消耗的時(shí)間,提高了搜索速度。QISA的時(shí)間耗費(fèi)主要在于對(duì)搜索樹的建立、更新、刪除等的操作,關(guān)系到系統(tǒng)內(nèi)存的分配、更新、刪除的操作,對(duì)QISA的更深入的研究可以擴(kuò)展到內(nèi)存優(yōu)化的研究中。
[1]張水平.數(shù)據(jù)結(jié)構(gòu)及算法分析[M].西安:西北工業(yè)大學(xué)出版社,2003.
[2]夏定純,徐濤,等.人工智能技術(shù)與方法[M].武漢:華中科技大學(xué)出版社,2004.
[3]Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,Clifford Stein.Introduction to Algorithms[M].3rd Edition.The MIT Press,2009.