iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 21
0
自我挑戰組

當傳統演算法遇到新的計算模型系列 第 21

Day 21: 串流計算模型(一)Streaming Model, Part 1

大家想必對「串流」這個詞並不陌生:比方說「影音串流」之類的,會有影像或音訊源源不絕地輸入或輸出。在 C++ 裡面也有所謂的檔案串流,作業系統會先將開啟的檔案的開頭的一部分存入緩衝區,然後等待你的程式將它們逐一讀進去。

這種感覺很像是:有一連串的資料「路過了」你的程式,你的程式不需要、也不見得有足夠記憶體將所有「路過」的資料通通存下來。以演算法的角度而言,這幾年因應大資料而發展出的兩大類演算法:

優於線性時間演算法 sub-linear time algorithms

能否不看過所有資料就能夠找到足夠好的答案呢?近幾年有很多很多大學陸續開設了相關的課程。比方說 MIT SurveyTel-Aviv UniversityColumbia UniversityU Texas。顯然對於大部分的問題而言,不看過所有輸入的資料無法精準回答正確答案(比方說找最大值等等),但是利用機率與一些對資料分佈的假設,不用看過所有輸入資料,也可以根據理論找出足夠好的答案。

串流演算法 streaming algorithms

與優於線性時間相對的,則是存不下所有輸入的少於線性空間 sub-linear space。但為什麼這系列的演算法不叫做 sub-linear space algorithms 呢?原因是,既然存不下所有的輸入,那麼一個非常合理的假設是,一個一個收到輸入之後、程式處理完就必須把它丟掉了。這樣子的計算模型我們就把它定義成串流計算模型。

什麼是 sub-linear 呢?假若輸入的資料量是 O(N),那麼 N/log N、https://chart.googleapis.com/chart?cht=tx&chl=%5Csqrt%7BN%7D、log N、log log N 都是 sub-linear 啊(除以 N 以後趨近於 0)。如果硬要對串流演算法使用的空間進行嚴格定義的話,通常我們只會認可 O(polylog N) 的資料使用量、才叫做 (hard) streaming algorithms。

但是,對於由兩個參數決定的入規模:比方說一個 Graph,它有 N 個點、M 條邊(雖然 M >= N,但 M 的取值範圍可以相當廣泛,對於演算法的分析而言也常常是個重要的參數)。又或者我們考慮的輸入形式是一個 N x N 大小的矩陣,其中只有 M 個非零的數值(這樣儲存只需要 O(M) 的空間、一般來說我們也有 M >= N。)。在現實中,往往我們能夠存得下 N 筆資料、但是存不下全部長度為 M 的輸入。因此,如果一個串流演算法使用了 O(N polylog N) 的空間,那麼我們會說這個演算法是半串流演算法 (Semi-Streaming Algorithms) 的。

明天我們來看看一些經典的串流演算法吧~


上一篇
Day 20: 隨機計算模型 Randomized Algorithms -- 快速排序法
系列文
當傳統演算法遇到新的計算模型21

尚未有邦友留言

立即登入留言