#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．參考的程式碼如下:

閱讀全文

#65 資料庫引擎的交易資料鎖定 (Lock) 策略

延續上一次資料庫的交易文章內容，在一個資料庫系統中同一時間可以執行多個交易 (Transaction)．在這同時執行的交易內容中，當遇到共同讀取和寫入同一個物件時，此時便有很大的機會將發生如上一篇文章中提到的資料衝突現象．為了要解決這個現象，資料庫引擎得採取一種策略．以學術的角度而言，策略有好幾種，但比較常見和合理的策略將是本篇文章中將討論的資料鎖定 (Lock)．

Lock

首先定義上一段文字中所說的 "共同讀取和寫入同一個物件"，物件是指交易內容中所感興趣的資料．可能是一筆資料，例如某一個學生的基本資料，可能是符合某條件的資料，例如去年十月份的所有訂單．以邏輯處理而言，通常來說這資料可能只存在於同一個表格，但也有可能存在於多個表格．以實體上而言，資料有可能在同一個 page，但更有可能分散在不同的 page．以邏輯上而言，資料庫引擎可以對一筆資料進行鎖定，也可以對一整個資料表格進行鎖定，或是鎖定某些特定條件的資料．以實體上而言，通常是以鎖定 page 為單位，資料庫引擎比較方便進行鎖定．

資料鎖定策略定義兩種鎖，第一種鎖是共享鎖 (Shared lock)，也就是當交易對某資料進行讀取動作時，則必需先取得共享鎖，共享的意思也就是其他的交易對同樣資料進行讀取時，也會取得共享鎖，代表這資料只供讀取．所以取得共享鎖的交易可以馬上對資料進行讀取．第二種鎖是互斥鎖 (Exclusive lock)，這是當交易對某資料進行寫入動作所需要取得的鎖，其顧名思義，互斥鎖在同一時間只能被一個交易取得使用，如果其他交易也要取得同份資料的互斥鎖，則必須等待．一般而言，我們將共享鎖簡稱為 S lock，互斥鎖稱為 X lock．透過這兩種 lock 便能解決上一篇文章裡所提出的問題．接下來，舉些例子來說明這兩種 lock 如何確保資料鎖定策略能成功．

首先來看下圖的範例，有兩個交易，他們對同一個資料 (A) 先進行讀取動作 (R) 再進行寫入動作 (W)

由於他們將對資料 A 進行寫入，因此他們都需要取得 X lock．假設是 T1 交易先啟動，因此當 T1 啟得 X lock 之後，T2 就得等待．當 T1 完成後 (Commit完成後)，對資料 A 的 X lock 就會被釋出，因此 T2 才能得取資料 A 的 X lock，接著 T2 才能執行．因此，真正的執行情況將變成下圖．

如果執行的情況變成 T2 先啟動，則 T1 就必須等到 T2 執行完成後才能取得 X lock 接著執行．因此，不論是那一個交易先執行，另一個交易都必須等待．這是一個很單純的例子．接下來來看一個對多個資料進行讀和寫的例子．

以上是兩個交易 (T3,T4) 對資料 A,B,C 進行動作, 其中 T3 讀取資料 A，讀取和寫入資料 C，而 T4 讀取資料 A，讀取和寫入資料 B．由於 T3, T4都對資料 A進行讀取，所以他們都會取得 S lock，因此可以同時讀取資料A．之後他們分別對不同的資料 (B ,C) 進行寫入動作，因此取得 X lock時是針對不同的資料，所以不用等待對方就能馬上進行寫入動作．

以上所說的方法是採用漸進式的方式來進行資料鎖定，也就是當交易讀取或寫入某資料時，才需要對該資料取得 S lock 或 X lock，而且 S lock 和 X lock 將決定交易是否馬上繼續執行或是需要等待．因此，這樣的方式對資料庫引擎來說是漸漸增加 lock 的數量，然後在交易 commit 或 abort 時，一次釋放該交易所擁有的 lock，就有如下圖一樣：

DeadLock

以上的策略會讓死結 (deadlock) 有機會產生，主要的原因在於 X lock，舉例如下圖:

