#76 演算法裡一個基本的觀念 - Reduction

Reduction 是一個在演算法知識裡基本且簡單的觀念．其實在各位的工作中也一定常用到這觀念，只是你不知道而己．在這文章裡一如往昔，不用學術理論的描述方式，而是用平常寫程式的例子來讓非電腦科系畢業的資訊人了解什麼是 Reduction．

接下來用寫程式的角度來看什麼是 Reduction．假設你需要寫一個影像辨識的程式，這個程式需要辨識一個圖片裡是否含有某個數字，所以你寫的 function 可能會像下列:



以上的程式碼尚未完成，部份內容先暫以文字描述表示．你可能不是一個影像辨識的專家，完全不知道該怎麼做數字辨識．所以你一定會尋找可能的方法來執行這項任務．最後，你找到一個程式可以做這項工作，它的程式碼如下 (數字辨識的內容用文字描述代替):



由於 DetectNumber() 是別人完成的程式，假設你僅知道它是可用的，但無法了解其中的運作內容．你可以將它視為一個黑盒子．至於黑盒子裡面是怎麼運作的，由於能力與知識不及，所以暫時無法了解．但不了解也不代表不能使用，你只要知道這個黑盒子需要的輸入和輸出是什麼資料型別，就可以將它套用到你的程式裡．

接下來，我們將 DetectNumber() 套用到 ContainNumber() 裡面，所以完成後的 ContainNumber() 如下:



如此一來， ContainNumber() 就能做到它需要的功能了．從寫程式的角度來看，你會覺得這不就是每天工作在做的事情嗎 ? 是的，你每天寫程式所做的事情都是讓程式呼叫東呼叫西，在這一連串呼叫的過程完成自己所需要達成的功能．當一個演算法呼叫另外一個演算法來達成某項功能時，這就是一個 Reduction．也就是說，ContainNumber() 要做的事情，其實 DetectNumber() 也能做的到，差別只是輸入輸出的資料型別不同而己．將 ContainNumber() 的輸入型別轉換一下，就能形成 DetectNumber() 的輸入型別，然後將 DetectNumber() 的輸出型別轉換一下，就能變成 ContainNumber() 的輸出型別．再換個角度想，ContainNumber() 和 DetectNumber() 要處理的問題核心其實是同一個，只是問法和要求的答案有點小差別而己．在演算法的世界裡，某些問題的解法能變成另一些問題的解法，靠的就是這種 Reduction 的技巧．只要你能找出問題的本質是一樣時，解法就很接近了．

Hope it helps,

閱讀全文

#75 將問題和演算法分類

學習基礎的演算法過程中，許多課本最常用的方式是將問題分類好，然後對每一類問題進行討論並給出一些著名的演算法來解決這一類的問題．因此，要了解自己面對的問題屬於那一類型的問題便是件重要的課題．在這一系列的文章中，我的目的並不是要告訴你大學課程的演算法內容，而是希望用一種比較實際工作上會遇到的普遍情況來說明在工作中可能會碰到跟演算法課本內容有關係的課題．就像上一篇文章提過的，演算法的內容就像是你寫的程式裡某一個 function，每一個 function 一定有一個特定的目的．因此，你可以想像世界上存在許多的演算法，每一個演算法都有一個目的．當你認識了許多演算法時，有一個簡單的方法來分類演算法的種類，就是按照目的來分類．只要你知道你的問題是屬於那一類，這樣你就知道該去找那一類的演算法．例如，你的工作裡某一個任務需要將資料庫中的訂單做排序，因此，你就可以在市面上找到許多的排序演算法，挑一個適合用在你的工作裡．排序是一個相當簡單的例子，你甚至不用找演算法，因為這類基礎的演算法都已被實做在許多產品裡．另外一個例子，你的工作是做一個檢查文章裡的英文字是否拼錯，如果拼錯的話，必須列出一些建議清單來讓使用者選擇．這一類的演算法通常不會在一般的 class library 裡面內建好，因此你得自行尋找可用的演算法．這類的演算法比較像在算字和字之間的相似度，或稱為字和字之間的距離，如 nprth 是使用者誤打的字，可能正確的字是 north，因為 o , p 在鍵盤位置上就是隔壁而己．有一個演算法能幫你計算字和字之間的距離，請參考 https://en.wikipedia.org/wiki/Levenshtein_distance

