標(biāo)準(zhǔn)容器移動窗口式存儲異類無序?qū)ο?/h1>
2022-10-09 11:17劉健
中國新技術(shù)新產(chǎn)品 2022年13期
劉 健
（1.四川開放大學(xué)高職學(xué)院，四川 成都 610107；2.四川華新現(xiàn)代職業(yè)學(xué)院信息中心，四川 成都 610107）
0 引言
現(xiàn)已有多種存儲數(shù)據(jù)的常規(guī)算法，相關(guān)算法也在實(shí)踐應(yīng)用中得到了證明和推廣。該文討論的算法涉及2個隊(duì)列：對象隊(duì)列和容器隊(duì)列，顯然不能簡單套用已有的普適性算法，必須在該基礎(chǔ)上進(jìn)行改進(jìn)。
現(xiàn)實(shí)生活中的實(shí)際需求不會一成不變，更不可能恰好匹配常規(guī)算法的要求。實(shí)際情況常需要綜合運(yùn)用2個或多個常規(guī)算法，還要摻雜一些特殊要求。在現(xiàn)實(shí)的生產(chǎn)生活中，工作人員還可以借助通用型的工業(yè)軟件，通過半手工操作的方法來進(jìn)行常規(guī)算法形式的運(yùn)算，這種方法的效率極低。當(dāng)遇到某些特殊需求時，這種半手工的方法就完全無法滿足要求。該文采用移動窗口的方式來消除若干個對象間的社會聯(lián)系，這是半手工方法根本不能勝任的任務(wù)。
1 背景介紹
該文討論的問題來源于一個經(jīng)常出現(xiàn)的現(xiàn)象：人或物在一個特定的環(huán)境里按照一定的規(guī)則安排存放的位置或場地。這些人或物可以抽象為對象，若干個人或物就組成對象隊(duì)列。當(dāng)然，這些人或物之間是要分類的，分類后就構(gòu)成異類的對象隊(duì)列。當(dāng)這些對象剛出現(xiàn)時，都是無序的。至于這些對象要存放的位置或場地就可以抽象為容器。因?yàn)槿嘶蛭锟赡軙?jīng)常更換，所以不能對這些對象有過多要求。而容器相對來說不會頻繁更換，可以按照特定的標(biāo)準(zhǔn)統(tǒng)一生產(chǎn)或配置。
2 前置條件
2.1 標(biāo)準(zhǔn)容器
所有容器都是標(biāo)準(zhǔn)化的容器，記為container（=1，2，…，），其容量記為capacity（=1，2，…，）。每個容器內(nèi)部都劃分為若干個小格，稱為存儲格，記為cell（=1，2，…，；=1，2，…，capacity）。容器中存儲格的數(shù)量就是這個容器的容量。
每個容器內(nèi)部的存儲格之間沒有區(qū)別，即尺寸、容量、和功能都一樣，而相同類型的容器與容器間在功能上也沒有區(qū)別，都可以存儲同類對象，這就是標(biāo)準(zhǔn)容器。標(biāo)準(zhǔn)容器利于存儲個體間有細(xì)小差異的同類對象。
2.2 對象和容器分類
對象有其自身的類型，根據(jù)對象類型的不同，對存儲格的要求也不同，于是就需要對存儲格進(jìn)行分類。因?yàn)槊總€容器內(nèi)的存儲格性質(zhì)都相同，所以存儲格的類型就決定容器的類型。存儲格的類型與容器的類型一致，并與存儲對象的類型一致，如公式（1）所示。
式中：object_type（=1，2，…，）為對象的類型；cell_type（=1，2，…，）為存儲格類型；container_type（=1，2，…，）為容器的類型。
既然3個實(shí)體的類型都必須一致，那可以把3個類型都簡化為1個類型，如公式（2）所示。
式中：type（=1,2,…,）為3個類型統(tǒng)一。
當(dāng)對象異類時，就需要異類容器去匹配相應(yīng)類型的對象，以滿足相應(yīng)的存儲要求。對象類型的數(shù)量決定容器類型的數(shù)量，這就解決了標(biāo)準(zhǔn)容器存儲異類對象的問題。
2.3 容器的容量
因?yàn)槭菢?biāo)準(zhǔn)容器，內(nèi)部的存儲格必須一致，所以可以將相同類型容器的內(nèi)部存儲格數(shù)量設(shè)定為相同，即同類容器的容量都一樣，這樣便于對容器進(jìn)行生產(chǎn)和管理。這種情況是一種理想狀態(tài)，實(shí)踐的過程中很難滿足這種極端條件，如公式（3）所示。
式中：capacity為容器的容量，=1,2,…,。
由于容量都一致，因此可以簡單記為。
在實(shí)際運(yùn)用中，因?yàn)楝F(xiàn)場地理?xiàng)l件等各種因素的影響，不一定只允許相同容量的容器存在，所以需要為每個容器設(shè)定自身的容量，此時各個capacity的值不盡相同。但每個容器的容量都不能超過標(biāo)準(zhǔn)容器的容量，即滿足公式（4）。
式中：為標(biāo)準(zhǔn)容器的容量；capacity為各個容器的容量，=1,2,…,。
2.4 容器的優(yōu)先級
雖然同類容器的功能一樣，但是實(shí)際每個容器的內(nèi)部構(gòu)成并不一定完全一致，只要滿足容器分類的標(biāo)準(zhǔn)即可。在使用的過程中，就需要對容器的使用順序進(jìn)行排序。對每個容器指定一個優(yōu)先級，記為rank（=1，2，…，），優(yōu)先級別最高的最先使用，以rank為最高優(yōu)先級。當(dāng)然也可以優(yōu)先級別最低的最先使用，這只需要倒序排序即可。在實(shí)際操作中，正序和倒序?qū)Y(jié)果沒有影響，簡單說就是排在最前的容器最先使用。
因?yàn)榇嬖诜菢?biāo)準(zhǔn)容器，所以為保證標(biāo)準(zhǔn)容器優(yōu)先使用，就需要保證大容量容器的優(yōu)先級高于小容量容器，即滿足公式（5）。
式中：capacity（=1，2，…，）為排序后各個容器的容量。
2.5 異類無序?qū)ο蟮拇嬖跔顟B(tài)
對象以批量的形式存在，即對象是整體出現(xiàn)或整體消亡的無序隊(duì)列，不是單個出現(xiàn)、逐個到達(dá)后形成隊(duì)列的。整個無序隊(duì)列存儲進(jìn)標(biāo)準(zhǔn)容器后，再經(jīng)過后續(xù)的相關(guān)階段，容器整體清空，待下個無序隊(duì)列存儲及使用。對象有批次的區(qū)分，各個批次之間有時間順序，不能同時存在。
對象隊(duì)列里存在各種類型的節(jié)點(diǎn)，因?yàn)槭菬o序隊(duì)列，所以隊(duì)列里相鄰節(jié)點(diǎn)的類型不一定相同。當(dāng)相鄰節(jié)點(diǎn)類型一致時，有可能出現(xiàn)若干個相鄰節(jié)點(diǎn)間的非技術(shù)性社會聯(lián)系。為消除這些社會聯(lián)系，就采用移動窗口式的手段使這些節(jié)點(diǎn)交錯分離，分別存儲在當(dāng)前窗口內(nèi)的若干個容器里，而不是連續(xù)存儲在同一個容器里。
3 存儲步驟
3.1 鎖定容器
在開始存儲對象前，必須鎖定現(xiàn)場所有容器，因?yàn)榇藭r尚不知道當(dāng)前對象的類型，所以是鎖定所有容器。鎖定后，不允許其他指令與該指令并行運(yùn)行，即使是讀取存儲容器狀態(tài)也不行（后續(xù)的操作都具有嚴(yán)格的排他性）。
如果有2個指令集并行運(yùn)行，就會出現(xiàn)臟數(shù)據(jù)，后續(xù)的操作結(jié)果都是臟數(shù)據(jù)。存儲對象的操作只能是串行運(yùn)行的，即當(dāng)某個操作指令集到達(dá)時，發(fā)現(xiàn)全部容器已經(jīng)被排他性鎖定，只能等待前一個指令集操作完畢、釋放容器后，才能對容器進(jìn)行鎖定操作。
3.2 判斷位置
在存儲列表中搜尋當(dāng)前指令的對象是否已經(jīng)存在存儲位置cell。如果有，就直接跳過后面的存儲流程，此時≠null并且≠null（1，1≤y≤capacity，null表示空）。如果沒有，就進(jìn)入下面的存儲流程，當(dāng)=null并且=null時，進(jìn)入步驟3.3。
3.3 選擇對象匹配的容器類型
根據(jù)對象的類型選擇適合的容器類型，即根據(jù)type選擇類型一致的容器，拋棄不符合需求的容器。后續(xù)的操作都不再涉及容器類型的問題，因?yàn)榇颂幰呀?jīng)作過類型篩選，只保留滿足需求的容器，所以默認(rèn)的操作都是在同種類型的容器上完成的。
3.4 存儲對象
首先，設(shè)定1個窗口值，采用偽隨機(jī)的方式把連續(xù)的個對象平均分配到個容器里去，目的是切斷這些對象間的社會聯(lián)系。偽隨機(jī)的方式有很多種，為計(jì)算簡單、運(yùn)行高效，目前采用的是取模方式，即根據(jù)對象的下標(biāo)取模，把個對象分別依次存儲到個容器里，下一輪的個對象也一樣，后面的對象存儲方式以此類推，直到窗口所在位置的個容器全部填滿。此時，窗口向后移動，躍過當(dāng)前的個容器，去覆蓋后面的個空閑容器。上一個窗口所在位置的個容器已經(jīng)填滿，就處于關(guān)閉狀態(tài)。此時，窗口所在位置的容器還沒有存入對象，處于就緒狀態(tài)，等待下一個對象的到來。
這樣，看上去就像窗口在不停地移動，因此稱為移動窗口式存儲。理論上來說，的取值范圍為1 ~。當(dāng)= 1時，全部容器根據(jù)優(yōu)先級依次使用，不存在偽隨機(jī)的存儲方式，也就不能發(fā)揮消除對象間社會聯(lián)系的作用。當(dāng)=時，把全部的容器同時放在最大的一個窗口里，全部的容器同時處于就緒狀態(tài)，整個對象隊(duì)列會平均分配到全部的容器里。顯然，在實(shí)際操作中的取值不應(yīng)該是兩頭的極限，即≠1并且≠。
此時，判斷存儲列表是否為空。如果為空，就進(jìn)入步驟3.4.1；如果不為空，就進(jìn)入步驟3.4.2。
當(dāng)存儲列表為空時，就表明還沒有任何一個對象已經(jīng)存儲到此類容器中，此類容器全部都是空閑狀態(tài)。因?yàn)槿萜饕呀?jīng)事先根據(jù)優(yōu)先級排序，所以根據(jù)這類容器的優(yōu)先級別最高級rank把當(dāng)前對象直接放在存儲列表的首位，即第1個容器container的第1個存儲格cell。因?yàn)槭谴鎯α斜淼牡?條信息，所以要單獨(dú)處理。
獲取存儲列表中存儲格cell的最大值，即和的最大值。因?yàn)榇鎯樞蚴歉鶕?jù)容器的優(yōu)先級rank和容器內(nèi)存儲格cell的排列次序執(zhí)行的，所以cell就是存儲列表末尾的那個值。
對進(jìn)行的取模運(yùn)算，即可獲得當(dāng)前窗口的位置。當(dāng)前窗口的第1個容器為container，如公式（6）所示。
式中：為當(dāng)前窗口第1個容器的編號；為窗口的尺寸；為存儲列表末尾容器的編號。
當(dāng)前窗口的最后1個容器為container，如公式（7）所示。式中：為當(dāng)前窗口的最后1個容器的編號；為窗口的尺寸；為當(dāng)前窗口第1個容器的編號。
不能簡單計(jì)為（+-1），當(dāng)窗口移動到最后1個位置時，窗口內(nèi)的容器數(shù)量有可能小于窗口的值，而且出現(xiàn)這種情況的概率非常高。在實(shí)際操作中，容器隊(duì)列的數(shù)量基本是固定的，而窗口是可變值。讓容器數(shù)量剛好為每個窗口的整數(shù)倍，這幾乎是不可能的事。
在確定和的值后，就可以確定當(dāng)前窗口所在的位置。而container就是當(dāng)前窗口里的當(dāng)前容器，cell就是當(dāng)前容器里的當(dāng)前存儲格，當(dāng)前對象就應(yīng)該存儲在當(dāng)前存儲格cell的“下一個位置”。這個“下一個位置”有可能是下一個容器的相同位置的存儲格cell，也有可能是當(dāng)前窗口內(nèi)第一個容器的下一個存儲格cell。
此時，對當(dāng)前窗口內(nèi)的所有容器進(jìn)行遍歷查找，目的是尋找合適的存儲位置。以當(dāng)前容器container為起始位置，獲得下一個容器container。如果container還有空余存儲格，即當(dāng)capacity＞時，那么當(dāng)前對象就存儲在容器container的存儲格cell里。如果container已經(jīng)填滿，即當(dāng)capacity=時，就獲取再下一個容器container。以此類推，直到查找到當(dāng)前窗口里的最后一個容器container為止。
在完成此輪遍歷查找后，如果沒有尋找到合適的存儲位置，就表明當(dāng)前窗口內(nèi)當(dāng)前容器后面的容器都已經(jīng)填滿，能據(jù)此判斷這樣結(jié)果的原因就在于前置條件2.4的容量優(yōu)先級。既然這些容器已滿，那只能回到當(dāng)前窗口的第1個容器container查詢空余位置。
如果container還有空余位置，即當(dāng)capacity＞時，當(dāng)前對象就存儲在容器container的存儲格cell 里。如果container也已經(jīng)填滿，就表明當(dāng)前窗口已滿，即整個窗口內(nèi)的全部容器都已經(jīng)填滿，只能移動到下一個窗口。當(dāng)前對象就存儲在容器container的存儲格cell里，可以判斷當(dāng)前窗口已滿的原因也是前置條件2.4的容量優(yōu)先級。
3.5 收斂窗口
當(dāng)存儲操作達(dá)到閾值時，就要對窗口值進(jìn)行收斂。這個閾值就是當(dāng)窗口移動到最后一個位置，即在最后一個窗口內(nèi)操作時，即為達(dá)到閾值?？梢杂脤ο笫Ｓ嗔颗c當(dāng)前窗口的容量比較值作為標(biāo)準(zhǔn)，以判斷是否已經(jīng)到達(dá)最后一個窗口，如公式（8）所示。
式中：為對象隊(duì)列的數(shù)量；capacity為第個容器的容量。
這時，就已經(jīng)到達(dá)最后一個窗口。
由公式（8）可以推導(dǎo)出公式（9）、公式（10）。
由公式（10）可知，判斷標(biāo)準(zhǔn)更簡潔，從代碼的實(shí)現(xiàn)程度來說，難度也降低了。并且公式（10）的實(shí)際意義可以解釋為對象的數(shù)量小于窗口所覆蓋過的全部容器的存儲量的總和，包括最后一個窗口。窗口所覆蓋的全部容器不一定是整個容器隊(duì)列，其數(shù)量有可能比整個容器隊(duì)列的數(shù)量少。
此時，不再使用窗口的預(yù)設(shè)值，而是把窗口收縮到最小值，即設(shè)置= 1。收斂窗口的目的是在最后一個窗口內(nèi)不作偽隨機(jī)的平鋪式存儲，而是根據(jù)容器的優(yōu)先級依次存儲。
如果繼續(xù)采用偽隨機(jī)的平鋪式存儲，那么必然會浪費(fèi)最后一個窗口內(nèi)容器的存儲空間（最后一個窗口內(nèi)的全部容器都會處于半空狀態(tài)，即每個容器都存儲部分對象，同時還有空余存儲格）。
因?yàn)殚_啟容器就意味使用鏈條上的資源都必然配合開啟，所以半空狀態(tài)的容器必然也會浪費(fèi)鏈條上、下游的資源。
在設(shè)置= 1后，則繼續(xù)步驟3.4.2，直至對象存儲完畢。整個流程如圖1所示。
圖1 存儲流程
4 應(yīng)用實(shí)例
該文承載項(xiàng)目的單位每年舉行參與人數(shù)眾多的招錄考試，高峰時人數(shù)達(dá)到3 413人。該實(shí)例就以該數(shù)量為試驗(yàn)數(shù)據(jù)進(jìn)行演算?？傮w數(shù)據(jù)都處于無序狀態(tài)，形成1個沒有排序標(biāo)準(zhǔn)的無序隊(duì)列。每個個體都可以抽象為1個對象，全部的對象就形成無序?qū)ο箨?duì)列。其中，有效數(shù)據(jù)3 300個，無效數(shù)據(jù)113個。有效數(shù)據(jù)分2類，第Ⅰ類為3 179個，第Ⅱ類為121個。為對象安排位置就可以抽象為存儲進(jìn)容器里的存儲格，該試驗(yàn)容器準(zhǔn)備情況為第Ⅰ類標(biāo)準(zhǔn)容器105個，容量都為30；第Ⅰ類非標(biāo)準(zhǔn)容器3個，容量分別為20、15和15；第Ⅱ類標(biāo)準(zhǔn)容器6個，容量都為30。
該實(shí)例采用SQL語言實(shí)現(xiàn)算法，形成存儲過程，再使用查詢語句逐個對象調(diào)用存儲過程，模擬工作人員逐個安排存儲位置。試驗(yàn)環(huán)境為Interl Xeon CPU E5-2609 v2 @ 2.5GHz，Windows 2003，SQL Server 2005 SP4。總共進(jìn)行10次試驗(yàn)，每次的取值都為1~10，試驗(yàn)耗時結(jié)果見表1。
表1 試驗(yàn)耗時結(jié)果（單位：s）
上述結(jié)果表明，窗口值的浮動對運(yùn)行時間的影響極小，每次運(yùn)行的時間差異非常小，耗時差最大值也僅為58-48 = 10 s。這跟運(yùn)行環(huán)境緊密相關(guān)，試驗(yàn)的服務(wù)器同時運(yùn)行多個虛擬機(jī)，因此其他虛擬機(jī)的服務(wù)對CPU、內(nèi)存和硬盤的使用都會影響試驗(yàn)結(jié)果。圖2可以更直觀地表述相關(guān)結(jié)果。
圖2 試驗(yàn)耗時結(jié)果
通過上文可以得出結(jié)論：對窗口大小的設(shè)置不影響實(shí)用方案的選擇。根據(jù)多年的經(jīng)驗(yàn)積累，最終實(shí)際選擇
= 3。
無效數(shù)據(jù)基本都是信息不全造成的，在補(bǔ)齊信息后即可轉(zhuǎn)換為有效數(shù)據(jù)。因?yàn)榍懊? 300個有效數(shù)據(jù)已經(jīng)安排完畢，所以此時不再由SQL查詢語句調(diào)用存儲過程，而是業(yè)務(wù)層通過業(yè)務(wù)邏輯層傳遞參數(shù)調(diào)用存儲過程，完成單個數(shù)據(jù)的存儲位置安排任務(wù)。
5 結(jié)語
該文所闡述的算法來源于普通的招考錄取社會現(xiàn)象，根據(jù)多年的實(shí)踐最終抽象為“標(biāo)準(zhǔn)容器存儲對象”的問題。
在解決該問題前，都采用傳統(tǒng)的人工方式分配位置。當(dāng)對象數(shù)量大約為2 000個時，工作人員需要3個工作日才能完成任務(wù)，而且必須是全程只處理這一件事，不能同時處理其他事務(wù)。當(dāng)對象數(shù)量大于3 000個時，通常工作人員需要4~5個工作日才能完成。在實(shí)際運(yùn)行中，該流程所許用的時間常少于4個工作，工作人員必須在非工作時間繼續(xù)處理這個問題。
在提出該算法后，真正的處理時間小于1 min，提升了工作效率。即使是性能并不出眾的服務(wù)器仍然可以在非常短的時間內(nèi)達(dá)到預(yù)期結(jié)果。
猜你喜歡
車身無序堆疊零件自動抓取系統(tǒng)汽車實(shí)用技術(shù)(2022年14期)2022-07-30 Different Containers不同的容器閱讀（快樂英語中年級）(2022年11期)2022-05-30 隊(duì)列里的小秘密小學(xué)生學(xué)習(xí)指導(dǎo)(低年級)(2020年4期)2020-06-02 難以置信的事情讀者·校園版(2019年24期)2019-12-10 在隊(duì)列里軍營文化天地(2018年2期)2018-12-15 豐田加速駛?cè)胱詣玉{駛隊(duì)列產(chǎn)品可靠性報告(2017年7期)2017-09-05 高速路上右行規(guī)則與無序行駛規(guī)則的比較研究山西大同大學(xué)學(xué)報(自然科學(xué)版)(2016年2期)2016-12-12 無序體系中的國際秩序國際政治科學(xué)(2016年2期)2016-10-20
劉 健
（1.四川開放大學(xué)高職學(xué)院，四川 成都 610107；2.四川華新現(xiàn)代職業(yè)學(xué)院信息中心，四川 成都 610107）
0 引言
現(xiàn)已有多種存儲數(shù)據(jù)的常規(guī)算法，相關(guān)算法也在實(shí)踐應(yīng)用中得到了證明和推廣。該文討論的算法涉及2個隊(duì)列：對象隊(duì)列和容器隊(duì)列，顯然不能簡單套用已有的普適性算法，必須在該基礎(chǔ)上進(jìn)行改進(jìn)。
現(xiàn)實(shí)生活中的實(shí)際需求不會一成不變，更不可能恰好匹配常規(guī)算法的要求。實(shí)際情況常需要綜合運(yùn)用2個或多個常規(guī)算法，還要摻雜一些特殊要求。在現(xiàn)實(shí)的生產(chǎn)生活中，工作人員還可以借助通用型的工業(yè)軟件，通過半手工操作的方法來進(jìn)行常規(guī)算法形式的運(yùn)算，這種方法的效率極低。當(dāng)遇到某些特殊需求時，這種半手工的方法就完全無法滿足要求。該文采用移動窗口的方式來消除若干個對象間的社會聯(lián)系，這是半手工方法根本不能勝任的任務(wù)。
1 背景介紹
該文討論的問題來源于一個經(jīng)常出現(xiàn)的現(xiàn)象：人或物在一個特定的環(huán)境里按照一定的規(guī)則安排存放的位置或場地。這些人或物可以抽象為對象，若干個人或物就組成對象隊(duì)列。當(dāng)然，這些人或物之間是要分類的，分類后就構(gòu)成異類的對象隊(duì)列。當(dāng)這些對象剛出現(xiàn)時，都是無序的。至于這些對象要存放的位置或場地就可以抽象為容器。因?yàn)槿嘶蛭锟赡軙?jīng)常更換，所以不能對這些對象有過多要求。而容器相對來說不會頻繁更換，可以按照特定的標(biāo)準(zhǔn)統(tǒng)一生產(chǎn)或配置。
2 前置條件
2.1 標(biāo)準(zhǔn)容器
所有容器都是標(biāo)準(zhǔn)化的容器，記為container（=1，2，…，），其容量記為capacity（=1，2，…，）。每個容器內(nèi)部都劃分為若干個小格，稱為存儲格，記為cell（=1，2，…，；=1，2，…，capacity）。容器中存儲格的數(shù)量就是這個容器的容量。
每個容器內(nèi)部的存儲格之間沒有區(qū)別，即尺寸、容量、和功能都一樣，而相同類型的容器與容器間在功能上也沒有區(qū)別，都可以存儲同類對象，這就是標(biāo)準(zhǔn)容器。標(biāo)準(zhǔn)容器利于存儲個體間有細(xì)小差異的同類對象。
2.2 對象和容器分類
對象有其自身的類型，根據(jù)對象類型的不同，對存儲格的要求也不同，于是就需要對存儲格進(jìn)行分類。因?yàn)槊總€容器內(nèi)的存儲格性質(zhì)都相同，所以存儲格的類型就決定容器的類型。存儲格的類型與容器的類型一致，并與存儲對象的類型一致，如公式（1）所示。
式中：object_type（=1，2，…，）為對象的類型；cell_type（=1，2，…，）為存儲格類型；container_type（=1，2，…，）為容器的類型。
既然3個實(shí)體的類型都必須一致，那可以把3個類型都簡化為1個類型，如公式（2）所示。
式中：type（=1,2,…,）為3個類型統(tǒng)一。
當(dāng)對象異類時，就需要異類容器去匹配相應(yīng)類型的對象，以滿足相應(yīng)的存儲要求。對象類型的數(shù)量決定容器類型的數(shù)量，這就解決了標(biāo)準(zhǔn)容器存儲異類對象的問題。
2.3 容器的容量
因?yàn)槭菢?biāo)準(zhǔn)容器，內(nèi)部的存儲格必須一致，所以可以將相同類型容器的內(nèi)部存儲格數(shù)量設(shè)定為相同，即同類容器的容量都一樣，這樣便于對容器進(jìn)行生產(chǎn)和管理。這種情況是一種理想狀態(tài)，實(shí)踐的過程中很難滿足這種極端條件，如公式（3）所示。
式中：capacity為容器的容量，=1,2,…,。
由于容量都一致，因此可以簡單記為。
在實(shí)際運(yùn)用中，因?yàn)楝F(xiàn)場地理?xiàng)l件等各種因素的影響，不一定只允許相同容量的容器存在，所以需要為每個容器設(shè)定自身的容量，此時各個capacity的值不盡相同。但每個容器的容量都不能超過標(biāo)準(zhǔn)容器的容量，即滿足公式（4）。
式中：為標(biāo)準(zhǔn)容器的容量；capacity為各個容器的容量，=1,2,…,。
2.4 容器的優(yōu)先級
雖然同類容器的功能一樣，但是實(shí)際每個容器的內(nèi)部構(gòu)成并不一定完全一致，只要滿足容器分類的標(biāo)準(zhǔn)即可。在使用的過程中，就需要對容器的使用順序進(jìn)行排序。對每個容器指定一個優(yōu)先級，記為rank（=1，2，…，），優(yōu)先級別最高的最先使用，以rank為最高優(yōu)先級。當(dāng)然也可以優(yōu)先級別最低的最先使用，這只需要倒序排序即可。在實(shí)際操作中，正序和倒序?qū)Y(jié)果沒有影響，簡單說就是排在最前的容器最先使用。
因?yàn)榇嬖诜菢?biāo)準(zhǔn)容器，所以為保證標(biāo)準(zhǔn)容器優(yōu)先使用，就需要保證大容量容器的優(yōu)先級高于小容量容器，即滿足公式（5）。
式中：capacity（=1，2，…，）為排序后各個容器的容量。
2.5 異類無序?qū)ο蟮拇嬖跔顟B(tài)
對象以批量的形式存在，即對象是整體出現(xiàn)或整體消亡的無序隊(duì)列，不是單個出現(xiàn)、逐個到達(dá)后形成隊(duì)列的。整個無序隊(duì)列存儲進(jìn)標(biāo)準(zhǔn)容器后，再經(jīng)過后續(xù)的相關(guān)階段，容器整體清空，待下個無序隊(duì)列存儲及使用。對象有批次的區(qū)分，各個批次之間有時間順序，不能同時存在。
對象隊(duì)列里存在各種類型的節(jié)點(diǎn)，因?yàn)槭菬o序隊(duì)列，所以隊(duì)列里相鄰節(jié)點(diǎn)的類型不一定相同。當(dāng)相鄰節(jié)點(diǎn)類型一致時，有可能出現(xiàn)若干個相鄰節(jié)點(diǎn)間的非技術(shù)性社會聯(lián)系。為消除這些社會聯(lián)系，就采用移動窗口式的手段使這些節(jié)點(diǎn)交錯分離，分別存儲在當(dāng)前窗口內(nèi)的若干個容器里，而不是連續(xù)存儲在同一個容器里。
3 存儲步驟
3.1 鎖定容器
在開始存儲對象前，必須鎖定現(xiàn)場所有容器，因?yàn)榇藭r尚不知道當(dāng)前對象的類型，所以是鎖定所有容器。鎖定后，不允許其他指令與該指令并行運(yùn)行，即使是讀取存儲容器狀態(tài)也不行（后續(xù)的操作都具有嚴(yán)格的排他性）。
如果有2個指令集并行運(yùn)行，就會出現(xiàn)臟數(shù)據(jù)，后續(xù)的操作結(jié)果都是臟數(shù)據(jù)。存儲對象的操作只能是串行運(yùn)行的，即當(dāng)某個操作指令集到達(dá)時，發(fā)現(xiàn)全部容器已經(jīng)被排他性鎖定，只能等待前一個指令集操作完畢、釋放容器后，才能對容器進(jìn)行鎖定操作。
3.2 判斷位置
在存儲列表中搜尋當(dāng)前指令的對象是否已經(jīng)存在存儲位置cell。如果有，就直接跳過后面的存儲流程，此時≠null并且≠null（1，1≤y≤capacity，null表示空）。如果沒有，就進(jìn)入下面的存儲流程，當(dāng)=null并且=null時，進(jìn)入步驟3.3。
3.3 選擇對象匹配的容器類型
根據(jù)對象的類型選擇適合的容器類型，即根據(jù)type選擇類型一致的容器，拋棄不符合需求的容器。后續(xù)的操作都不再涉及容器類型的問題，因?yàn)榇颂幰呀?jīng)作過類型篩選，只保留滿足需求的容器，所以默認(rèn)的操作都是在同種類型的容器上完成的。
3.4 存儲對象
首先，設(shè)定1個窗口值，采用偽隨機(jī)的方式把連續(xù)的個對象平均分配到個容器里去，目的是切斷這些對象間的社會聯(lián)系。偽隨機(jī)的方式有很多種，為計(jì)算簡單、運(yùn)行高效，目前采用的是取模方式，即根據(jù)對象的下標(biāo)取模，把個對象分別依次存儲到個容器里，下一輪的個對象也一樣，后面的對象存儲方式以此類推，直到窗口所在位置的個容器全部填滿。此時，窗口向后移動，躍過當(dāng)前的個容器，去覆蓋后面的個空閑容器。上一個窗口所在位置的個容器已經(jīng)填滿，就處于關(guān)閉狀態(tài)。此時，窗口所在位置的容器還沒有存入對象，處于就緒狀態(tài)，等待下一個對象的到來。
這樣，看上去就像窗口在不停地移動，因此稱為移動窗口式存儲。理論上來說，的取值范圍為1 ~。當(dāng)= 1時，全部容器根據(jù)優(yōu)先級依次使用，不存在偽隨機(jī)的存儲方式，也就不能發(fā)揮消除對象間社會聯(lián)系的作用。當(dāng)=時，把全部的容器同時放在最大的一個窗口里，全部的容器同時處于就緒狀態(tài)，整個對象隊(duì)列會平均分配到全部的容器里。顯然，在實(shí)際操作中的取值不應(yīng)該是兩頭的極限，即≠1并且≠。
此時，判斷存儲列表是否為空。如果為空，就進(jìn)入步驟3.4.1；如果不為空，就進(jìn)入步驟3.4.2。
當(dāng)存儲列表為空時，就表明還沒有任何一個對象已經(jīng)存儲到此類容器中，此類容器全部都是空閑狀態(tài)。因?yàn)槿萜饕呀?jīng)事先根據(jù)優(yōu)先級排序，所以根據(jù)這類容器的優(yōu)先級別最高級rank把當(dāng)前對象直接放在存儲列表的首位，即第1個容器container的第1個存儲格cell。因?yàn)槭谴鎯α斜淼牡?條信息，所以要單獨(dú)處理。
獲取存儲列表中存儲格cell的最大值，即和的最大值。因?yàn)榇鎯樞蚴歉鶕?jù)容器的優(yōu)先級rank和容器內(nèi)存儲格cell的排列次序執(zhí)行的，所以cell就是存儲列表末尾的那個值。
對進(jìn)行的取模運(yùn)算，即可獲得當(dāng)前窗口的位置。當(dāng)前窗口的第1個容器為container，如公式（6）所示。
式中：為當(dāng)前窗口第1個容器的編號；為窗口的尺寸；為存儲列表末尾容器的編號。
當(dāng)前窗口的最后1個容器為container，如公式（7）所示。式中：為當(dāng)前窗口的最后1個容器的編號；為窗口的尺寸；為當(dāng)前窗口第1個容器的編號。
不能簡單計(jì)為（+-1），當(dāng)窗口移動到最后1個位置時，窗口內(nèi)的容器數(shù)量有可能小于窗口的值，而且出現(xiàn)這種情況的概率非常高。在實(shí)際操作中，容器隊(duì)列的數(shù)量基本是固定的，而窗口是可變值。讓容器數(shù)量剛好為每個窗口的整數(shù)倍，這幾乎是不可能的事。
在確定和的值后，就可以確定當(dāng)前窗口所在的位置。而container就是當(dāng)前窗口里的當(dāng)前容器，cell就是當(dāng)前容器里的當(dāng)前存儲格，當(dāng)前對象就應(yīng)該存儲在當(dāng)前存儲格cell的“下一個位置”。這個“下一個位置”有可能是下一個容器的相同位置的存儲格cell，也有可能是當(dāng)前窗口內(nèi)第一個容器的下一個存儲格cell。
此時，對當(dāng)前窗口內(nèi)的所有容器進(jìn)行遍歷查找，目的是尋找合適的存儲位置。以當(dāng)前容器container為起始位置，獲得下一個容器container。如果container還有空余存儲格，即當(dāng)capacity＞時，那么當(dāng)前對象就存儲在容器container的存儲格cell里。如果container已經(jīng)填滿，即當(dāng)capacity=時，就獲取再下一個容器container。以此類推，直到查找到當(dāng)前窗口里的最后一個容器container為止。
在完成此輪遍歷查找后，如果沒有尋找到合適的存儲位置，就表明當(dāng)前窗口內(nèi)當(dāng)前容器后面的容器都已經(jīng)填滿，能據(jù)此判斷這樣結(jié)果的原因就在于前置條件2.4的容量優(yōu)先級。既然這些容器已滿，那只能回到當(dāng)前窗口的第1個容器container查詢空余位置。
如果container還有空余位置，即當(dāng)capacity＞時，當(dāng)前對象就存儲在容器container的存儲格cell 里。如果container也已經(jīng)填滿，就表明當(dāng)前窗口已滿，即整個窗口內(nèi)的全部容器都已經(jīng)填滿，只能移動到下一個窗口。當(dāng)前對象就存儲在容器container的存儲格cell里，可以判斷當(dāng)前窗口已滿的原因也是前置條件2.4的容量優(yōu)先級。
3.5 收斂窗口
當(dāng)存儲操作達(dá)到閾值時，就要對窗口值進(jìn)行收斂。這個閾值就是當(dāng)窗口移動到最后一個位置，即在最后一個窗口內(nèi)操作時，即為達(dá)到閾值?？梢杂脤ο笫Ｓ嗔颗c當(dāng)前窗口的容量比較值作為標(biāo)準(zhǔn)，以判斷是否已經(jīng)到達(dá)最后一個窗口，如公式（8）所示。
式中：為對象隊(duì)列的數(shù)量；capacity為第個容器的容量。
這時，就已經(jīng)到達(dá)最后一個窗口。
由公式（8）可以推導(dǎo)出公式（9）、公式（10）。
由公式（10）可知，判斷標(biāo)準(zhǔn)更簡潔，從代碼的實(shí)現(xiàn)程度來說，難度也降低了。并且公式（10）的實(shí)際意義可以解釋為對象的數(shù)量小于窗口所覆蓋過的全部容器的存儲量的總和，包括最后一個窗口。窗口所覆蓋的全部容器不一定是整個容器隊(duì)列，其數(shù)量有可能比整個容器隊(duì)列的數(shù)量少。
此時，不再使用窗口的預(yù)設(shè)值，而是把窗口收縮到最小值，即設(shè)置= 1。收斂窗口的目的是在最后一個窗口內(nèi)不作偽隨機(jī)的平鋪式存儲，而是根據(jù)容器的優(yōu)先級依次存儲。
如果繼續(xù)采用偽隨機(jī)的平鋪式存儲，那么必然會浪費(fèi)最后一個窗口內(nèi)容器的存儲空間（最后一個窗口內(nèi)的全部容器都會處于半空狀態(tài)，即每個容器都存儲部分對象，同時還有空余存儲格）。
因?yàn)殚_啟容器就意味使用鏈條上的資源都必然配合開啟，所以半空狀態(tài)的容器必然也會浪費(fèi)鏈條上、下游的資源。
在設(shè)置= 1后，則繼續(xù)步驟3.4.2，直至對象存儲完畢。整個流程如圖1所示。
圖1 存儲流程
4 應(yīng)用實(shí)例
該文承載項(xiàng)目的單位每年舉行參與人數(shù)眾多的招錄考試，高峰時人數(shù)達(dá)到3 413人。該實(shí)例就以該數(shù)量為試驗(yàn)數(shù)據(jù)進(jìn)行演算?？傮w數(shù)據(jù)都處于無序狀態(tài)，形成1個沒有排序標(biāo)準(zhǔn)的無序隊(duì)列。每個個體都可以抽象為1個對象，全部的對象就形成無序?qū)ο箨?duì)列。其中，有效數(shù)據(jù)3 300個，無效數(shù)據(jù)113個。有效數(shù)據(jù)分2類，第Ⅰ類為3 179個，第Ⅱ類為121個。為對象安排位置就可以抽象為存儲進(jìn)容器里的存儲格，該試驗(yàn)容器準(zhǔn)備情況為第Ⅰ類標(biāo)準(zhǔn)容器105個，容量都為30；第Ⅰ類非標(biāo)準(zhǔn)容器3個，容量分別為20、15和15；第Ⅱ類標(biāo)準(zhǔn)容器6個，容量都為30。
該實(shí)例采用SQL語言實(shí)現(xiàn)算法，形成存儲過程，再使用查詢語句逐個對象調(diào)用存儲過程，模擬工作人員逐個安排存儲位置。試驗(yàn)環(huán)境為Interl Xeon CPU E5-2609 v2 @ 2.5GHz，Windows 2003，SQL Server 2005 SP4。總共進(jìn)行10次試驗(yàn)，每次的取值都為1~10，試驗(yàn)耗時結(jié)果見表1。
表1 試驗(yàn)耗時結(jié)果（單位：s）
上述結(jié)果表明，窗口值的浮動對運(yùn)行時間的影響極小，每次運(yùn)行的時間差異非常小，耗時差最大值也僅為58-48 = 10 s。這跟運(yùn)行環(huán)境緊密相關(guān)，試驗(yàn)的服務(wù)器同時運(yùn)行多個虛擬機(jī)，因此其他虛擬機(jī)的服務(wù)對CPU、內(nèi)存和硬盤的使用都會影響試驗(yàn)結(jié)果。圖2可以更直觀地表述相關(guān)結(jié)果。
圖2 試驗(yàn)耗時結(jié)果
通過上文可以得出結(jié)論：對窗口大小的設(shè)置不影響實(shí)用方案的選擇。根據(jù)多年的經(jīng)驗(yàn)積累，最終實(shí)際選擇
= 3。
無效數(shù)據(jù)基本都是信息不全造成的，在補(bǔ)齊信息后即可轉(zhuǎn)換為有效數(shù)據(jù)。因?yàn)榍懊? 300個有效數(shù)據(jù)已經(jīng)安排完畢，所以此時不再由SQL查詢語句調(diào)用存儲過程，而是業(yè)務(wù)層通過業(yè)務(wù)邏輯層傳遞參數(shù)調(diào)用存儲過程，完成單個數(shù)據(jù)的存儲位置安排任務(wù)。
5 結(jié)語
該文所闡述的算法來源于普通的招考錄取社會現(xiàn)象，根據(jù)多年的實(shí)踐最終抽象為“標(biāo)準(zhǔn)容器存儲對象”的問題。
在解決該問題前，都采用傳統(tǒng)的人工方式分配位置。當(dāng)對象數(shù)量大約為2 000個時，工作人員需要3個工作日才能完成任務(wù)，而且必須是全程只處理這一件事，不能同時處理其他事務(wù)。當(dāng)對象數(shù)量大于3 000個時，通常工作人員需要4~5個工作日才能完成。在實(shí)際運(yùn)行中，該流程所許用的時間常少于4個工作，工作人員必須在非工作時間繼續(xù)處理這個問題。
在提出該算法后，真正的處理時間小于1 min，提升了工作效率。即使是性能并不出眾的服務(wù)器仍然可以在非常短的時間內(nèi)達(dá)到預(yù)期結(jié)果。
猜你喜歡
汽車實(shí)用技術(shù)(2022年14期)2022-07-30
閱讀（快樂英語中年級）(2022年11期)2022-05-30
小學(xué)生學(xué)習(xí)指導(dǎo)(低年級)(2020年4期)2020-06-02
讀者·校園版(2019年24期)2019-12-10
軍營文化天地(2018年2期)2018-12-15
產(chǎn)品可靠性報告(2017年7期)2017-09-05
山西大同大學(xué)學(xué)報(自然科學(xué)版)(2016年2期)2016-12-12
國際政治科學(xué)(2016年2期)2016-10-20
