標準容器移動窗口式存儲異類無序對象

劉 健

（1.四川開放大學高職學院，四川 成都 610107；2.四川華新現(xiàn)代職業(yè)學院信息中心，四川 成都 610107）

0 引言

現(xiàn)已有多種存儲數(shù)據(jù)的常規(guī)算法，相關算法也在實踐應用中得到了證明和推廣。該文討論的算法涉及2個隊列：對象隊列和容器隊列，顯然不能簡單套用已有的普適性算法，必須在該基礎上進行改進。

現(xiàn)實生活中的實際需求不會一成不變，更不可能恰好匹配常規(guī)算法的要求。實際情況常需要綜合運用2個或多個常規(guī)算法，還要摻雜一些特殊要求。在現(xiàn)實的生產生活中，工作人員還可以借助通用型的工業(yè)軟件，通過半手工操作的方法來進行常規(guī)算法形式的運算，這種方法的效率極低。當遇到某些特殊需求時，這種半手工的方法就完全無法滿足要求。該文采用移動窗口的方式來消除若干個對象間的社會聯(lián)系，這是半手工方法根本不能勝任的任務。

1 背景介紹

該文討論的問題來源于一個經常出現(xiàn)的現(xiàn)象：人或物在一個特定的環(huán)境里按照一定的規(guī)則安排存放的位置或場地。這些人或物可以抽象為對象，若干個人或物就組成對象隊列。當然，這些人或物之間是要分類的，分類后就構成異類的對象隊列。當這些對象剛出現(xiàn)時，都是無序的。至于這些對象要存放的位置或場地就可以抽象為容器。因為人或物可能會經常更換，所以不能對這些對象有過多要求。而容器相對來說不會頻繁更換，可以按照特定的標準統(tǒng)一生產或配置。

2 前置條件

2.1 標準容器

所有容器都是標準化的容器，記為container（=1，2，…，），其容量記為capacity（=1，2，…，）。每個容器內部都劃分為若干個小格，稱為存儲格，記為cell（=1，2，…，；=1，2，…，capacity）。容器中存儲格的數(shù)量就是這個容器的容量。

每個容器內部的存儲格之間沒有區(qū)別，即尺寸、容量、和功能都一樣，而相同類型的容器與容器間在功能上也沒有區(qū)別，都可以存儲同類對象，這就是標準容器。標準容器利于存儲個體間有細小差異的同類對象。

2.2 對象和容器分類

對象有其自身的類型，根據(jù)對象類型的不同，對存儲格的要求也不同，于是就需要對存儲格進行分類。因為每個容器內的存儲格性質都相同，所以存儲格的類型就決定容器的類型。存儲格的類型與容器的類型一致，并與存儲對象的類型一致，如公式（1）所示。

式中：object_type（=1，2，…，）為對象的類型；cell_type（=1，2，…，）為存儲格類型；container_type（=1，2，…，）為容器的類型。

既然3個實體的類型都必須一致，那可以把3個類型都簡化為1個類型，如公式（2）所示。

式中：type（=1,2,…,）為3個類型統(tǒng)一。

當對象異類時，就需要異類容器去匹配相應類型的對象，以滿足相應的存儲要求。對象類型的數(shù)量決定容器類型的數(shù)量，這就解決了標準容器存儲異類對象的問題。

2.3 容器的容量

因為是標準容器，內部的存儲格必須一致，所以可以將相同類型容器的內部存儲格數(shù)量設定為相同，即同類容器的容量都一樣，這樣便于對容器進行生產和管理。這種情況是一種理想狀態(tài)，實踐的過程中很難滿足這種極端條件，如公式（3）所示。

式中：capacity為容器的容量，=1,2,…,。

由于容量都一致，因此可以簡單記為。

在實際運用中，因為現(xiàn)場地理條件等各種因素的影響，不一定只允許相同容量的容器存在，所以需要為每個容器設定自身的容量，此時各個capacity的值不盡相同。但每個容器的容量都不能超過標準容器的容量，即滿足公式（4）。

式中：為標準容器的容量；capacity為各個容器的容量，=1,2,…,。

2.4 容器的優(yōu)先級

