#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 都接收輸入然後產生輸出，這些都是在你專案裡用來解決特定的問題或是達成特定的目標．

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

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

閱讀全文

#73 Coding面試 LeetCode#14 Longest Common Prefix

原題目網址是 https://leetcode.com/problems/longest-common-prefix/description/

這一題在 LeetCode 的難易度分類屬於簡單級，題目的意思是你會得到一個 string array，然後你得從這個 string array 裡面找到最長從頭開始的共同子字串．在題目裡有給了簡單的範例，例如 Input: ["flower","flow","flight"] , 則答案就是 "fl"．如果找不到合適的子字串，就直接回傳空字串．同時題目也告訴你，input 字串只有 a 到 z 之間的小寫字母，不會有其他的符號，這個條件大大降低了答案的難易度，因為可以少一些大小寫辦別或特殊字元或文化上的處理．

解法的邏輯也相對單純．找出最短長度的字串，以它為基礎，然後去比對每一字串從頭開始的字母，以此類推做到有一個字母是不符合條件或是最短長度已經到達．

參考的程式碼如下:



這解法的時間複雜度是 O(n²)，空間複雜度是 O(n)．也許有更快速的解法等待你的尋找．

Help it helps,

閱讀全文

#72 一秒38萬個交易的故事 - 資料庫引擎篇

與資料庫有關的文章到目前為止已張貼了二十二篇文章，這些文章所談論的內容大部份都是描述資料庫引擎裡 Storage 和 Transaction 的內容．資料庫引擎裡的內容當然不只這些，還包括 SQL query parser, query optimizer, logging manager, 以及一些基本的功能如 security control 等等．光是有關 storage manager 的故事就能寫一本書了，除非你想做資料庫引擎的專家才需要知道所有的細節，不然的話，只要了解一些基本的設計便能幫助你在工作上做到更好的境界．在這些二十二篇與資料庫引擎有關的文章，我寫的那些內容其實簡化或跳過不少的細節，但那些細節並不會影響你對資料庫引擎設計的了解，只讓你可以用比較高層次的角度來檢視資料庫引擎會為你做的事情．畢竟這些內容主要的對象是給非電腦科系畢業的資訊人所參考用，因此忽略了許多數學上的推導與比較．若你是電腦科系的學生正在學習資料庫理論，請以課本內容為主，因為課本內容裡面會用一些數學來明確表達運作成本等事情．為什麼要說這些呢 ? 這當然是和本篇文章的主題有關，一個一秒38萬個交易的故事．

這句話是去年阿里巴巴在雙十一的購物節活動後，阿里巴巴的大老闆馬雲所講的．他用總交易數量除以總交易時間，得到一個值就是阿里巴巴的系統在購物節活動時能處理一秒三十八萬筆交易．這是一個相當驚人的數字，也證明了阿里巴巴的工程團隊能得到這樣的水準．其實這樣的水準，既便是連 Amazon 也不見得能有這機會達成，畢竟以美國的人口數和使用量，要一秒鐘達成三十八萬交易數量，似乎蠻難的．中國有更龐大的人口再加上雙十一購物節的熱潮，自然而然能在短時間內形成非常高的使用量．反觀台灣呢 ? 若我記憶正確的話，高鐵訂購系統曾因大家搶票而掛了，江蕙退隱歌壇演唱會的訂票系統也曾發生這樣的事．想想台灣人口才多少人，瞬間能產生的使用量一定遠遠不如阿里巴巴遇到的情況，但很可惜系統掛掉的事情仍是發生了．可能的原因大概有兩種，一種是工程人員無法勝任工作，另一種原因是電腦資源不足．不論是那一種原因所產生的結果都是會令人產生負面的印象．

一個能處理一秒三十八萬筆交易的系統是一個龐大的系統，每個部份都有許多故事可以講，接下來的內容只討論一些與資料庫引擎有關的內容．在網路上我曾看過一篇文章談到阿里巴巴的資料庫交易系統裡為效能改進所做的一些事情，其中最讓我印象深刻的事情是預先建立訂單資料．以資料庫引擎的角度來看，預先建立訂單資料等於把所需要的 page 先建立完成，因此在系統運行的過程中，不會有 page split 的事情產生．請參考之前的文章

• http://www.woolycsnote.tw/2015/07/19-page.html
  
• http://www.woolycsnote.tw/2015/08/21.html
  
