[發(fā)明專利]排序數(shù)組元素以優(yōu)化數(shù)組修改的計(jì)算機(jī)系統(tǒng)及方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 01125741.5
• 申請(qǐng)日: 1998-01-06
• 公開(kāi)（公告）號(hào): CN1339744A
• 公開(kāi)（公告）日: 2002-03-13
• 發(fā)明（設(shè)計(jì)）人: R·E·約翰森
• 申請(qǐng)（專利權(quán)）人: 國(guó)際商業(yè)機(jī)器公司
• 主分類號(hào): G06F12/06
• 分類號(hào): G06F12/06
• 代理公司: 中國(guó)專利代理(香港)有限公司
• 代理人: 王勇,王忠忠

本發(fā)明總的來(lái)說(shuō)涉及計(jì)算機(jī)與數(shù)據(jù)處理系統(tǒng)中實(shí)現(xiàn)的數(shù)組數(shù)據(jù)結(jié)構(gòu)，特別是涉及在諸如存儲(chǔ)器壓縮的應(yīng)用中對(duì)數(shù)據(jù)結(jié)構(gòu)的操作。

數(shù)組是一種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，在計(jì)算機(jī)或其它數(shù)據(jù)處理系統(tǒng)中用來(lái)存儲(chǔ)數(shù)據(jù)。在數(shù)組數(shù)據(jù)結(jié)構(gòu)中通常把多個(gè)數(shù)組元素放到一個(gè)列表中，通過(guò)一個(gè)唯一的索引訪問(wèn)每個(gè)數(shù)組元素。例如，許多計(jì)算機(jī)存儲(chǔ)器系統(tǒng)都以數(shù)組來(lái)管理，各個(gè)存儲(chǔ)器單元或一組存儲(chǔ)器單元都可被作為數(shù)組元素，每一元素都有對(duì)之索引的唯一的一個(gè)存儲(chǔ)器地址。

使用數(shù)組數(shù)據(jù)結(jié)構(gòu)的最主要的優(yōu)點(diǎn)是它能隨機(jī)訪問(wèn)，比如能通過(guò)指向元素的指針或索引快速訪問(wèn)每一元素。但其缺點(diǎn)是很難有一種高效的方法對(duì)改變整個(gè)數(shù)組大小的修改進(jìn)行處理。特別是人們希望能對(duì)任一數(shù)據(jù)結(jié)構(gòu)進(jìn)行緊致存放，只利用所必須的存儲(chǔ)器空間。所以，一旦數(shù)組被修改，如刪除或增加元素，或者是對(duì)支持可變大小的數(shù)組元素的數(shù)組進(jìn)行修改，改變?cè)氐拇笮。诒恍薷脑睾蟮拿恳粋€(gè)元素通常也要修改或移動(dòng)其在內(nèi)存的位置。但是移動(dòng)數(shù)組元素是一個(gè)費(fèi)時(shí)的內(nèi)存?zhèn)鬏敳僮鳎瑥亩档痛鎯?chǔ)器系統(tǒng)的效率。

另外，每一個(gè)數(shù)組元素可以用未使用過(guò)的存儲(chǔ)單元來(lái)“填充”，因此可以在不影響數(shù)組中隨后元素的起始元素地址的情況下，允許元素“變大”或“縮小”。但是這種技術(shù)會(huì)由于數(shù)組中存在尚未使用的存儲(chǔ)器而極其浪費(fèi)。而且這種技術(shù)既無(wú)法適應(yīng)數(shù)組元素的刪除與增加，也無(wú)法對(duì)溢出了可用填充的較大的數(shù)組元素進(jìn)行修改。

數(shù)組一個(gè)重要的應(yīng)用是存儲(chǔ)器壓縮，這種應(yīng)用需要高存儲(chǔ)密度及快速的存儲(chǔ)器傳送操作。在一些存儲(chǔ)器壓縮應(yīng)用中，數(shù)據(jù)頁(yè)被安排成塊的數(shù)組，然后把塊壓縮成幀，以減少內(nèi)存占用量，在對(duì)壓縮的數(shù)據(jù)進(jìn)行修改后，再次對(duì)它們進(jìn)行壓縮。不論幀中的數(shù)據(jù)何時(shí)被修改，幀必須重新壓縮，這通常改變了幀大小及/或幀中存儲(chǔ)的信息量。該頁(yè)中跟在重新壓縮的幀之后的每一幀也通常被更新，例如移動(dòng)或重壓縮，從而優(yōu)化該頁(yè)的壓縮。當(dāng)存儲(chǔ)在靠近一頁(yè)的開(kāi)始的幀中的數(shù)據(jù)被修改時(shí)，通常該頁(yè)中絕大部分或所有幀都被更新，這對(duì)該存儲(chǔ)器系統(tǒng)中的總的性能有很顯著的影響。