雖然同類容器的功能一樣，但是實際每個容器的內部構成并不一定完全一致，只要滿足容器分類的標準即可。在使用的過程中，就需要對容器的使用順序進行排序。對每個容器指定一個優(yōu)先級，記為rank（=1，2，…，），優(yōu)先級別最高的最先使用，以rank為最高優(yōu)先級。當然也可以優(yōu)先級別最低的最先使用，這只需要倒序排序即可。在實際操作中，正序和倒序對結果沒有影響，簡單說就是排在最前的容器最先使用。

因為存在非標準容器，所以為保證標準容器優(yōu)先使用，就需要保證大容量容器的優(yōu)先級高于小容量容器，即滿足公式（5）。

式中：capacity（=1，2，…，）為排序后各個容器的容量。

2.5 異類無序對象的存在狀態(tài)

對象以批量的形式存在，即對象是整體出現(xiàn)或整體消亡的無序隊列，不是單個出現(xiàn)、逐個到達后形成隊列的。整個無序隊列存儲進標準容器后，再經過后續(xù)的相關階段，容器整體清空，待下個無序隊列存儲及使用。對象有批次的區(qū)分，各個批次之間有時間順序，不能同時存在。

對象隊列里存在各種類型的節(jié)點，因為是無序隊列，所以隊列里相鄰節(jié)點的類型不一定相同。當相鄰節(jié)點類型一致時，有可能出現(xiàn)若干個相鄰節(jié)點間的非技術性社會聯(lián)系。為消除這些社會聯(lián)系，就采用移動窗口式的手段使這些節(jié)點交錯分離，分別存儲在當前窗口內的若干個容器里，而不是連續(xù)存儲在同一個容器里。

3 存儲步驟

3.1 鎖定容器

在開始存儲對象前，必須鎖定現(xiàn)場所有容器，因為此時尚不知道當前對象的類型，所以是鎖定所有容器。鎖定后，不允許其他指令與該指令并行運行，即使是讀取存儲容器狀態(tài)也不行（后續(xù)的操作都具有嚴格的排他性）。

如果有2個指令集并行運行，就會出現(xiàn)臟數(shù)據(jù)，后續(xù)的操作結果都是臟數(shù)據(jù)。存儲對象的操作只能是串行運行的，即當某個操作指令集到達時，發(fā)現(xiàn)全部容器已經被排他性鎖定，只能等待前一個指令集操作完畢、釋放容器后，才能對容器進行鎖定操作。

3.2 判斷位置

在存儲列表中搜尋當前指令的對象是否已經存在存儲位置cell。如果有，就直接跳過后面的存儲流程，此時≠null并且≠null（1，1≤y≤capacity，null表示空）。如果沒有，就進入下面的存儲流程，當=null并且=null時，進入步驟3.3。

3.3 選擇對象匹配的容器類型

根據(jù)對象的類型選擇適合的容器類型，即根據(jù)type選擇類型一致的容器，拋棄不符合需求的容器。后續(xù)的操作都不再涉及容器類型的問題，因為此處已經作過類型篩選，只保留滿足需求的容器，所以默認的操作都是在同種類型的容器上完成的。

3.4 存儲對象

首先，設定1個窗口值，采用偽隨機的方式把連續(xù)的個對象平均分配到個容器里去，目的是切斷這些對象間的社會聯(lián)系。偽隨機的方式有很多種，為計算簡單、運行高效，目前采用的是取模方式，即根據(jù)對象的下標取模，把個對象分別依次存儲到個容器里，下一輪的個對象也一樣，后面的對象存儲方式以此類推，直到窗口所在位置的個容器全部填滿。此時，窗口向后移動，躍過當前的個容器，去覆蓋后面的個空閑容器。上一個窗口所在位置的個容器已經填滿，就處于關閉狀態(tài)。此時，窗口所在位置的容器還沒有存入對象，處于就緒狀態(tài)，等待下一個對象的到來。