• http://www.woolycsnote.tw/2015/08/22-page-3.html
  
• http://www.woolycsnote.tw/2016/04/45-page-fill-factor.html
  

以上這幾篇文章與 page 有關，看完後，你便能了解為何 page split 是件大事，並且也能了解預先建立訂單資料就相當預先把這些 page 都建立完成．等系統運行時，資料庫引擎便不需要在當下建立這些 page，而是直接使用這些 page．簡單的說就是不用做 insert table, 只要 update table 即可．

除此之外，把 foreign key 拿掉也是件對效能有幫助的事情．因為把 foreign key 拿掉就等於讓資料庫引擎不用去檢查 foreign key 對應 primary key 的正確性，也就是讓資料庫引擎少做事情．但這樣做有某種程度的風險，請記得要搭配一些必要的配套措施．這方面的內容請參考之前的文章 http://www.woolycsnote.tw/2015/04/7-foreign-key.html

另外還有一個比較常用的技巧是將 database schema 做 de-normalization 的處理．如果你的程式需要做很多的 table join 時，你得好好考慮 de-normalization 這件事．平常使用量不高時，table join 也許不會造成你太大的影響，一旦使用量一高時，table join 將是個高成本的動作．所以在特別的情況下，將資料做 de-normalization 減少 table join 這能讓資料庫引擎少做許多事情．這方面的內容請參考之前的文章

• http://www.woolycsnote.tw/2018/03/68-table-join.html
  
• http://www.woolycsnote.tw/2018/04/69-table-join.html
  

當整個系統過了尖峰時刻後，再將結果的資料回復到 normalization 的情況下即可．

如果為了特別的目的而需要讓資料庫引擎少做一些事情以讓它達到最大效能的運行情況，都需要進行一些特別處理，上面所講的都是不錯的特別處理，可以有效讓資料庫引擎少做一些事讓它達到盡可能好的運行效能．當然可行的方法不只是這些，還有許多其他從資料角度或硬體角度來思考的方法．這篇文章的主要目的就是幫助大家明白在做這些特別處理的事情時背後所用的原理 (原因) 是什麼，讓你有足夠強大的理由相信這樣做的確是有幫助的，這也是這個部落格的目的．

Hope it helps,

閱讀全文

#71 資料庫引擎 - Deadlock 偵測 (Wait-For graph)

前兩篇文章談完了 table join，接著這篇文章把主題拉回到資料庫的 Transaction．

之前文章曾提過 deadlock 的發生，這在關聯式資料庫裡算是件平常可見的事情．之前曾提過當 deadlock 發生時，資料庫引擎可利用 wait-for graph 來偵測 deadlock 的發生．這篇文章將說明什麼是 wait-for graph．

Wait-for graph 是一個簡單的圖形，是一個有方向的圖形 (directed graph)，也就是它圖形上的邊具有方向性，這裡的方向性用來代表是那一個交易等待那一個交易．如下圖:



上圖的 S(A) 代表某個交易要對 A 物件取得 shared lock，R(A) 代表某交易要對 A 物件進行 read 動作，X(B) 代表某交易要對 B 物件取得 exclusive lock，W(B) 代表某交易要對 B 物件進行 write 動作．在進行 read 動作之前必須取得 shared lock，在進行 write 動作之前必須取得 exclusive lock．

從上圖可得知，T1 等待 T2，因為 T2 正在寫入 B 物件．所以在 wait-for graph 上就會有一個邊從 T1 指向 T2，用來代表 T1 等待 T2．再來， T2 等待 T3 因為 T2 想要寫入 C 物件，但 T3 先對 C 物件進行 read 動作．T3 等待 T1，因為 T3 想對 A 物件進行寫入動作，但在這之前 T1 對 A 物件進行讀取動作．因此就變成了 T1 等待 T2, T2 等待 T3, T3 等待 T1 的情況．這個情況將使得 wait-for graph 會形成一個 cyclic graph ，意思就是圖形裡點的某個點走到其他點上後有可能再走回到原來出發的點，這便形成了一個 cycle．