透過上述的說明，你可以明白若進入一個自己不懂的領域，要針對該領域的問題找出適合的演算法來解決問題，這是需要花費時間學習．另外還有一個簡單的分類方式是用實做的方法來進行分類．例如，你的工作安排工廠裡產線的機器，每個機器會有不同的維修周期，不同種類的機器也會有不同的處理量，而產線上機器之間的順序是不會變的，就像一定得先把模具做出來，才能做各式機械加工處理，完成後才能噴塗料等等的程序．你老闆希望你能設計一個機器運作方式讓機器運作的情況是最佳的，也就是說產線的產量是最大的．像這樣看起來就是一個 “最佳化” 的問題，在演算法課本裡面會談到許多最佳化的問題．以這問題來說，採用 linear programming (未來文章會介紹) 是一個可能的解法之一．但要注意的是，並不是所有 “最佳化” 的問題都能用 linear programming 來找到最佳值，上述問題的限制給的很多，因此無形中幫你把問題的範圍縮小，解法也相對變簡單．如果問題的限制變少了，如加工製程的順序是不重要的，拿掉就個限制就讓整個問題變得很難用一個簡單的演算法找到最佳解，難的不是找不到答案，而是一旦問題的輸入量變大 (機器變多)，找出解答的時間 (演算法內的步驟) 就會以不成比例的方式往上增加，也就是說演算法的 Big O 變大．用寫程式的角度來看，一旦限制條件變少，程式就必須做更多的步驟來尋找各種可能以得到最佳值，這相當於 for loop 會變多了．Big O 漸漸變大時，此時你就得思考其他的解法方法，如果你的情境不需要最佳解，則採用一些近似解法來尋找接近最佳解的解答，而且通常近似值解法的速度都會比最佳值解法的速度來得快很多．

分類的情況實在太多了，無法一一描述．在這邊希望帶給非電腦科系畢業的資訊人一個觀念就是學習演算法的過程中，要先了解把問題分類，並且也知道一些常見問題分類裡一些著名的演算法．我們不需要發明什麼了不起的演算法，以我個人的經驗是，能夠善用許多聰明人為解決某些問題而想出來的演算法，這就已經夠利害了，同時也能幫助你寫出好程式．畢竟，對非本科畢業的資訊人來說，不是遇到一個不會的問題就用暴力法來解決．即便是一個看似很簡單的工作人員排班表的事情，用暴力法，它的 Big O 可是很大的．又比如你是做地圖導航的工程師，你要安排一個最短路徑從某一個點到另一個點，若沒有好的演算法，你能想像你用暴力法來解決，那將是什麼程度的 Big O 嗎 ?

最後，你可能會問，你明白分類的重要性，則到底有那些分類呢 ? 老實說，我回答不出來有那些分類．通常我的方法是看問題的資料輸入類型和問題的重點來決定．例如，問題是一個最佳化問題，例如找出成績最好的前十名學生，或是訂單金額最高的前十名，資料輸入類型是一個 List 或 Array，一堆資料庫來的訂單或學生清單，而問題的重點是在最佳解，像最大值，最小值，或某些子項目是符合某個條件，這一類的解法通常像之前一些 Coding面試文章的解法那樣．再困難一點，問題是一個觀光路徑排列的問題，資料輸入類型是一個 Tree 或 Graph，像一個地圖，而問題的重點是依照某個條件做排序，例如觀光景點參觀順序從低海拔排到高海拔，此時除了要了解基本的 Tree, Graph 的資料結構運作之外，最後還得讓排序演算法派上用場．不論怎麼分類，其實你都能感受到問題都是傾向某一種 “最佳” 的方向靠近，而且善用好的演算法就是希望結果能快速地被運算出來，也就是 Big O 盡可能低．如果問題不需要傾向某一種 “最佳” 的方向靠近，那麼程式隨便亂寫，最後能跑出答案就行了．

