沈春元，張曉峰，李華君

(1.海軍駐南京地區(qū)雷達(dá)系統(tǒng)軍事代表室，南京 210003;2.中國船舶重工集團(tuán)公司第七二四研究所，南京 210003)

0 引言

隨著計(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 快速插入算法

本文提出的快速插入算法(見圖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）所示。

2 快速搜索算法

搜索算法實(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)信息。

3 結(jié)果與分析

仿真環(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ì)比

4 結(jié)束語

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.