這樣，看上去就像窗口在不停地移動，因此稱為移動窗口式存儲。理論上來說，的取值范圍為1 ~。當= 1時，全部容器根據(jù)優(yōu)先級依次使用，不存在偽隨機的存儲方式，也就不能發(fā)揮消除對象間社會聯(lián)系的作用。當=時，把全部的容器同時放在最大的一個窗口里，全部的容器同時處于就緒狀態(tài)，整個對象隊列會平均分配到全部的容器里。顯然，在實際操作中的取值不應該是兩頭的極限，即≠1并且≠。

此時，判斷存儲列表是否為空。如果為空，就進入步驟3.4.1；如果不為空，就進入步驟3.4.2。

當存儲列表為空時，就表明還沒有任何一個對象已經存儲到此類容器中，此類容器全部都是空閑狀態(tài)。因為容器已經事先根據(jù)優(yōu)先級排序，所以根據(jù)這類容器的優(yōu)先級別最高級rank把當前對象直接放在存儲列表的首位，即第1個容器container的第1個存儲格cell。因為是存儲列表的第1條信息，所以要單獨處理。

獲取存儲列表中存儲格cell的最大值，即和的最大值。因為存儲順序是根據(jù)容器的優(yōu)先級rank和容器內存儲格cell的排列次序執(zhí)行的，所以cell就是存儲列表末尾的那個值。

對進行的取模運算，即可獲得當前窗口的位置。當前窗口的第1個容器為container，如公式（6）所示。

式中：為當前窗口第1個容器的編號；為窗口的尺寸；為存儲列表末尾容器的編號。

當前窗口的最后1個容器為container，如公式（7）所示。式中：為當前窗口的最后1個容器的編號；為窗口的尺寸；為當前窗口第1個容器的編號。

不能簡單計為（+-1），當窗口移動到最后1個位置時，窗口內的容器數(shù)量有可能小于窗口的值，而且出現(xiàn)這種情況的概率非常高。在實際操作中，容器隊列的數(shù)量基本是固定的，而窗口是可變值。讓容器數(shù)量剛好為每個窗口的整數(shù)倍，這幾乎是不可能的事。

在確定和的值后，就可以確定當前窗口所在的位置。而container就是當前窗口里的當前容器，cell就是當前容器里的當前存儲格，當前對象就應該存儲在當前存儲格cell的“下一個位置”。這個“下一個位置”有可能是下一個容器的相同位置的存儲格cell，也有可能是當前窗口內第一個容器的下一個存儲格cell。

此時，對當前窗口內的所有容器進行遍歷查找，目的是尋找合適的存儲位置。以當前容器container為起始位置，獲得下一個容器container。如果container還有空余存儲格，即當capacity＞時，那么當前對象就存儲在容器container的存儲格cell里。如果container已經填滿，即當capacity=時，就獲取再下一個容器container。以此類推，直到查找到當前窗口里的最后一個容器container為止。

在完成此輪遍歷查找后，如果沒有尋找到合適的存儲位置，就表明當前窗口內當前容器后面的容器都已經填滿，能據(jù)此判斷這樣結果的原因就在于前置條件2.4的容量優(yōu)先級。既然這些容器已滿，那只能回到當前窗口的第1個容器container查詢空余位置。

如果container還有空余位置，即當capacity＞時，當前對象就存儲在容器container的存儲格cell 里。如果container也已經填滿，就表明當前窗口已滿，即整個窗口內的全部容器都已經填滿，只能移動到下一個窗口。當前對象就存儲在容器container的存儲格cell里，可以判斷當前窗口已滿的原因也是前置條件2.4的容量優(yōu)先級。

3.5 收斂窗口

當存儲操作達到閾值時，就要對窗口值進行收斂。這個閾值就是當窗口移動到最后一個位置，即在最后一個窗口內操作時，即為達到閾值?？梢杂脤ο笫Ｓ嗔颗c當前窗口的容量比較值作為標準，以判斷是否已經到達最后一個窗口，如公式（8）所示。

式中：為對象隊列的數(shù)量；capacity為第個容器的容量。

這時，就已經到達最后一個窗口。

由公式（8）可以推導出公式（9）、公式（10）。