雖然每個演算法都有特定目的用來解決特定問題，不同的問題之間有可能用相同的演算法來解決嗎 ? 答案是有可能的，這是下一篇文章的重點．

Hope it helps,

閱讀全文

#74 演算法從零開始

資料結構和演算法算是最基礎而且重要的知識．若沒有這兩個科目的足夠知識的話是很難在其他電腦科學領域有所進步的，其中也包括程式設計這一條路．基本上來說，程式設計這條路需要強大的邏輯基礎，除了你得對 if .. else .. for loop 用的很熟練外，你還得了解你所用的 SDK, framework 的優缺點，這樣使用起來，你才知道你的 SDK, framework 為你的程式做了什麼事情．除此之外，你便需要知道資料結構和演算法的基本知識，這兩個學科是能幫助你寫出好程式的關鍵．

從前面的文章裡，我談了許多資料結構及其應用，也談了許多面試考題．當你看完那些文章後，你應該能抓到一個重點，這重點就是儘量地省時間 (省運算步驟)，不然的話，就得用空間來換時間 (提高空間複雜度來降低時間複雜度)．雖然每一種問題的情況都不一樣，不見得都能用空間換時間，但至少這是一個讓你思考的方向．演算法在這過程中扮演了重要角色，因為這門學問能幫助你辨別問題，知道什麼樣的問題 “應該” 要用什麼樣的解法．如果沒有好的解法時，也可以得到盡可能好的解法．

你可能會覺得，有這麼神奇嗎? 基本上是的，大學裡學的演算法只是一個開始，並不是包山包海．這門學問可幫助我們辨別問題，同時提供好的解法．許多特定領域的問題，如人工智慧，資料庫等領域，都是需要演算法的基礎知識才能繼續在該領域裡研究和學習．常常也會發現類似的演算法或想法被用在不同的系統中．例如，資料庫常用 B-tree 來幫助快速搜尋資料，相同的做法也能放在作業系統中用來快速尋找檔案．這是典型的用空間換時間的做法，同時也是演算法中 Divide & Conqure 的概念．

說了這一些，到底演算法是什麼 ? 在演算法的課本裡你可以找到正式的學術說明來定義什麼是演算法．以下是我用不學術的方式來簡單定義演算法: 演算法是一連串的運算，這運算會有輸入端 (你的問題)，然後會有輸出端 (問題的答案)．演算法也可以視為一段程式碼，既然是一段程式碼，之前在資料結構裡提到的空間複雜度和時間複雜度也同樣適合在這裡做分析用途．但有一個重點，演算法裡這一連串的運算應該是有盡頭的，也就是能夠跑的完，而不是一直無窮迴圈跑下去．所以，每個演算法的目的就是解決問題 (輸入端)，然後產生解答 (輸出端)．如果用你工作上的專案來看的話，在你程式裡的大部份的 method 都是一個演算法，因為這些 method 都接收輸入然後產生輸出，這些都是在你專案裡用來解決特定的問題或是達成特定的目標．

當你看到這裡時，你可能會認為演算法就像是一般的程式一樣，這樣想也沒什麼不可．但為什麼演算法常給人一種好像是個高深學問或是很難的感覺，我只能說你可能從網路上看到的先進應用都是需要特別的演算法，這些特別演算法不是那麼容易可以想的出來的，自然而然給你一些既定印象認為演算法好像很難．如前面所提的，大學課程裡面教的演算法並非是為了解決特定問題，而是把世界上常見的問題做分類，並且介紹每一個分類裡一些著名的演算法用來解決這些問題．

把這篇文章做為介紹演算法的第一篇文章，正式開啟演算法之路．

閱讀全文