當 T1 嘗試著取得資料B 的 X lock，結果資料 B 的 X lock 在被 T2 使用中，因此得等到 T2 完成才行，結果 T2 後面有個動作要對資料A 進行寫入，欲取得資料A 的 X lock 時，此時它正被 T1 所使用，需得到 T1 完成才行．因此就進入了一個你等我，我等你的狀態，也是電腦科學領域中常見的 deadlock 問題．資料庫引擎需要有能力來偵測死結的情況，並且要有能力處理死結．以理論上來說，偵測不是難事，資料庫引擎得維護一個 waits-for graph 來對整體系統裡那些交易在等待那些交易完成，透過 waits-for graph 可讓資料庫引擎偵測死結．這對資料庫引擎來說是一項不得不花費的成本，因為要偵測死結的存在，才能對死結的現象進行解決．解決死結最簡單的方法就是將造成死結的交易終止，好讓其他交易可以順利取得 lock，然後再將被終止的交易重新啟動．無論如何，資料庫引擎在這能做的只是事後的預防與問題的排除，若想要盡量避免死結，還需要程式開發人員的配合．交易是程式開發人員所撰寫，因此在寫交易時要儘量避免死結的發生便很重要．有幾個簡單的準則可供參考:

• 若非必要，不要為你的 stored procedure 設定成以交易的方式進行．
  
• 交易應盡量短．如果交易過長，這表示交易將進行更多的讀取或寫入的動作，無形中也增加了死結的機會．因此，最好把交易分割到最小不可分割的單位．過於複雜的商業邏輯由外面的程式邏輯層執行，資料庫只要做基本的資料操作動作．
• 盡量讓交易對資料有相同順序的讀取或寫入．如前面的例子，死結的發生往往在於你等我，我等你的情況．因此，若把資料讀寫的順序盡可能排成一樣，這樣就能大大減少你等我我等你的機會．

以理論上來說，資料鎖定的策略不只以上介紹的方法，還有其他不同的鎖定策略以及死結預防和處理的方式．不論是用那一種，對資料庫來說都是相對應要付出成本．若能將這方面的成本降低，這將有助於資料庫引擎效能．

閱讀全文

#64 資料庫引擎交易 (Transaction) 進行中的讀寫異常

前面的文章曾談到交易 (Transaction) 需要具有 ACID 的特性．在一個繁忙的資料庫系統中一定會有許多的交易同時執行，這篇文章便來談論許多交易同時執行時會遇到那些挑戰．

許多交易在進行時，非常有可能會遇到對相同的資料進行讀或寫的動作．如果所有的交易對相同的資料進行讀的動作，則這情況並沒有什麼好擔心的，因為所有的交易對這份資料都是讀的動作，早讀和晚讀都是同一個答案，所以不會造成任何的資料異常現象．但如果情況變成其中有一個交易或多個交易對同一份資料進行寫的動作時，那麼早寫和晚寫就會有很大的影響了．因此，我們在乎的情況便是當有交易在進行寫的動作．以下假設某個資料庫系統中有兩個交易，這兩個交易會對同一份資料進行讀和寫的動作:



如上圖所示，T1 做的動作是 A=A-100 和 B=B+100，T2 做的動作是 A=A*1.5 和 B=B*1.5．如果交易執行的情況如上圖的話，假設 A 和 B 的初始值都是 300，你認為當這兩個交易完成後，A 和 B 的值會多少呢 ? 沒算錯的話，A 應是 300，B 應是 550．如果 T1 和 T2 執行的情況不是像上圖一樣，而是 T1 先執行，完成後再執行 T2，此時答案是多少呢? 沒算錯的話，A 還是 300，但 B 是 600．這時你就會發現怪怪的，執行的順序果然會影響答案，這可是不得了的大事呀．如果你把 A 和 B 想像成是銀行中的戶頭，而 T1 就像在執行匯款的動作，T2 就像是在執行加值的動作．這兩組不同目的動作是可以同時被觸發的，但很顯然地你一定發現 T1 在執行動作時，T2 不應該執行，因為他們會對相同的資料進行寫的動作．如果你允許他們可以同時對相同資料進行寫的動作，則就會發生資料異常的現象．所謂資料異常就是指不應該發生的情況．正常的情況是 T1 先執行再執行 T2，或是 T2 先執行再執行 T1．我們再來看另一種例子:



這一個例子是 T1 的讀寫動作完成後 T2 才開始進行讀寫，但最大的差別是 T2 在進行讀寫時，T1 還沒有 commit．等到 T2 commit 完成之後，最後 T1 才決定 abort．這種情況也是我們不希望看到的，因為這也是一種資料異常的現象，因為 T2 在對 A資料進行讀寫時，它的基礎是建立在 T1 對 A 完成的結果上，結果 T1 對其結果是否定的 (abort)，所以 T2 的結果就便成是一個大笑話了．

看到這裡時，你就可以知道當某一個交易對某一個資料進行 "寫" 的動作時，在這交易尚未完成前 (Commit or Abort)，我們不希望其他交易能對相同資料進行 "讀" 和 "寫" 的動作．相同地，當某一個交易對某一個資料進行 "讀" 的動作時，在這交易尚未完成前 (Commit or Abort)，我們也不希望其他交易能對相同資料進行 "寫" 的動作．如下圖所示:



為了防止以上資料異常的現象發生，資料庫引擎裡需要某些特別的設計來防止這類的事情發生，這個特別的設計稱為 Locking．也就是當某交易在對某份資料進行動作時，便把該份資料鎖住讓其他交易無法使用該資料．下一篇文章將會來談談這個鎖資料的內容．

閱讀全文

#63 出神入化的用介面 第三集_修改共用的介面

上一集的內容中曾提過三個團隊負責三個不同的元件，團隊一負責 ClassLibrary1，團隊二負責 ClassLibrary2，團隊三負責主要的 UI 主體 (WindowsFormApp1) 以及 CommonLibary．你可以把這三部份的功能想像成是一個普通的軟體產品．在產品演進的過程中勢必會再提供更多的功能，這可能會讓 ClassLibrary1 和 ClassLibrary2 之間的互動會更多，這也代表修改共用的介面 (在 CommonLibrary 裡) 是必需的．如果這三個團隊擁有一致的產品釋出時程，則共用 Interface 的修改並不會造成任何影響．但如果不是如此，則修改共用的 Interface 將會是個棘手的事情．



接下來，我們來看三個團隊的產品釋出時程是不一樣的情況．團隊一所負責的 ClassLibrary1，因其功能很容易受到市場影響，所以有著較短產品釋出時程，每隔二個月就會推出新版本．團隊二和團隊三所負責的 ClassLibrary2, CommonLibrary, WindowFormsApp1 是一些基本且較少變動的功能，所以其產品釋出的間隔較長，大約每隔半年才需要更新一次．所以一年裡，ClassLibrary1 會推出六個新版本，ClassLibrary2, CommonLibrary, WindowsFormsApp1 只會推出二個新版本．ClassLibrary1 可以各自獨立釋出，不受限要和 WindowsFormsApp1 或 ClassLibrary2 一起釋出．

共用的介面仍維持跟前一個版本一樣的狀態．如上一集所講的，其共用介面的長相如下:

public interface IOperation
{
    string Name { get; }
    string Description { get; }
    int AddIntOperation(int i);
    string ChangeStringOperation(string input);
}

假設今天團隊二和團隊三釋出新版的 ClassLibrary2, CommonLibrary, WindowsFormsApp1，其中 ClassLibrary2 也提供一個新的 method 給 ClassLibrary1 使用．於是就會遇到以下的問題:

1. 如果直接修改 IOperation，將新的 method 定義加上去的話，那麼對舊版的 ClassLibrary1 會造成問題，因為 IOperation 有不同的 interface 定義．
2. 在不久的未來, ClassLibrary1 也將釋出新版，它可能會被更新在舊版的 WindowsFormsApp1 上，也可能被更新在新版的 WindowsFormsApp1 上，ClassLibrary1 怎麼知道它所面對的 IOperation 是新的還是舊的呢?

問題當然不止這兩個，但這兩個算是最麻煩的了．首先，IOperation 在舊版裡只有三個 properties 一個 method，在新版裡多了一個 method，變成三個 properties 兩個 methods．如果直接對 IOperation 上修改，這一定行不通的，因為現有版本的 ClassLibrary1 認得的 IOperation 是三個 properties 一個 method．因此，為了讓現有版本的 ClassLibrary1 能繼續使用，所以 IOperation 不能變動．為了讓新版的 ClassLibrary2 提供新的 method，最簡單的方法就是創造一個新的 interface，並且將它繼承 IOperation，如下所示:

public interface IOperation2 : IOperation
{
    int MinusIntOperation(int i);
}

IOperation2 是 IOperation 的小孩，所以 IOperation 有的，IOperation2 都有，並且 IOperation2 增加了一個 method，用來實現 ClassLibrary2 提供的新功能，在 ClassLibrary2 會有一個新的 class 用來實作 IOperation2 的內容．這樣的做法解決了上面所提的第一個問題．一旦新版的 ClassLibrary2, CommonLibrary, WindowsFormsApp1 被釋出時，此時的 ClassLibrary1 還沒有新版，所以 ClassLibrary1 只認得 IOperation，不會認得 IOperation2．而 ClassLibrary2 和 CommonLibrary 裡都把 IOperation 的相關內容都保留了，因此新版的 ClassLibrary2 還是能照常提供原有的功能給 ClassLibrary1 使用．

接下來 ClassLibrary1 也要釋出新版了．因為 IOperation2 已經釋出了，所以新版的 ClassLibrary1 必須設計成要能使用 IOperation2，同時新版的 ClassLibrary1 也必須保留原有的功能．接蓍 ClassLibrary1 就面臨到上述第二個問題，也就是 ClassLibrary1 被下載更新時，它有可能被更新在舊版的 ClassLibrary2 上 (沒有 IOperation2)，也有可能被更新在新版的 ClassLibrary2 上 (有 IOperation2)．此時 ClassLibrary1 怎麼知道它被下載更新後所面對的是舊版還是新版的 ClassLibrary2 呢? 方法應該有好幾種，在這提供兩個簡單且直覺的．

第一: ClassLibrary1 可以檢查 CommonLibrary/ClassLibrary2 的 assembly version 或是 file version．因為 IOperation2 隨著新版的 ClassLibrary2, CommonLibrary, WindowsFormsApp1 釋出，所以 ClassLibrary1 可以知道他們釋出時的版本資訊．

第二: 當 ClassLibrary1 想要使用 IOperation2 時，並不直接使用它．因為 IOperation2 是 IOperation 的小孩，所以當 ClassLibrary1 得到來自 ClassLibrary2 的物件時，一律先將它視為 IOperation，這樣就可以成功讓該物件進入到 ClassLibrary1 的領域中，然後再試著將該物件轉型 (type conversion) 成 IOperation2，如果可以轉型成功，那代表該物件是實作了 IOperation2，也就表示 ClassLibrary1 面對的是新版的 ClassLibrary2．以下是 ClassLibrary1 裡嘗試使用 IOperation2 的簡單 code:

if (ObjectContainer.Operations.TryGetValue("operation2", out IOperation op))
{
    IOperation2 op2 = op as IOperation2;
    if (op2 == null)
    {
        richTextBox1.Text = "We are using older version of interface";
        return;
    }

    int result = op2.MinusIntOperation(100);
    richTextBox1.Text = $"We are using a new version of interface and the result is {result}";
}
else
{
    richTextBox1.Text = "Cannot find Operation2";
}

以上的情況在一般的大型軟體系統中其實是很常見的，解決的方法當然不止如上述的方法，而上述的內容也是用在 Visual Studio 裡，中間有很多細節省略了，但重點就是修改共用 interface 時，是生一個小孩來繼承它，把原有的 interface 原封不動地保留．

閱讀全文

#62 Coding面試 LeetCode #236 Lowest Common Ancestor of a Binary Tree

原文題目在 https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree．

題目是說給你三個 TreeNode, 第一個 TreeNode 是這個樹的 root, 第二個和第三個 TreeNode 是這顆樹裡面任意兩個 TreeNode. 所以，題目都這樣說了，你就不用擔心它會給你一個不在這顆樹裡面的 TreeNode．題目問你要在任意給你樹裡面兩個 TreeNode 後，你要找出這兩個 TreeNode 最低位置的父節點．所謂最低位置是指離 root 越遠越好．