資料庫引擎在這個 wait-for graph 上來辦別是否有 cycle．如果有，這表示 deadlock 發生了．此時資料庫引擎便得採用設計好的規則來決定該如何解決 deadlock．解決的方法就是讓 wait-for graph 不會有 cycle 的現象．理論上，只要在 cycle 的路徑上把某一個 transaction 刪除即可．通常來說，資料庫引擎會刪除 "年輕" 的 transaction，"年輕" 是用 transaction 啟動時間來決定，因為基本上來說年輕的 transaction 已做過的動作可能比較少，所以刪除他們再重新啟動後比較省點讀取和寫入資料成本．

Wait-for graph 的應用其實蠻廣泛，在資料庫系統或一般的作業系統都會用到它來描述物件之間的關係．甚至在程式開發工具裡，元件之間參考的關係也可以用 wait-for graph 來呈現．當 A 元件參考 B 元件，B 元件參考 C 元件，C 元件再參考 A 元件，這情況將不允許發生，因為在 wait-for graph 裡將會有一個 cycle．

Hope it helps,

閱讀全文

#70 Coding面試 - LeetCode #5 Longest Palindromic Substring

原文網址 : https://leetcode.com/problems/longest-palindromic-substring

這一題與之前曾提過的試驗字串是否為 Palindromic 的題目蠻雷同的．如果搭配 Palindromic 字串的檢驗法用在這題上，可能的解法如下:



從上面的程式碼你可以看到是將所有可能的子字串從大到小的長度逐一檢查是否為 Palindromic．因為題目是要找最長的 Palindromic，所以子字串長度才會從大到小．上述寫法的空間複雜度是 O(1)，但時間複雜度卻是 O(n³) ，主要因為有三個迴圈與字串長度是有關係的．雖然上述的寫法可以在合格的時間內通過 LeetCode 的 test cases，但若你提了這樣的 solution，面試官很有可能會再問你在空間複雜度上還有進步的空間．

如果你從第一篇文章看到現在的話，你應該可以發現我在許多文章都提過不少次 "加速" 的方法．最基本的做法就是用空間換時間．以這題目而言，如果有機會將時間複雜度往下降的話，較簡單做法便是增加空間複雜度，也就是用空間換時間的做法．以這一題來說，要如何用空間換時間呢 ? 簡單的思考是從 "重複" 的動作開始想．在這題中，什麼是重複的呢 ? 大字串往小字串開始找子字串比對時，這便是一堆重覆的過程．當大的字串逐一比對若沒能成功時，便會將字串縮短一個字，然後再逐一比對．在這裡你就可以發現大字串的比對動作和短一個字的字串比對動作有許多是重複的比對．如果可以將這些比對動作的結果先跑起來並且儲存著，而之後大字串要進行比對時，就不用真的地比對，而是到儲存結果的地方將結果讀出來就知道比對是成功還是失敗．當大字串縮短變小字串時，比對結果也是從 "查表" 而得，而不需要真的地進行比對．因此，這個題目比較好的做法如下:



以上這做法的時間複雜度是 O(n²)，成功地下降了，同時空間複複度也上升變成 O(n²)．這種 "查表" 的方法就是演算法裡所謂的 dynamic programming，如果你沒念過演算法的話，基本上很難寫出 dynamic programming 的方法．這需要一點時間的學習和試驗．未來的文章寫到演算法時，再來解釋多一點．

閱讀全文

#69 資料庫引擎 Table Join 的運行方式 - 下集

在 table join 上集的文章裡談到了最基本的 table join 運作的方式，也讓你知道資料庫引擎是如何進行 table join．你可以發現到不論用什麼方式進行 table join，資料庫引擎所處理的資料必須位在記憶體中才能被處理，因此，將資料從硬碟讀到記憶體的次數和方式將是主宰了整個大部份的執行時間．因此，要讓 table join 的完成速度變快就得在資料從硬碟讀到記憶體的過程中去下點功夫．由於資料量有大有小，記憶體的量也有大有小，所以不同情況下可能要採用不同的方法才能達到最好的效果．接下來，這篇文章來談談另一種 table join 的處理方式，稱之為 hash join．

聽到 hash join 的名字就不難想像這是跟 hash function 有關的處理方式．假設有兩個表格 R 和 S ，其中 R 的資料量比較小，並且也假設電腦的記憶體足夠大能讀入它．此時，可以將 R 一次全部讀入記憶體中，然後對 R 裡面的每一筆資料進行 hash 運算，完成後會得到一個 hash table．另外，假設 S 表格的資料量過大而無法一次全部讀入到記憶體，因此必須分批來處理，所以就一批一批地讀入到記憶體，每一批被讀進來後，就將這一些的資料進行同樣的 hash 運算就能知道是否有符合條件的資料在 hash table 裡面．如果有符合，便將結果暫存到 output page 裡．S 表格資料分批完成之後，就將 output page 回傳給使用者．整個邏輯就像下列的 code



