實作 Landmark Window 與 Sliding Window

由於在 “Knowledge Discovery from Data Streams" 第 17 頁見到 windowing 技術的概括分類,

%e6%93%b7%e5%8f%96

我試著實作 Landmark Window [1] 和 Sliding Window [2] 。

Windowing 技術,以 Sliding Window 為例,為了能保留較近的資料,同時拋棄較遠的資料,一段連續的資料段落需要被保留起來。 Landmark Window 從尾端放進了多少資料,就需要保留多少資料。 Sliding Window 則實作 FIFO ,當新的一筆資料放進去尾端時,假如 window 的資料數目已達到 window 的容量,則前端最早的一筆資料則要退出。

實作上, window 的容量,定義為資料數目。每一筆資料都編列一個號碼,而由於 Erlang 語言有能力以字面寫出超大數字,並且可以操作,所以用一個變數 next 標記下一筆即將進來的資料編號,並且只要有 next 變數,就可以指出串流資料的數目。 Sliding Window 需要多用到一個變數 size ,表示 window 的容量,而資料數目需要由 next 和 size 二變數來求出。

串流資料的保存,我選擇以字典格式 dict 搭配二變數,提供 FIFO 的能力,同時保留其他方面的彈性,例如隨機存取。我沒有選擇以許多個 list 實作 queue 來表達 sliding window ,因為對於 queue 的結構與驗證等細節,要多做討論。

[1] Landmark Window 實作: https://github.com/streamarium/DataStreamsErlang/blob/master/src/landmark_window_of_int.erl

[2] Sliding Window 實作: https://github.com/streamarium/DataStreamsErlang/blob/master/src/sliding_window_of_int.erl

廣告

About 黃耀賢 (Yau-Hsien Huang)

熱愛 Erlang ,並且有相關工作經驗。喜歡程式語言。喜歡邏輯。目前用 Python 工作。
本篇發表於 Uncategorized 並標籤為 。將永久鏈結加入書籤。