看到這題目便想到跟 TreeNode 往上走到 root 的路徑有關，因為你要找的就是從任意兩 TreeNode 出發，會在那一個 node 第一次相遇．有一個很直覺的想法是在這兩個 node 一起往上走，但問題來了，你怎麼知道往上走要走到那去呢 ? 再者，任意兩 node 一起往上走不見得會在最小高度的 ancestor node 剛好碰在一起，因為任意兩 node 的高度不見得是一樣的．我當初想這一題時，便沒有想到要讓兩個 node 一起往上走，而是先讓其中一個 node 一直往上走到 root，把經過的 node 都記錄下來，完成之後便開始另一個 node 往上走，每往上走一個 node 時便比較第一個 node 是不是有走過同樣的 node，如果有的話，就代表找到了，如果沒有的話，就繼續往上走，一直到找到為止．

因此，我們需要把整顆樹的 "路徑" 和第一個參數 TreeNode 往上走的 "路徑" 記錄下來．在這裡，比較特別的是用 Dictionary (Hash table)，而不是用 List．第二個參數的 node 只要在每一層往上走的過程中，檢查該位置的 node 是否在於第一個參數 TreeNode 的 "路徑" 就好了，其參考程式碼如下:

為何 Root 和第一個參數 TreeNode 的路徑是用 Dictionary (Hash table)，而不是用 Stack/Queue 或 List 來記錄路徑．答案在以前的文章已經說明過了，這點就留給讀者想一想．

閱讀全文

#61 出神入化的用介面 第二集_物件如何在大型軟體系統中移動

在上一集中談到最基礎的 interface 應用和簡單的例子，因此從上一集的內容中應該能讓你了解到 interface 的用途之一．interface 的用途很廣，除了可以做一些物件抽象化的表示方式以外，也可以用來幫助一個物件在一個大型的軟體中不受元件範圍的限制而讓其他不同的元件來使用．在上一集的內容中，你已經看到了最基本的抽象化應用，透過 email interface 的建立，讓所有的團隊可以依照同一份 interface 的規格實做出各自所用的物件，在這一集的內容中將展現一個極為簡單的例子用來說明一個物件如何在大型的軟體系統中移動．

首先，簡介此簡單的例子，下圖是這例子中的元件，一共有四個元件:


WindowsFormsApp1.exe 是整個軟體的基礎，它提供 IDE 介面，以及負責尋找系統上有那些元件，並且呼叫各元件的註冊程式，將每個元件所提供的功能記錄下來．

CommonLibrary.dll 是一個讓各元件都能使用到的共用內容，如一些共用的 interface 定義以及元件被註冊時所需要的空間．

ClassLibrary1 包含了該元件所提供的 Form 和相關的功能，同樣地，ClassLibrary2 也包含了一些 Form 和相關的功能．

上圖中的線條代表 dependency 關係，所以 WindowsFormsApp1 認識另外三元件，ClassLibrary1 只認識 CommonLibrary，ClassLibrary2 也只認識 CommonLibrary，所以 ClassLibrary1 和 ClassLibrary2 彼此並不認識，最後 CommonLibrary 完全不認識其他元件．這裡所用的 "認識" 就是 reference 的意思．

假設以上四個元件分別是由不同的團隊所製作而成，現在 ClassLibrary1 圖隊需要在他們自己的 Form 上面做兩個按鈕，而這兩個按鈕所需的畫面和功能分別是由 ClassLibrary2 團隊所提供的．正常來說，如果一個團隊要用到另一個團隊所開發的功能時，最直接且直接的方法就是將對方的元件在自己的專案中加入 reference，這樣做就能讓自己團隊的元件可以認識另一個團隊的元件，但這樣子做在較大型的軟體團隊中是不方便的，因為第一集已經說明過了．因此，如第一集所說的內容，比較好的方法是要做一個共用的 interface 讓兩個團隊都可以認識這個共用的 interface．於是，ClassLibrary1, ClassLibrary2, 和 CommonLibrary 這三個團隊做成了一個協議，CommonLibrary 團隊將製作一份 interface 讓 ClassLibrary1 和 ClassLibrary2 可以實做．除此之外，CommonLibrary 團隊還提供了一個 Dictionary 用雙方可以將自己實做好的元件放在這個 Dictionary 裡頭．

public interface IOperation
{
    string Name { get; }
    string Description { get; }
    int AddIntOperation(int i);
    string ChangeStringOperation(string input);
}

