武警工程大學信息工程系 張 劍

循環(huán)鏈表式滑動窗的設計與實現(xiàn)

武警工程大學信息工程系 張 劍

由于數(shù)據(jù)流具有無限性及連續(xù)性，滑動窗口的應用可以有效的對數(shù)據(jù)流上的操作加以限制，但傳統(tǒng)向量型滑動窗在連續(xù)數(shù)據(jù)的處理上計算開銷大，效率低。本文提出一種循環(huán)鏈表式滑動窗口技術，以鏈表的形式存儲每個子窗口所在位置，將新數(shù)據(jù)直接插入子窗口中，使滑動窗口在處理數(shù)據(jù)流時不必頻繁移動窗內(nèi)數(shù)據(jù)。實驗結果證明，該方法能有效減少計算開銷，增加數(shù)據(jù)處理效率。

循環(huán)鏈表；滑動窗口；流數(shù)據(jù)

0 引言

隨著信息網(wǎng)絡的發(fā)展，數(shù)據(jù)量不斷加大，存儲在數(shù)據(jù)庫中的靜態(tài)數(shù)據(jù)已不能滿足研究與應用的需求，數(shù)據(jù)不再是靜態(tài)的，而是一串實時，連續(xù)且有序的數(shù)據(jù)流，如電話數(shù)據(jù)、氣溫數(shù)據(jù)、病例數(shù)據(jù)、商業(yè)數(shù)據(jù)等等[1-3]。如今，如何對數(shù)據(jù)流進行高效處理已成為研究熱點問題。

常用數(shù)據(jù)流處理模型有滑動窗口模型、界標模型和快照模型?；瑒哟澳Ｐ褪且环N流量控制技術，可以良好的改善吞吐量，進行傳輸控制，目前被廣泛的研究并應用于數(shù)據(jù)的處理當中[4-7]。目前大多滑動窗口的實現(xiàn)都基于向量模型[8]，隨著窗口的滑動，新數(shù)據(jù)移入且舊數(shù)據(jù)的移出，所有子窗口內(nèi)的數(shù)據(jù)都要進行移動，這就造成了資源的浪費。循環(huán)鏈表[9]中，每一個子節(jié)點包含信息域和指針域，分別用來存儲信息和指向下一節(jié)點。本文通過為滑動窗建立指針域，來減少窗口移動帶來的因子窗口移動帶來的數(shù)據(jù)處理量過大，效率低的問題。

1 基礎知識

1.1 滑動窗口

滑動窗口模型就是在數(shù)據(jù)流中設置一個窗口，可以通過滑動來維護處理當前數(shù)據(jù)。每處理一段數(shù)據(jù)，窗口向前滑動一個單位，對處理過的數(shù)據(jù)進行刪除，并插入新的數(shù)據(jù)。如圖1所示為含有4個基本窗口的滑動窗口。

圖1 滑動窗口

圖2 循環(huán)鏈表

1.2 循環(huán)鏈表

鏈表中的每個結點包含一個指針域，每個結點除了存儲自身元素外，還要存儲一個指向后續(xù)結點的指針信息，最后一個結點的指針則指向鏈表的頭結點，使整個鏈表形成一個環(huán)狀鏈表，稱作循環(huán)鏈表，可通過指針信息實現(xiàn)結點的插入與刪除，結構如圖2所示。

2 循環(huán)鏈表式滑動窗口

2.1 基本思想

在基于向量模型的滑動窗口中，如果窗口未滿，則順序向前滑動。而當窗口被數(shù)據(jù)充滿后，后續(xù)數(shù)據(jù)的到來會使得滑動窗口內(nèi)的所有數(shù)據(jù)發(fā)生移動，但若是通過鏈表的方式，利用指針指向下一子目標窗口，把已處理數(shù)據(jù)直接刪去，并向目標窗口直接插入新數(shù)據(jù)，而不是將窗口內(nèi)的數(shù)據(jù)進行移動。

2.2 形式化表示

循環(huán)鏈表式滑動窗口可以形式化的表示為：

Circular linked list W=＜w，length，l，head，link ai＞

link=head;

i=1;

將初始數(shù)據(jù)輸入到窗口1；

whlie （數(shù)據(jù)流輸入）

{

i=i+1；

link=link ai;

將數(shù)據(jù)輸入到窗口i；

}

其中w表示滑動窗口的寬度；length表示當前子窗口內(nèi)的數(shù)據(jù)量；head表示滑動窗口起始子窗口的位置；link ai 表示每一子窗口的指針信息，用于指出下一子窗口的位置信息。

2.3 模型分析

在滑動窗口未被填滿時，循環(huán)鏈表式滑動窗口直接將數(shù)據(jù)根據(jù)鏈表指針填入空的子窗口中。當子窗口已滿時，與傳統(tǒng)向量模型不同的是，本文所提滑動窗口模型不會大幅度移動數(shù)據(jù)，而是根據(jù)指針直接將數(shù)據(jù)插入到下一子窗口并覆蓋此處的數(shù)據(jù)，同時修改link值，指向末端數(shù)據(jù)。