假設 R 表格有 m pages, S 表格有 n pages，上面的動作可以看到 R 和 S 的 page 讀入到記憶體的次數只有 m+n 次，並且迴圈裡的動作是 hash function 的計算和尋找，他們是 O(1)，因為跟 R, S 的資料量大小無關．因此整個運作的過程蠻快的．可惜世界不會如此美好，大部份的情況是 R 和 S 往往都遠大於記憶體大小，因此無法將較小的表格一次讀入到記憶體去，於是要再想出其他的方法．有一個不錯的方法叫 Grace Hash Join，它採取兩階段的方式，先對 R, S 的每一筆資料用一個 hash function 做分類，假設分類成 k buckets, 然後再到每個 bucket 裡面再用另一個 hash function 做分類以快速比對資料．整個邏輯如下:



前面用 hash function A 進行 partition 時，其結果是寫入在硬碟中，這稱之為 partition phase．如下圖:



接下來將每個 bucket 依序地讀入到記憶體中來尋找符合條件的資料，這稱之為 probe phase，如下圖:



假設 R , S 分別有 m, n pages，在 partition phase 中，R 所有的 pages 會讀入到記憶體，並且 partition 完成後也會寫入分類好的資料，也是有一樣的 page 數，所以資料庫引擎會有 m 次的讀和 m 次的寫．相同地，對 S 表格而言，也會有 n 次的讀和 n 次的寫，因此在 partition phase 中一共用 2m + 2n 的 page 讀寫．

在 probe phase 中，每個 bucket 都會被讀入到記憶體一次，所以對 R, S 表格來說，一共會有 m + n 次．如果我們不計算寫入 output data 的成本花費，則整個 Grace Hash Join 的動作將用了 3m + 3n 次的 page 讀寫．這個比起上一篇文章裡將的方法大約是 m * n 次要來的好，當 m 和 n 夠大時．

你可以看到依記憶體大小的不同以及資料量大小的不同，採用不同的 join 方式會得到不同的效果．一個好的資料庫引擎便會依照這些條件來決定用何種方式來進行 table join．但不論何種方式，table join 本身就是一個高成本的動作．依此對於超大資料量的表格，不需要 join 的情況是最好的，因此有時為了一些效能成本的考量，才會適當地做一點 de-normalization 的動作讓 table join 可以少見．但這樣做也會產生其他的問題，必須搭配其他的配套措施．

Hope it helps,

閱讀全文

#68 資料庫 Table Join 的運行方式 - 上集

在資料庫引擎中，table join 是一個很重要並且常見的動作．這一篇文章將討論以邏輯上來看資料庫引擎是如何進行 table join 的動作．

假設資料庫中有兩個表格，一個是學生表格，一個老師表格，這兩個表格裡都各自有一個 id 欄位用來代表學生編號與老師編號．對這兩個表格來說，這個 id 非常適合做為 primary key．學生表格裡有一個欄位是老師 id，這用來代表某學生的班導師是某位老師．這是一個一對多的關係，所以只要在學生表格上有一個老師 id 的欄位便能說明這個關係．用一個簡單的 SQL 語法可以用來表示這樣的關係

Select S.Name, R.Name
From S join R
On S.TeacherId = R.TeacherId    ( S = Student, R = Teacher)

假設你是資料庫引擎的程式設計師，需要處理以上的語法並回傳結果，你會怎麼處理呢? 所有的資料都儲存在磁碟中，但運算時你得把資料搬到記憶中才能計算，於是你可能會想到最直覺的方法就是把所有老師和學生的資料放到記憶體中，然後用兩個 for loop 將學生與老師的資料一筆一筆的比對，把比對成功的結果暫存起來，執行完畢之後就把結果回傳給使用者．這方法是假設所有的資料並沒有任何 index 建立的情況下．