因此減小修改數(shù)組中的元素所引起的性能降低是一個(gè)實(shí)際的問(wèn)題，特別是在存儲(chǔ)器壓縮或其它類似應(yīng)用中。

本發(fā)明解決現(xiàn)有技術(shù)中在提供維護(hù)數(shù)組的方式方面有關(guān)的這些以及其它問(wèn)題，該數(shù)組通常由一種排序算法對(duì)其元素進(jìn)行排序，該算法至少部分依賴于那些元素有可能被修改的所預(yù)測(cè)的頻率。具有較高修改頻率的數(shù)組元素放在靠近數(shù)組尾部的地方，以便響應(yīng)對(duì)這些元素的修改將通常需要更新的數(shù)組元素?cái)?shù)減至最小。對(duì)于那些具有較小修改可能性的數(shù)組元素，保留了需要更新較多數(shù)組元素的數(shù)組元素修改。這樣，響應(yīng)任一數(shù)組元素的修改需要更新的數(shù)組元素的平均數(shù)目，對(duì)于該數(shù)組在整體上減少了，從而減少了數(shù)組修改的整體性能影響。

本發(fā)明還不限于此，它的一個(gè)特殊的有益的應(yīng)用是在存儲(chǔ)器壓縮領(lǐng)域，這是因?yàn)猷徑鼉?nèi)存邏輯頁(yè)開(kāi)始位置的數(shù)據(jù)要比鄰近該頁(yè)末端位置的數(shù)據(jù)改變得頻繁。對(duì)于一個(gè)給定頁(yè)將數(shù)據(jù)塊以倒序排列，無(wú)論一個(gè)數(shù)據(jù)塊何時(shí)被修改，必須要被更新的塊的平均數(shù)減至最小。

突出本發(fā)明特征的這些以及其它優(yōu)點(diǎn)與特點(diǎn)在隨后的 提出，并作為其中的一部分。但為了更好地理解本發(fā)明及其通過(guò)其應(yīng)用所帶來(lái)的優(yōu)點(diǎn)及其特色，將參照附圖及說(shuō)明來(lái)描述本發(fā)明，其中描述了本發(fā)明的實(shí)施例。

圖1為描述一個(gè)數(shù)組中對(duì)元素進(jìn)行各種修改時(shí)的框圖。

圖2為一個(gè)計(jì)算機(jī)系統(tǒng)的框圖，它與本發(fā)明的原則相一致。

圖3是圖2中計(jì)算機(jī)系統(tǒng)的內(nèi)存映象框圖。

圖4是描述圖2計(jì)算機(jī)系統(tǒng)的內(nèi)存邏輯頁(yè)的框圖。

圖5是描述圖1中計(jì)算機(jī)系統(tǒng)的一個(gè)建立表的項(xiàng)與一個(gè)邏輯塊數(shù)組之間的映射框圖。

圖6是顯示對(duì)圖5中邏輯塊數(shù)組進(jìn)行了一種示例的數(shù)據(jù)修改后所得的結(jié)果的框圖。

本發(fā)明示意性實(shí)施例通常是通過(guò)對(duì)數(shù)值元素進(jìn)行排序來(lái)操作的，這種排序是根據(jù)預(yù)測(cè)的數(shù)組元素被修改的有關(guān)頻率進(jìn)行的，它允許修改數(shù)組元素，這種修改影響到數(shù)組尾部的后續(xù)元素，從而減少了由于修改數(shù)組中的任一給定元素而影響到的數(shù)組元素的平均數(shù)。特別是最好經(jīng)常維護(hù)在連續(xù)內(nèi)存空間的數(shù)組元素，在元素之間很少或幾乎沒(méi)有未使用的空間。從而減小數(shù)組占用的存儲(chǔ)量。應(yīng)該可以理解，一個(gè)數(shù)組的連續(xù)存儲(chǔ)空間在一定程度上可以是非連續(xù)的，即邏輯存儲(chǔ)位置可以被映射到固定大小的分區(qū)上，比如在隨后結(jié)合所示意的實(shí)施例所討論的壓縮數(shù)據(jù)分區(qū)所示出的。

對(duì)可以影響隨后數(shù)組元素的數(shù)組元素修改操作一般包括刪除數(shù)組元素及增加新的數(shù)組元素。而且，對(duì)于支持可變長(zhǎng)數(shù)組元素的數(shù)組來(lái)說(shuō)，另一種修改操作還包括改變數(shù)組元素的大小。