iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 1
1

寫程式的目的,即是把不斷重複的計算流程自動化。而演算法,則是用以明確定義自動化後的計算流程。在設計演算法之前,除了對於要解決的問題有一定程度的認識以外,還必須考量實作演算法後的執行環境(例如程序執行時的主機和系統),才能找出理想的答案。

看!演算法無所不在(梗)

讓我們來考慮一個平鋪直敘的問題:最大求職問題,不對,說錯了,是求最大值的問題。給你 https://chart.googleapis.com/chart?cht=tx&chl=n 個數字,請回答出這些數字裡頭最大的那個。你可能想說:欸,這很簡單啊,我可以宣告一個變數 temp,然後把每一個數都跟這個數字拿來比較,每一次比較都留下較大的那個值,把它存回 temp,獲得一個 https://chart.googleapis.com/chart?cht=tx&chl=O(n) 的線性時間演算法,心滿意足。

實際上把他寫出來以後,你可能會注意到實際在執行的時候,面對超大的資料量(比方說 https://chart.googleapis.com/chart?cht=tx&chl=n%3D10%5E9 個整數)你的程式就是會變成整套系統的悲慘瓶頸。

「這時候該怎麼辦?」

以現實層面而言,若我們使用的演算法,僅僅對於輸入的資料與欲回答的問題進行設計。那很容易忽略掉「計算模型」帶給我們效能改變。我以外部存取模型(External Memory Model) 為例:硬碟的讀取比記憶體的存取慢上很多很多倍,如果我們今天只在乎整套演算法做了多少次的加減法運算,那麼實際執行時很可能會因為大量 page fault 造成的硬碟讀寫而拖慢了整體的演算法效能。因此,考量不同程式的運行環境對於演算法來說也是相當必要的。

然而,每一台電腦和每一次的執行環境,其實都不太一樣啊。考量每個人的軟硬體設備、上面安裝的作業系統等等,會影響效能的因素實在是太多了。(那要怎麼改?改天吧(facepalm
因此,一些做計算機理論的人平常在分析的時候,會把一部分相較之下比較無關緊要的部份通通去掉。而剩下的部份,就會被歸類在我們稱為「計算模型」的東西。以下列出幾種常見的計算模型給各位參考(我把一些過於理論的模型去掉了,可能也有其他重要的計算模型,還請大家多多提出補充)~

隨機存取模型 Word RAM Model

這個是最貼近單機版的假設:單一執行緒(thread)、假設所有資料都存在記憶體裡面、CPU 支援每單位時間進行一次 https://chart.googleapis.com/chart?cht=tx&chl=w bits (https://chart.googleapis.com/chart?cht=tx&chl=w = 64-bit) 加減計算。

外部存取模型 External Memory Model

這個是考量到大多數資料都除存在一個緩慢的外接儲存裝置裡面,資料們是以頁(page) 為單位進行存儲。時間的計算也是以存取一次 page 為單位。有許多作業系統或資料庫演算法都是基於這個模型進行分析。

平行計算模型 Parallel Computation Model

與 RAM Model 雷同,假設所有資料都儲存在記憶體裡面。但不同的是,同時可以有多個執行緒(threads) 在跑。執行緒的數量會以一個參數 P 表示(代表運氣好的話,程式的執行時間可以到達 P 倍快)。這些執行緒可以分享一部分的記憶體。

線上計算模型 Online Computing

如果一個資料集可能會時常被更新,而每一次更新後我們又想要知道對於當前資料集,答案會是如何。這時候我們會需要發展出各種不同的資料結構(以及對應的演算法)來有效率地回答這些問題。評估時間效率的方法有兩種:最壞情形分析(worst case analysis,每次操作都不會花太久時間) 和均攤分析(amortized analysis,一口氣進行許多操作加起來不會花太久時間)。

串流計算模型 Streaming Model

如果輸入無法完全存放在記憶體裡面,但又想要有效地找到足夠好的解,那這時候可以參考一下串流模型底下的各種演算法們。除了影音串流處理、生物醫學的 DNA 序列等,串流演算法這幾年因應大資料而獲得很多重視,也有許多巧妙的演算法可以在某些題目上幫助大家節省記憶體。

分散式計算模型 Distributed Computation Model

如果所有資料放不進一台電腦怎麼辦?與平行計算模型不同的地方是,分散式系統以運算節點(node) 為單位,每一個節點執行自己的程序、擁有自己的記憶體、讀取屬於自己那部分的輸入。節點與節點之間相互以網路溝通,每一個封包被稱為訊息 message。相對而言,訊息的傳遞所需要的代價通常比在一個節點內部的計算來得高出許多。因此,在分析時間效能的時候,我們通常以訊息量和傳遞訊息的相依性作為指標。而分散式系統又可以根據訊息傳遞規則分成同步(Synchronous)和非同步(Asynchronous)的。不同的問題在這兩種模型底下的解法差異甚劇。


這些計算模型的創立或發明,都是為了因時制宜、滿足各種不同的運算需求的。有趣的是,當我們站在這些新的計算模型上面,回顧一些經典的演算法問題時,時常可以把計算模型附帶的好處應用在一些問題上,提出新的演算法,既能夠實際提昇效率、滿足解題需求、也往往能夠藉此看清問題的本質。

大家有興趣可以想想看:原本的找最大值問題,若要在以上幾個模型中有效率地運行,會變成什麼樣子呢?(寫書的作者們最喜歡叫大家 left as exercise 了!我也不例外)

在接下來的 29 天裡面,我會試著從幾個計算模型的角度出發,分享一些在這些模型中一些經典演算法問題的不同思考方式~
由於是第一次寫這一類型的文章,還請大家不吝指教(盡量鞭但是拜託鞭小力一點拜託QQ)


下一篇
Day 2: 隨機存取模型(一) Word RAM Model, Part 1
系列文
當傳統演算法遇到新的計算模型21

尚未有邦友留言

立即登入留言