外存儲算法中兩個數(shù)據(jù)結(jié)構(gòu)的設(shè)計研究.pdf

1、近年來,隨著信息科技的日益發(fā)展,人們已經(jīng)淹沒在數(shù)據(jù)的海洋里,各種各樣的數(shù)據(jù)充斥著人們的生活。其中一部分數(shù)據(jù)由于其數(shù)據(jù)量比較龐大,需要海量的存儲空間,而目前的計算機內(nèi)存空間不足以滿足這種需求,只能將其存儲在外存儲器中。因此處于內(nèi)外存之間傳輸數(shù)據(jù)的I/O通道就成為了制約算法運行效率的主要瓶頸。這種現(xiàn)象在如下幾個方面表現(xiàn)的尤為明顯,比如:空間數(shù)據(jù)庫中的海量幾何數(shù)據(jù)、數(shù)據(jù)庫、統(tǒng)計學、地理信息系統(tǒng)(GIS)、約束邏輯規(guī)劃、計算機圖形學、虛擬現(xiàn)實系

2、統(tǒng)等。由此產(chǎn)生了外存儲算法與數(shù)據(jù)結(jié)構(gòu)的設(shè)計和分析領(lǐng)域,其主要目標就是研究算法的有效性,以盡量減小程序運行過程中的輸入/輸出代價。
　　 本文首先研究了已有的適用于外存儲算法的數(shù)據(jù)結(jié)構(gòu)?；贔ibonacci堆在內(nèi)存儲算法中的特點,進一步改進得出了一種新的適合外存儲算法的數(shù)據(jù)結(jié)構(gòu),并分析了該數(shù)據(jù)結(jié)構(gòu)中各種操作的時間復雜度。并以這種數(shù)據(jù)結(jié)構(gòu)在Dijkstra算法中的應(yīng)用為實例證明了該數(shù)據(jù)結(jié)構(gòu)的可行性和有效性。
　　 其次,雙

3、端優(yōu)先級隊列是一種可同時支持針對最大、最小數(shù)據(jù)進行插入,刪除操作的數(shù)據(jù)結(jié)構(gòu),本文利用外存儲算法中對堆的研究,設(shè)計了一種新的適合外存儲算法的雙端優(yōu)先級隊列。并分析它的操作復雜度,其中除查找操作具有單位時間的頁面置換次數(shù)以外,其他操作都具有對數(shù)時間的頁面置換次數(shù)。最后借助網(wǎng)絡(luò)傳輸中的包緩存實現(xiàn)了該數(shù)據(jù)結(jié)構(gòu)在外存中的應(yīng)用。
　　 本文的創(chuàng)新點主要包括以下兩個方面:
　　 (1)針對外存儲算法中的數(shù)據(jù)結(jié)構(gòu)問題,目前還沒有支持單位

4、時間操作復雜度的外存儲算法。本文根據(jù)Fibonacci堆在內(nèi)存儲算法中的特點,設(shè)計出了一種針對海量數(shù)據(jù)支持單位時間操作復雜度的外存儲算法。并通過實例證明了算法的可行性和有效性。
　　 (2)基于外存儲算法中對堆的研究,經(jīng)過一些改進得到了一種新的適應(yīng)于外存儲算法的雙端優(yōu)先級隊列。該數(shù)據(jù)結(jié)構(gòu)可以同時支持針對最大、最小數(shù)據(jù)的查找,刪除操作。并且其查找操作的頁面置換次數(shù)為O(1),其他操作的頁面置換次數(shù)為O(logN)。通過這種數(shù)據(jù)結(jié)構(gòu)