以上的想法很直覺，但會面臨到幾個問題．第一個問題是有可能把學生和老師的資料全部載入到記憶體中嗎 ? 如果學生老師人數不多，這是可能的．但如果是一家龐大電子商務公司的訂單與客戶資料呢 ? 資料量一定大於記體量容量，所以把兩個表格的全部資料載入到記憶體是不可行的．因此，當你寫兩個 for loop 做資料比對時，資料必須一批一批地從硬碟載入到記憶體．如同以前的文章提過，所有資料的儲存單位是以 page 為主，所以可以一個一個 page 依序地載入到記憶體，然後對該 page 裡的資料進行比對的動作．如下圖所示:

比如老師表格 (R)  有二個 page，學生表格 (S) 有五個 page．當第一個老師 page 被載入到記憶體，接著第一個學生 page 被載入記憶體進行資料比對，然後再換第二個學生 page 被載入，一直到第五個學生 page，然後再換成第二個老師 page 被載入到記憶體，接著再依序 (反向) 將學生 page 一一載入比對資料．符合條件的資料將被放在記憶體另一個區域，如上圖的粉紅區域．整個比對完成之後，就將粉紅區域的資料回傳給使用者．如果採用這個方法，老師和學生的 page 將被載入 2+5+4 = 11 次．以速度來看，這 11 次從硬碟載入到記憶體的 page 讀取時間應該主宰了這個動作大部份的時間．

如果將以上的點子做一個小改進，也就是將其中一個表格絕大部份的內容載入到記憶體，而另一個表格一次只載入一個 page 到記憶體，如下圖所示 :

假設，老師的兩個 page 一次全被載入到記憶體，而學生表格的五個 page 將依序載入到記憶體，然後進行資料比對．這樣的 page 載入將發生 2 + 5 = 7 次．理論上應該比前一個方式來的好．這也是典型的用空間換時間的方法．

Select S.Name, R.Name
From S join R
On S.TeacherId = R.TeacherId    ( S = Student, R = Teacher)
Where S.Age = 20

上述語法是另外一種情況．如果表格資料的數量很大並且在適當的欄位上 (S.Age) 皆建立 index 的話，那麼就不用將所有的 page 都載入到記憶體中來進行資料比對．只要透過 Index tree 的尋找機制，將符合條件的資料所在的 page 載入到記憶體進行比對．所以，在 table join 時，若能適當地加上條件 (where)  並且該條件有 index，這將對 table join 的處理速度有莫大的幫助．

其實，以上所說的方法用在表格資料不大的情況下都算能應付的過去，但如果表格資料太大時，以上的方法並不具有效率，為什麼呢 ? 顯而易見，你看到了兩個 for loop 的想法是整個運算方式的主體．有這兩個  for loop 在，速度當然是快不起來．因此，下一篇資料庫的文章將介紹更快的方式．

閱讀全文

#67 IT人生 - 有關你的銀行戶頭

最近工作上和生活上寫太多 code 了，用了許多腦筋，於是今晚決定來休息一下  ，來寫篇與 IT人生有關的事情．今天的主題將和錢有關係．

由於我花了太多的時間在學校，當我在博班三年級決定離開學校去工作時，我已經三十五歲了．當時的我，口袋沒什麼錢，只是一個剛離開學校的窮人．以前二十多歲時雖然也沒什麼存款，但錢這件事並沒有真正對自己產生很大的衝擊．這樣的情況在我三十五歲離開學校後沒多久有了很大的改變，因為我當時看到了一個調查．這份調查是台灣一份財經雜誌，針對台灣三十五歲以上的人所做的調查．這份調查的內容主要是詢問被調查者在三十五歲時是否擁有超過一百萬以上的資產．根據這份調查結果，75% 左右的調查者在三十五歲時並沒有一百萬元的資產．當時才發現自己也是在 75% 的這一群人中，仔細想想，一百萬並不是很多的錢，許多人都當成是人生的第一桶金，而自己連第一桶金也沒有，這似乎是件不太妙的事情．在那之後便讓我開始重視有關錢的事情．首先要做的功課就是除了一般的工作薪資以外，還有什麼方式可以增加收入，好為自己的未來與退休生活做準備．接著找了許多資料和評估自己的情況後，我選擇的方式是 "投資"．