由公式（10）可知，判斷標準更簡潔，從代碼的實現(xiàn)程度來說，難度也降低了。并且公式（10）的實際意義可以解釋為對象的數(shù)量小于窗口所覆蓋過的全部容器的存儲量的總和，包括最后一個窗口。窗口所覆蓋的全部容器不一定是整個容器隊列，其數(shù)量有可能比整個容器隊列的數(shù)量少。

此時，不再使用窗口的預設值，而是把窗口收縮到最小值，即設置= 1。收斂窗口的目的是在最后一個窗口內不作偽隨機的平鋪式存儲，而是根據(jù)容器的優(yōu)先級依次存儲。

如果繼續(xù)采用偽隨機的平鋪式存儲，那么必然會浪費最后一個窗口內容器的存儲空間（最后一個窗口內的全部容器都會處于半空狀態(tài)，即每個容器都存儲部分對象，同時還有空余存儲格）。

因為開啟容器就意味使用鏈條上的資源都必然配合開啟，所以半空狀態(tài)的容器必然也會浪費鏈條上、下游的資源。

在設置= 1后，則繼續(xù)步驟3.4.2，直至對象存儲完畢。整個流程如圖1所示。

圖1 存儲流程

4 應用實例

該文承載項目的單位每年舉行參與人數(shù)眾多的招錄考試，高峰時人數(shù)達到3 413人。該實例就以該數(shù)量為試驗數(shù)據(jù)進行演算?？傮w數(shù)據(jù)都處于無序狀態(tài)，形成1個沒有排序標準的無序隊列。每個個體都可以抽象為1個對象，全部的對象就形成無序對象隊列。其中，有效數(shù)據(jù)3 300個，無效數(shù)據(jù)113個。有效數(shù)據(jù)分2類，第Ⅰ類為3 179個，第Ⅱ類為121個。為對象安排位置就可以抽象為存儲進容器里的存儲格，該試驗容器準備情況為第Ⅰ類標準容器105個，容量都為30；第Ⅰ類非標準容器3個，容量分別為20、15和15；第Ⅱ類標準容器6個，容量都為30。

該實例采用SQL語言實現(xiàn)算法，形成存儲過程，再使用查詢語句逐個對象調用存儲過程，模擬工作人員逐個安排存儲位置。試驗環(huán)境為Interl Xeon CPU E5-2609 v2 @ 2.5GHz，Windows 2003，SQL Server 2005 SP4?？偣策M行10次試驗，每次的取值都為1~10，試驗耗時結果見表1。

表1 試驗耗時結果（單位：s）

上述結果表明，窗口值的浮動對運行時間的影響極小，每次運行的時間差異非常小，耗時差最大值也僅為58-48 = 10 s。這跟運行環(huán)境緊密相關，試驗的服務器同時運行多個虛擬機，因此其他虛擬機的服務對CPU、內存和硬盤的使用都會影響試驗結果。圖2可以更直觀地表述相關結果。

圖2 試驗耗時結果

通過上文可以得出結論：對窗口大小的設置不影響實用方案的選擇。根據(jù)多年的經驗積累，最終實際選擇

= 3。

無效數(shù)據(jù)基本都是信息不全造成的，在補齊信息后即可轉換為有效數(shù)據(jù)。因為前面3 300個有效數(shù)據(jù)已經安排完畢，所以此時不再由SQL查詢語句調用存儲過程，而是業(yè)務層通過業(yè)務邏輯層傳遞參數(shù)調用存儲過程，完成單個數(shù)據(jù)的存儲位置安排任務。

5 結語

該文所闡述的算法來源于普通的招考錄取社會現(xiàn)象，根據(jù)多年的實踐最終抽象為“標準容器存儲對象”的問題。

在解決該問題前，都采用傳統(tǒng)的人工方式分配位置。當對象數(shù)量大約為2 000個時，工作人員需要3個工作日才能完成任務，而且必須是全程只處理這一件事，不能同時處理其他事務。當對象數(shù)量大于3 000個時，通常工作人員需要4~5個工作日才能完成。在實際運行中，該流程所許用的時間常少于4個工作，工作人員必須在非工作時間繼續(xù)處理這個問題。

在提出該算法后，真正的處理時間小于1 min，提升了工作效率。即使是性能并不出眾的服務器仍然可以在非常短的時間內達到預期結果。