public class ObjectContainer
{
    public static Dictionary<string, IOperation> Operations = new Dictionary<string, IOperation>();
    public static Dictionary<string, Form> Dialogs = new Dictionary<string, Form>();
}

IOperation 介紹讓是讓雙方可以依自己的邏輯實做成物件，然後放在 Operations dictionary 裡面．因此，只要 ClassLibrary1 團隊知道如何在這個 dictionary 中取出 ClassLibrary2 所放入的物件，那麼 ClassLibrary1 可以使用 ClassLibrary2 團隊所提供的功能了，如 AddIntOperation(), ChangeStringOperation()．

於是 ClassLibrary2 團隊將 IOperation 實做如下:

public class Operation2 : IOperation
{
    public string Name => "Operation2";

    public string Description => "This is Operation2 from ClassLibrary2";

    public int AddIntOperation(int i)
    {
        if (i < int.MaxValue - 1)
        {
            return i + 2;
        }

        return i;
    }

    public string ChangeStringOperation(string input)
    {
        return string.IsNullOrEmpty(input) ? null : input.ToLower();
    }
}

然後 ClassLibrary1 團隊在一個按鈕的 code-behind 寫出以下的程式碼來使用 ClassLibrary2 的 IOperation.

private void button2_Click(object sender, EventArgs e)
{
    if (ObjectContainer.Operations.TryGetValue("operation2", out IOperation op))
    {
        int i = 5;
        richTextBox1.Text += $"int starts at {i}\n";
        i = op.AddIntOperation(5);
        richTextBox1.Text += $"int becomes {i} after Operation2\n";

        string s = "aBc";
        richTextBox1.Text += $"sting starts as {s}\n";
        s = op.ChangeStringOperation(s);
        richTextBox1.Text += $"string becomes {s} after Operation2";
    }
    else
    {
        richTextBox1.Text = "Cannot find Operation2";
    }
}

這樣做的話不能成功，因為在 CommonLibrary 的 Operations dictionary 裡面並沒有 ClassLibrary2 所製做的 IOperation 物件，因此 ClassLibrary1 團隊使用上述的程式碼時會看到 "Cannot find Operation2" 的訊息．比較簡單的方法是在整個軟體一開始啟動的時候，ClassLibrary2 就得把 IOperation 物件寫入到 CommonLibrary 的 Operations dictionary 裡．當然，這並不是最好的方法，只是在這極為簡單的例子中，我們暫用這個方法來簡化許多細節．

因為 WindowsFormsApp1 是整個軟體的啟動點，所以我們就在 WindowsFormsApp1 啟動的時候來將相關的物件都寫入到 CommonLibrary 裡面．由於每個團隊會有不同的啟動邏輯，因此，每個團隊可以提供一個入口來讓 WindowsFormsApp1 直接呼叫，而這份入口裡的內容就是將自己的 IOperation 物件寫入到 CommonLibrary 的 Operations dictionary 裡．同樣地，除了 IOperation 以外，每個團隊也可以寫入不同的 Form 物件到 CommonLibrary 的 Dialogs dictionary 裡．

以下是 ClassLibrary2 團隊所使用讓 WindowsFormsApp1 執行注冊的內容:

public static class Starter
{
    public static void Register()
    {
        ObjectContainer.Operations["operation2"] = new Operation2();
        ObjectContainer.Dialogs["library2"] = new Lib2WinForm1();
    }
}

以上的做法是一個極為簡化的方式，在 ClassLibrary2 裡直接做一個 static method 讓 WindowsFormsApp1 呼叫，所以 WindowsFormsApp1 必須知道這一個 "入口"．在正常的方式來說，WindowsFormsApp1 找到並執行 ClassLibrary2 的入口不會用這種直接的方法，因為這樣會把程式碼限制住，這方面細節的內容以後將再寫文章來說明，現在就先假設 WindownsFormsApp1 可以找到 ClassLibrary2 並且執行 Starter.Register() 來達成將 Operation2 物件和 Lib2WinForm1 物件寫入到 CommonLibrary 的 dictionary 中．因此，WindowsFormsApp1 的啟動程式看起來如下:

static class Program
{
    [STAThread]
    static void Main()
    {
        // 尋找相關元件並且執行他們所提供的註冊方法
        ClassLibrary1.Starter.Register();
        ClassLibrary2.Starter.Register();

        Application.Run(new Form1());
    }
}

這樣一來，ClassLibrary1 團隊就可以在 CommonLibrary 的 dictionary 裡找到 ClassLibrary2 所製做的 Form 物件以及 IOperation 物件，並且使用它們，如下圖所示:



Form1 是 WindowsFormsApp1 團隊製做的主要 Form，也就是整個軟體最基礎的 IDE，而 Lib1WinForm1 是 ClassLibrary1 所製做的 Form，透過 WindowsFormsApp1 的呼叫將它顯示在畫面上．在 Lib1WinForm1 裡第一個按鈕 (Let's show Lib2WinForm1) 的 code-behind 如下:

private void button1_Click(object sender, EventArgs e)
{
    if (ObjectContainer.Dialogs.TryGetValue("library2", out Form lib2WinForm1))
    {
        lib2WinForm1.ShowDialog();
    }
}

直接到 CommonLibrary 的 Dialogs dictionary 去找是否有 CommonLibrary2 的 Form 物件，如果有找到，就直接對它做 ShowDialog()．因此，ClassLibrary1 團隊不一需要 "認識" ClassLibrary2 團隊的元件也可以將它提供的 Form 顯示在畫面上．

同樣地，Lib1WinForm1 的第二個按鈕 (Run Operation2) 是使用 ClassLibrary2 的 IOperation 物件所執行的功能，它的程式碼如下:

private void button2_Click(object sender, EventArgs e)
{
    if (ObjectContainer.Operations.TryGetValue("operation2", out IOperation op))
    {
        int i = 5;
        richTextBox1.Text += $"int starts at {i}\n";
        i = op.AddIntOperation(5);
        richTextBox1.Text += $"int becomes {i} after Operation2\n";

        string s = "aBc";
        richTextBox1.Text += $"sting starts as {s}\n";
        s = op.ChangeStringOperation(s);
        richTextBox1.Text += $"string becomes {s} after Operation2";
    }
    else
    {
        richTextBox1.Text = "Cannot find Operation2";
    }
}

當這個按鈕被按下後，它的結果如下:



你可以看到數字被加 2 (7 = 5+2) 並且字串變小寫 (abc)，這都是前面提到 ClassLibrary2 所實做 IOperation 的內容．

當我們把 Visual Studio 的 break point 設定在這程式碼時，你會看到如下畫面:



此時，你可以看到 op 的 data type 是 IOperation，而它裡面真正的物件是 ClassLibrary2.Operation2．

這個範例用極為簡化的方式說明了 Interface 如何幫助 ClassLibrary2 團隊的物件可以在 ClassLibrary1 的程式中呈現，並且是在兩團隊元件互相不 "認識" 的情況下．

Operation2 的實做完全保留在 ClassLibrary2 裡面，其他團隊無法變更，也不需要知道實做細節，讓團隊之間的合作只需要關心 Interface 的定義．

用這個例子可以讓你看到不同的團隊各司其職而達成一個共同的目標．以上的例子 IOperation 是定義在 CommonLibrary，通常來說，自已團隊所開發的 Interface 應該是放在自己所定義的 Interface 元件裡，然後再將這一個 Interface 元件公開給其他團隊來使用．因此，這份 Interface 是大家都看的到，理論上你就不能修改，否則別人用了就會出現問題．下一集的內容將說明當公開共用的 Interface 需要修改時，該怎麼處理比較好．

閱讀全文

#60 Coding面試 LeetCode #199 Binary Tree Right Side View

原文網址在這裡

這題是一個標準的走訪樹節點的題目．這題多一個限制，就是只抓出每一層最右邊的節點．因此，最簡單的方法就是用 breadth first 的走法，把每一層逐漸地一層層往下走．在每一層走完要往下一層走之前，把該層最後一個走到的節點儲存到欲輸出的 List 上即可．這題參考的程式碼如下:

通常來說你不會遇到一模一樣的面試題目．我能想到有關這一題的變化就是要能得到左右兩邊看的結果，或者是主考官規定你要用 depth-first 的走法來得到答案．有興趣的話，不妨試著寫寫這兩種變化題目．

閱讀全文