投資並不是買樂透，所以不會一夜致富，而是需要透過長時間的慢慢累積才能得到一定的成果，換個簡單的方式來講，在世界上有許多很有希望在未來數年內能快速成長或是獲利穩定的公司，而這些公司中一定可以找到願意將獲利與股東分享的公司，因此只要持有這些公司的股票，享受其股價上升或股息分派的好處．換句話說就是用你的錢去買這些好公司的股份來讓他們幫你賺錢，是一種用錢賺錢的想法．簡單地說這兩三句結論，卻是我用兩三年的時間才決定要採用的投資方式．金融市場裡有許多投資工具，這對我們做軟體的人來說是完全不同的領域，因此自己也必須花時間尋找適合自己的投資工具．

以我自己的情況而言，我選擇的方式是投資某個區域或某個產業的 ETF，比如像台灣的 0050, 0056 等．這類型的 ETF 依照他們的目標將大部份的資金投資在許多的目標公司，因此，這些 ETF 的漲跌和股息將是這些目標公司的總和表現．只要透過長期投入並且將得到的股息再投入產生複利效果，我相信整體的年化投資報酬率一定可以大於 5%．別小看這 5%，想想看，假設你二十年後累積到了二千萬的投資金額，二千萬的 5% 將是一百萬，換句話說，你什麼事都不用做，一年就有一百萬的收入．二十年後在台灣也許一百萬不算很多，但至少可以讓自己過個很安穩的基本生活，而不用擔心中晚年失業或轉業等問題．

接下來，談談另一個與錢有關的事情，稅．在大部份的國家裡，只要有工作收入就得繳稅，這是無法避免的事情．不同的收入所繳的稅率也不同．比如薪資收入和股利收入所採用的稅制就不一樣．少繳點稅也是一種能存下更多錢的方法，但如果你的收入只來自工作薪資，這可能有矛盾．所以，當你在累積資產時，一開始無法降低你的稅，一旦你的投資資產漸漸上升時，股利或是資本利得也將增加，此時你可以有計畫地讓你的薪資 "降低" 以使得稅可以少繳一點．降低的方式有好幾種，比如像結婚，有了老婆和小孩能增大免稅額，比如像買房子或是房租支出，保險支出等來增大免稅額．但這幾年台灣政府對投資的稅制已有點改變，比如證所稅到頭來還是白忙一場，而股利和利息所得還得多扣上一筆健保補充費．這使得台灣股市變成是一個資本利得不用繳稅，但股利所得者卻要繳稅 (所得稅與健保補充費)，似乎有點鼓勵大家儘量炒股而主．這情況與美國的稅制剛好相反．目前來看，美國聯邦政府所採取的方式是持有一年內的股票交易所產生的資本利得和股利是計算個人所得後來計算稅務，而一年以上的資本利得和股利是另外一種算法，這算法會比較優惠，而股利也分兩種，一種是 qualified 股利，也就是股票持有數個月之後所產生的股利，這類型的股利對一般人來說幾乎是免費，因為一般人不太會有一年七八萬美元的股利收入，如果有超過，其算法也是比同級距的所得稅率要低，另一種是 non-qualified 股利，也就是股票在持有數個月之內所產生的股利，這類型的股利將併入一般薪資所得來計算．所以，美國聯邦政府的制度似乎對領取股利的人較為有利．不論你在那一個國家，使用那一種投資方式，都需要了解稅制，因為賺到的錢減掉繳出去的錢，剩下來才是真正留在自己口袋的錢．

這一篇文章講的不深入，不深入的原因是每一項內容都是許多的細節所組成，而且不同的人所得到的結果都會不同．自己得依自己情況來計算．寫這一篇文章最主要的目的就是提醒大家，平常除了努力學習新知識，努力學習新技術以外，也別忘了為自己的財富加點新知，別只當個努力工作賺錢而不知怎麼運用錢的工程師．

閱讀全文

#66 Coding面試 LeetCode #24 Swap Nodes in Pairs

原題網址 : https://leetcode.com/problems/swap-nodes-in-pairs

題目與一般的 List 題目類似，主要都是在考 next pointer 的位置安排．這一題比較特別的是兩兩成雙來交換位置，交換的邏輯並不會太難，用心推演一下就能推導出來，只有處理第一個 node 時需要做點額外處理即可．題目中有特別規定答案只能使用 constant space，也就是指你使用記憶體的量不能和輸入的 List 大小有關係．除此之外，題目也要求不能更改 node 裡的值來做交換位置的方法，所以你該做的就像一般 List 的考題來換 next pointer．參考的程式碼如下:

閱讀全文