循環(huán)鏈表式滑動(dòng)窗的設(shè)計(jì)與實(shí)現(xiàn)

武警工程大學(xué)信息工程系 張 劍

循環(huán)鏈表式滑動(dòng)窗的設(shè)計(jì)與實(shí)現(xiàn)

武警工程大學(xué)信息工程系 張 劍

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

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

0 引言

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

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

1 基礎(chǔ)知識(shí)

1.1 滑動(dòng)窗口

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

圖1 滑動(dòng)窗口

圖2 循環(huán)鏈表

1.2 循環(huán)鏈表

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

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

2.1 基本思想

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

2.2 形式化表示

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

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表示滑動(dòng)窗口的寬度；length表示當(dāng)前子窗口內(nèi)的數(shù)據(jù)量；head表示滑動(dòng)窗口起始子窗口的位置；link ai 表示每一子窗口的指針信息，用于指出下一子窗口的位置信息。

2.3 模型分析

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

2.4 效率分析

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

3 實(shí)驗(yàn)結(jié)果與分析

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

實(shí)驗(yàn)1：主要通過(guò)將等量數(shù)據(jù)分別交給兩種不同滑動(dòng)窗口模型來(lái)考察滑動(dòng)窗口對(duì)于數(shù)據(jù)流的響應(yīng)能力，實(shí)驗(yàn)中未對(duì)窗口進(jìn)行并發(fā)控制，實(shí)驗(yàn)結(jié)果如圖1所示。由圖3可知隨著子窗口的變大，滑動(dòng)時(shí)間均有減少，這是因?yàn)榇翱诘淖兇笫箚挝粫r(shí)間內(nèi)可滑過(guò)的數(shù)據(jù)量增加，由于循環(huán)鏈表在數(shù)據(jù)處理時(shí)不需要將數(shù)據(jù)頻繁移動(dòng)所以滑動(dòng)時(shí)間更少。且隨著窗口變大，指針信息的添加對(duì)于滑動(dòng)窗口的影響越來(lái)越小。

圖3 未加鎖滑動(dòng)時(shí)間比較

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

圖4 加鎖控制滑動(dòng)時(shí)間比較

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

4 結(jié)論

本文提出了循環(huán)鏈表式滑動(dòng)窗口模型，目的是減少向量模型在窗口滑動(dòng)時(shí)大量移動(dòng)數(shù)據(jù)。通過(guò)對(duì)每個(gè)子窗口建立鏈接，直接將數(shù)據(jù)寫入下一子窗口。通過(guò)實(shí)驗(yàn)證明，本文所提方案能夠有效減少窗口滑動(dòng)時(shí)間，提高數(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]常建龍,曹鋒,周傲英．基于滑動(dòng)窗口的進(jìn)化數(shù)據(jù)流聚類[J]．軟件學(xué)報(bào),2007,18(4)：905-918．

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

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

[7]葉春濤,吳鋌,張旻,等．“靈活”的滑動(dòng)窗口算法及其計(jì)算量的估計(jì)[J]．計(jì)算機(jī)應(yīng)用與軟件,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)鏈表的虛擬云存儲(chǔ)研究[D]．中國(guó)科學(xué)院大學(xué)(工程管理與信息技術(shù)學(xué)院),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