2.4 效率分析

在處理數(shù)據(jù)流時，滑動窗口在短時間內(nèi)將會被填滿，傳統(tǒng)滑動窗口模型在子窗口被填滿后會將窗口中數(shù)據(jù)依次移動，覆蓋原有數(shù)據(jù)，并將新數(shù)據(jù)添加至最末端子窗口。本文所提循環(huán)鏈表式滑動窗口則是直接將新數(shù)據(jù)添加到最末端子窗口，無需大量移動原有數(shù)據(jù)。在對數(shù)據(jù)流的長期處理中，效率的提升是巨大的。

3 實驗結果與分析

本節(jié)將對循環(huán)鏈表式滑動窗口進行實驗分析。實驗數(shù)據(jù)來源于一臺信號發(fā)生器，實驗環(huán)境為：Microsoft Windows 7，500G硬盤，4G內(nèi)存，使用C++實現(xiàn)滑動窗口的編譯。

實驗1：主要通過將等量數(shù)據(jù)分別交給兩種不同滑動窗口模型來考察滑動窗口對于數(shù)據(jù)流的響應能力，實驗中未對窗口進行并發(fā)控制，實驗結果如圖1所示。由圖3可知隨著子窗口的變大，滑動時間均有減少，這是因為窗口的變大使單位時間內(nèi)可滑過的數(shù)據(jù)量增加，由于循環(huán)鏈表在數(shù)據(jù)處理時不需要將數(shù)據(jù)頻繁移動所以滑動時間更少。且隨著窗口變大，指針信息的添加對于滑動窗口的影響越來越小。

圖3 未加鎖滑動時間比較

實驗2：實驗中對窗口進行加鎖的并發(fā)控制，進一步研究循環(huán)鏈表式滑動窗口在效率上的提升。由圖4可知，傳統(tǒng)向量模型滑動時間高低起伏，這是由于鎖定條件下窗口越大，鎖定粒度越大，阻礙滑動速度。

圖4 加鎖控制滑動時間比較

由實驗結果可知，循環(huán)鏈表式滑動窗口可以有效減少數(shù)據(jù)流的處理速度，且在子窗口變大后處理速度的增加比傳統(tǒng)向量模型更加明顯。

4 結論

本文提出了循環(huán)鏈表式滑動窗口模型，目的是減少向量模型在窗口滑動時大量移動數(shù)據(jù)。通過對每個子窗口建立鏈接，直接將數(shù)據(jù)寫入下一子窗口。通過實驗證明，本文所提方案能夠有效減少窗口滑動時間，提高數(shù)據(jù)流處理的效率。

[1]Janacek G．Time series analysis forecasting and control[J]．Journal of Time Series Analysis,2010,31(4)：303-303．

[2]Chu H H,Chen T L,Cheng C H,et al．Fuzzy dual-factor timeseries for stock index forecasting[J]．Expert systems with applicatio ns,2009,36(1)：165-171．

[3]Koijen R S J,Lustig H N,Van Nieuwerburgh S．The cross-section and time-series of stock and bond returns[J]．2012．

[4]常建龍,曹鋒,周傲英．基于滑動窗口的進化數(shù)據(jù)流聚類[J]．軟件學報,2007,18(4)：905-918．

[5]楊宏斌．基于無鎖可復用滑動窗口的流量控制方法[J]．電子技術與軟件工程,2016(17)：13-13．

[6]李建中,張冬冬．滑動窗口規(guī)模的動態(tài)調(diào)整算法[J]．軟件學報,2004,15(12)：1800-1814．

[7]葉春濤,吳鋌,張旻,等．“靈活”的滑動窗口算法及其計算量的估計[J]．計算機應用與軟件,2008,25(11)：42-43．

[8]IEEE Computer Society LAN MAN Standards Committee．Wireless LAN medium access control(MAC)and physical layer(PHY) specifications[J]．IEEE Standard 802．11-1997,1997．

[9]韋雷．基于多維雙向循環(huán)鏈表的虛擬云存儲研究[D]．中國科學院大學(工程管理與信息技術學院),2015．

Design and Implementation of Sliding Window with Circular Linked List

ZHANG Jian
（Department of Information Engineering，Engineering University of CAPF，Xi’an Shaanxi 710086，China）

Because data streams are unlimited and continuity，application of the sliding window can be effective for data stream operation restrictions，but the traditional vector type sliding window in processing continuous data on large computational overhead，low eff i ciency.This paper presents a circular list type sliding window technology，in the form of storage of each sub window list of the location of the new data directly into the sub window，the sliding window when processing data stream without frequent mobile data window.Experimental results show that this method can effectively reduce the computational overhead and increase the eff i ciency of data processing.

Circular linked list；sliding window；stream data