The two most important days in your life are the day you were born and the day you find out why. -Mark Twain

#86 貪心方法是最佳解 ?

最佳解? 這種解答是許多問題所追尋的目標.例如,在一個城市裡找到出發點和目的地的最短距離.直覺來看,若你沒有把所有可能的路徑列出來,你怎麼知道那一個才是最短的.再舉例一個例子,在一個 int array 裡面,找出最大值的元素位置.若你沒把所有的元素都拜訪一遍,你怎知道那一個才是最大的.這兩個例子雖然都是在找 "最佳解",但是解法的思考卻不太一樣.第二個例子的思考是 "一條路",而第一個例子是 "多條絡".在 "一條路" 的情況下,對下一個步驟來說沒什麼好選擇的,只能一直往前走.然而,"多條路"的情況下,在什麼路口選擇什麼路,這對答案或執行過程會有很大的影響. 

前面已有兩篇文章簡單地介紹了貪心方法.這篇文章要討論的是利用貪心方法得到的解答會是最佳解嗎 ? 用一個簡單的問題來測試.假設郵局提供的郵票面值如下:

$10, $5, $2, $1, $0.5, $0.2, $0.1 

現在你要寄一封信,它所需的郵資是16.1 元,請問最少要用幾張郵票 ? 這是一個最佳解的問題,目的是要找最少的郵票數量. 使用貪心方法來解這問題,它所需的程式碼如下:

以上的程式範例就是一個貪心方法.從最大的面值一直嘗試到最小的面值,一直湊到超過所需要賺買的郵票面值. 得到的答案是 $10, $5, $1, $0.1,需要四張郵票,面值是 10, 5, 1, 0.1 剛好能湊到 16.1,並且也這麼湊巧,四張郵票剛好是最佳解.

如果把郵票的面值改變,新的郵票面值有 

$5, $3.7, $3.1, $2.9, $2.3, $2, $1.7, $1.3, $1, $0.5, $0.2, $0.1

當我們再用同樣的程式去執行時,得到的答案會是 $5, $5, $5, $1, $0.1 ,需要 5 張郵票.但你認真排列之後,你會發現有一個更好的答案,那就是 $5, $3.7, $.3.7, $3.7,只需要 4 張郵票即可.此時便可發現貪心方法並無法保證我們一定能夠得到最佳解.如果得到最佳解,只能說題目本身的特性剛好能讓貪心方法得到最佳解而己.

從第一個問題來看,最佳解的答案有幾個特性

1. 答案最多一個 $0.1,因為若有兩個以上的 $0.1,便可以用 $0.2 來替代.

2. 答案最多兩個 $0.2,因為若有三個以上的 $0.2,便可以用一個 $0.5 和一個 $0.1 來替代.

3. 答案不會存在兩個 $0.2 和一個 $0.1,因為可以用一個 $0.5 替代.

還有一些其他的特性可以類推而得.同時,第二個問題可以用同樣的方式來找出最佳解的特性.第二個問題的其中一個特性就是,不該出現兩個 $5, 一個 $1 和一個 $0.1,因為可以用三個 $3.7 來替代,所以我們用貪心方法所得到的答案便不會是最佳解.


Share:

#85 如何聘用適合的軟體工程師

如果你是一個團隊的領導者,尋找適合的軟體工程師一定是你份內工作裡不會缺少的一項任務.我這邊採用 "適合的軟體工程師" 而不是用 "優秀的軟體工程師",其主要原因在於每個團隊的任務與能力不同,所以無所謂的優不優秀,只要是適合的人,對你團隊來說都是優秀的.

人們常說 "物以類聚",這句話適用在許多人類的活動裡,對於建構一個軟體開發團隊而言,其實也是適用的.真正優秀的工程師對於技術含量低的工作通常不見得感興趣,相同地,能力不好的工程師也無法在技術含量高的團隊裡存活下來.這些原因可能來是一個現實的條件 - 薪資.

一般而言,薪資高的工作對於工程師的品質也會要求較高,相同地公司付出的薪水也會比較多.這是一個很簡單的經濟學原理 Supply-Demand 的觀念.一個健全的社會裡都是有這樣的現象.因此,身為團隊領導者的你首先必須思考一件事情,你需要什麼程度的軟體工程師.在你設定下了一個範圍之後,接下來的問題便是該如何衡量一個軟體工程師是否適合.

以下是我的做法,已經行之有年了,這些做法並不是我發明的,只能說是被 "同化" 後的結果.

1. 設定基本功夫的內容

既然是從事軟體開發的工作,你得先確保來面試的人具備基礎的資料結構與演算法的頭腦. 若是你資工相關科系畢業的,你應該能明確深刻的體驗到軟體工程師的工作就是將專案中的問題轉換成程式可以操作的模型,然後在電腦的架構下,不斷地在這些可操作的模型上做 "資料處理" 的動作,最後將結果產生出來.在這過程中,了解資料結構是一件非常重要的基礎.你可以從前面的文章裡了解到一個軟體工程師對資料結構的熟悉度將決定了程式的好壞 (Time complexity and Space complexity),最終將會影響到整個專案的品質.

如果你團隊的工作是一般簡單的資料處理網站,使用者在表單上輸入資料,然後在其他表單上輸出資料.類似這樣的工作,你至少得確認你的軟體工程師懂得 Array, List, Stack, Queue, Hash table 這些基本的資料結構以及相關的應用.如果你團隊是製造一個資料庫引擎,那麼 Tree/Graph 的操作與相關應用將會是你團隊裡所需要的最基本的功夫.

透過考試來了解面試者的情況是最快速的方法之一.但我通常不建議拿一般市面上的考題.我建議的方式是準備一個在你過去的專案經驗裡值得拿出來當考試的題目.這是一個真實世界的問題,所以題目內容是容易能面試者明白為什麼是這種考題,同時也能讓面試者體會到未來有機會進來工作時,面對的情況這類似是這樣.通常準備一個簡單的和一個難的題目.

2. 設定操作工具的熟練度內容

世界上有許多程式語言以及相關許多不同的產品與工具.如果你需要的是一個可以盡快上戰場協助團隊的軟體工程師,那麼你便需要確保來面試的人員具備相關工具的知識與熟練度.例如,團隊的工作裡需要大量用到 Visual Studio/Microsoft SQL server 來進行專案開發,則你必須確認面試的人們對這些工具是熟悉的.最簡單的方法就是上機考.透過上機考的過程,你便可以清楚知道面試者對一個工具操作的熟悉度是在什麼程度.

3. 設定其他所需知識的領域

若專案是用關聯式資料庫做為 repository 時,你必須確定面試者具備 ER Model 的知識以及相關的知識,如 Index 的設計等. 若專案是用物件導向的方法來開發時,你必須確定面試者明白什麼是 class, object, 以及其他物件導向的原則與應用.同樣地,透過考試是最能直接明白面試者的情況.我在這邊也是給相同的建議,那就是考試的內容最好是團隊過去所面臨過的情況,分別找出簡單與難的問題來做為面試題目.

4. 設定人格特質

每個團隊都有一種 "文化",這種文化的事情實在困難說清楚,而這種文化確會大大地影響整個團隊的產出和品質.身為團隊領導者的你必須了解到團隊的文化是什麼,然後將這些文化融入在團隊的運作過程中.比如,沒有經過 review 的 code 不能 check-in source control, 沒有加上 unit test 的 function 不能 check-in source control.類似這樣的事情讓面試者了解到團隊運作是有規則地運行.因此,態度散漫或不夠嚴謹的人自然無法能適應這種文化.

分享一個以前的經驗,我多年前參加一個公司內部的面試,面試的過程中,那位老闆不斷地提出許多問題來轟炸我的思緒,除了看我的反應以外,也看我能不能耐住性子來穩健地解決問題.他們團隊的工作是一個線上問題支援的網站服務,所以工程師們必須 on-call 並且有抗壓的能力.

一個適合的軟體工程師除了要寫出符合團隊期待的程式碼品質以外,還要執行團隊所規定用來幫助便於軟體管理的事情.要盡量讓一切的團隊活動都是在可受控的範圍內,這是團隊領導者非常需要的.

最後,找工作是緣份,找到適合的軟體工程師也是一種緣份.千萬別為了補滿工程師的人數而濫芋充數,因為最後倒霉的將是整個團隊,這是團隊領導者最需要注意的事情之一.


Share:

#84 程式設計的簡約格式 - 減少程式碼縮排


最近在 code review 的過程中,總是常常會看到一些令人驚喜的事情,其中一件事情和程式的寫法有關.有時候是邏輯可以在簡化,有時候是 coding style 上可以在簡化以便閱讀.首先來看 coding style 可以簡化的部份.在寫程式的過程中,有時會因為業務邏輯面的複雜而造成會寫出多個 nested if statements 的情況,如下面的例子



上面的程式碼其實沒錯,也算方便閱讀.也許是我個人的因素,遇到 nested if 的時候,我會儘量地朝向少點縮排的方式前進. 除此之外,第 7 行和第 13 行是回傳一樣的答案.在程式寫法上可以將他們結合在一起,因為那是一個 "業務邏輯",一般來說,我們希望同一件事情只要發生在一個地方.因此,可以將上述的程式碼改成如下:



一個 if 配合上多個檢查條件,我自己覺得這樣閱讀起來比上述的語法好些.

再來看另外一個例子.

原本的程式碼如下:



同樣的,這程式也沒錯.不過,閱讀起來有點 "階梯".因為當我們閱讀時,大腦會產生那種 "階梯",如果 if true part/false part 的內容物很多程式碼,我們還得仔細看縮排才知道下一行要跑到那繼續看.

其實,只要動一點腦筋想一下就可以把它寫的更簡單,如下



這樣的寫法是一樣的邏輯,而且是不是覺得更方便閱讀呢 ?

在寫程式的過程式,會常用到 if..else.. 是很正常的事情,然後這也代表你的業務邏輯將分成兩塊,而這兩塊的內容是獨立而不會互相干擾的,所以這兩塊的內容基本上不會重覆.若有重覆,那就是一般所謂的 duplicated code bad smell.另外,利用減少 "縮排" (indentation) 的技巧也能讓程式碼達到更方便閱讀的地步.
Share:

#83 最近搜尋清單資料結構

最近遇到一個特別的需求有關一種像 Queue 但又不是 Queue 的資料結構

需求如下:
1. 可以自訂清單數量大小
2. 內容一筆一筆的存放,但讀取時是後進先出
3. 如果存放時,該資料已存在,則讀取時它會先被讀取.

舉些實例來說明
以下為動作順序
Initialize as size of 5
Set 1
Set 2
Set 3
GetItems() ==> 資料是 3,2,1

Set 4
Set 5
GetItems() ==> 資料是 5,4,3,2,1

Set 6
Set 7
GetItems() ==> 資料是 7,6,5,4,3

Set 5
GetItems() ==> 資料是 5,7,6,4,3

Set 3
GetItems() ==> 資料是 3,5,7,6,4

簡單的說,這是一個 array 具有 circular queue 行為並且帶有 special priority item 的特別需要.
範例程式碼如下


Share:

#82 K個最近鄰居演算法 (k-nearest neighbor algorithm, KNN)

在大部份的科學領域裡都蠻注重分類 (Classification) 這件事.透過分類,它能幫助我們整理問題,也能整理答案,甚至在不同的問題集合裡找出通用的答案.在人工智慧的領域裡,有一門科目叫模式辨認 (pattern recognition),它應用在影像辨識,人臉辨識,語言辨識等的範圍,其中需要一個重要的技能就是將所要辦認的物件做分類,然後在該分類裡找出合適的對應結果.在這過程中,k-nearest neighbor (KNN) 是一種相對古老且直覺的方法.方法簡單而且能有高準確率,並且不需要所謂的 “訓練”.在人工智慧的領域裡,簡單而言,做的事情就是收集資料,然後依這些資料整理出一個數學模型,未來有新資料出現時,就可以丟入這數學模型加以運算,得出來的結果就是此模型的預測結果.KNN 這方法並不需要所謂的 “訓練” ,也就是說你並不需要從舊資料裡整理出一個數學模型.

KNN 利用資料本身所具備的一些 “自然” 特性來達成辨認的目的.在網路上能找到最常見用來說明 KNN 的範例就是房價. 房價的資料本身就是一個許多資訊的綜合結果,例如包含了環境好壞,面積大小,學區優劣,交通便利,文化觀點等等的因素所綜合起來的結果.想像一下,當你有一份房價資料,裡頭記錄了每一條街某一棟建築物的價格.當你用地圖的方式來呈現時,這在城市的地圖上你可以為已知道建築物標上價格標籤,然後還有許多的建築物尚未知道價格.即便你不懂房地產,當任意從城市的地圖上找到一棟建築物來猜測其價格時,你會怎麼做呢 ? 最簡單直覺的做法就是找附近類似條件的房價來做為參考價格.這也就是 KNN 所採用的概念.

在 KNN 的方法裡,K 是一個大於 0 的數字.以上述房價的例子來看,用來代表你要參考附近 (以距離來算) 多少個房價來做為預測新位置房價的對象.接下來,直接從 Wikipedia 上 KNN 例子的圖來做範例:



假設上圖是某個城市的房價分佈圖,用顏色來代表不同等級的房價.若採用 K=1 時的分類方法時,可以將地理區域劃出如下的區域:



這代表該區域內代表 KNN 方法在 K = 1 時所計算出來的房價.如果 K 值不同時,所得到的區域不會一樣.至於 K 值要取多少才能得到較好的預測結果,這需要更多對資料特性有實務經驗,才能找到適合的 K 值.因此,KNN 要用的好,除了找到一個適合算 “距離” 的公式外,還得對資料有許多實務經驗才行.

剛剛所談的算 “距離” 的公式,這是什麼呢 ? 以上述房價的例子而言,所謂的距離就是預測的房子與資料中最近房子的地理位置上的距離.你可以用直線距離或是真實道路距離來計算,完全依你的情境所需來決定.所以,不同的情況下,計算距離的方式是不一樣的.接下來舉個例子,車牌號碼的辨識已經在許多地方都派上用場了,例如高速公路收過路費,停車場進出入的車牌識別等.車牌識別用 KNN 的方法來進行,該怎麼做呢 ? 首先,我們的資料集合裡一定會有車牌會出現的所有符號,包含數字,英文字母或其他符號等.每一個符號都是一張圖案,而每一個符號在這圖案上所佔用的位置一定不一樣.如下圖是車牌數字的 7 :



當我們用一個 2D array 來代表 7 時,你可以把白色區域用 0 ,而黑色區域用 1,這樣一個 2D array 就可以表達出一個數字的 “長相” 了.會不會有其他的符號有一樣的長相呢 ? 在這個例子裡不會發生,因為每個符號都是不一樣,因此 2D array 裡的 0 ,1 也會不同.

接著,當一個欲辨識的符號進入時,我們怎麼算 “距離” 呢 ? 只要把欲辨識的符號用同樣的方式轉換成 2D array,然後再將這個 2D array 跟我們資料裡所有符號的 2D array 做一個 XOR 的運算 (或是檢查兩個值是否相等).如下面簡單的程式碼 :



只要兩個 2D array 的某個元素不一樣時, diff 就會增加.卻辨識的符號會和所有的符號都進行一次算 “距離” 的運算,最後就選出 diff 最小的,那個就是我們找出的答案.

上述的方法是一個 K = 1 的 KNN 應用,我忽略了許多實作細節,但希望透過這樣簡單的說明能讓沒聽過 KNN 的朋友們知道 KNN 如何應用在車牌辨識上.如前面所說,透過 KNN 方法,我們不需要像 SVM (Support Vector Machine) , CNN (Convolutional Neural Networks) 那樣搞複雜的訓練模型過程就可以得到準確率還蠻高的結果.這樣說並不是說 KNN 比 SVM 或 CNN 強大,只是剛好在簡單的辨識情境裡 (如上述前的車牌辨識) KNN 在 K = 1 時能提供準確率相當高的結果,而且也不用事先訓練模型,也許這能算上是一種數學的奇蹟吧!
Share:

#81 出神入化的用介面 第四集 修改共用的介面 part.2

這一篇文章是上一集的延伸,再來說明新版本 interface 的後續實際使用的情況.先將此篇文章要解決問題再描述一次.想像一家公司出版了一套軟體,而這個產品裡包含了許多的元件檔案 (.dll),而且每一個元件是由不同的團隊產生.每個元件可以有獨立的發行時間,也就是說當 A 團隊要釋出新功能的版本時,他們可以自行釋出.在客戶端裡,可以透過該軟體裡的更新程式來下載並且安裝 A 團隊所製做的新版本元件.由於各元件釋出的時間並非一致,因此元件之間的互動將變得有挑戰性.

A 團隊裡的某些功能是透過 B 團隊的元件所完成的.例如,A 團隊提供的功能裡有一項是計算產品折扣,而這項功能的細節實作者其實是 B 團隊,因此 B 團隊會提供 interface component 給 A 團隊使用,如:



因此,在 A 團隊的程式碼裡,將可能利用下述的程式碼得到實做該介面的物件,然後來進行折扣計算,如:



接著,A, B 團隊從產品經理接收到新需求,他們必須提供一個新的功能 - 回饋金 (cash back).因此,比較簡單的做法便是將上述的 interface 加以延伸.但如上一集文章所提,B 團隊不能直接改 IProductUtils,所以他們必須要製造一個新的 interface,並且繼承自 IProductUtils.



A 團隊接著將他們的程式碼修改如下:



若 A 團隊用上述的方式更改程式,則有可能發生錯誤.當某個用戶端使用新版的 A 團隊程式而且用了舊版的 B 團隊程式,則執行到上述程式碼時,就會發生 TypeLoadException 的錯誤,因為此時電腦裡是舊版的 B 團隊元件,所以 runtime 看不懂 IProductUtils2,對它而言,這是一個 unknown type.

為了防止上述的錯誤發生,A 團隊必須採用一些方法來辨別 runtime 所載入的是舊版或新版的元件.可能的方法如下:

  • 讓 B 團隊為不同版本的元件使用不同的檔案名稱.如 BContract.1.dll 和 BContract.1.1.dll 等.B 團隊發行新版本時,可將兩個新舊兩版的 contract dll 一起釋出,同時在實做的程式碼裡也會同時實做新舊兩版的 interfaces.所以,A 團隊若用舊版 (BContract.1.dll),則 A 團隊只會看到 IProductUtil,若用新版 (BContract.1.1.dll),可看到 IProductUtil 和 IProductUtil2.這樣做的好處是讓新舊兩版的 interface 位於不同的元件裡,當其他團隊取得舊版時,其他團隊只能看到 IProductUtil.使用新版時,則可看到兩個 interfaces.利用實體檔案區別同一個功能的新舊版本.壞處就是可能會造成過多的元件檔案.




  • 讓 B 團隊將新舊版本的 interfaces 寫在同一個元件檔案裡,如 BContact.dll.這樣做將讓 A 團隊無法從元件檔名上知道他們正使用的是新版還是舊版.因此,就必須透過程式碼來解決這問題.A 團隊為了處理新舊兩版的情況,當他們載入 B 團隊的元件時,他們可先嘗試使用 IProductUtil2,若 IProductUtil2 使用時發生 TypeLoadException,則表示 B 團隊的元件是舊版的.此時 A 團隊便可以把回饋金功能的相關 UI 畫面關閉.請參考下列程式碼來看 A 團隊如何使用正確的版本.



    透過上述的方式,當 runtime 執行到 line 12 準備進入 TryGetNewVersion() 時,如果此時 A 團隊使用的是舊版 B 團隊元件,則 runtime 便會發生 TypeLoadException 的錯誤,因為 line 28 的 IPorductUtils2 是一個 unknown type,並且此錯誤會在 line 18 被抓住.接著 A 團隊便可以關閉回饋金的相關功能.如果 A 團隊使用新版本,則不會發生 TypeLoadException.只要能順利取得正確的物件就能呼叫 GetCashBack() 來得到回饋金的金額.若用這個方法,則 A 團隊必須使用 B 團隊的新版本元件在他們的編輯環境裡,才不會發生 build fail (unknown type) 的情況.




  • 這一篇文章提到的情境應該不會是大多數人的情境,畢竟同一個軟體產品裡每一個元件可以有不同的釋出時程是很少見的.如果你的工作情況真的有符合這樣的情境,希望這篇文章能給你一種解法來解決這情境的問題.若你的解法不同,也歡迎你分享給我.

    Hope it helps,

    Share:

    #80 寫程式的參考準則 (coding guideline) - C# 篇

    曾有一些朋友問我,在微軟公司裡是否有寫程式的準則 (coding guideline).這件事因不同的團隊而異,大部份的團隊都會依循 MSDN 文件裡的建議,但並非每一個團隊都有文件記錄這些準則.以前我在 Windows 部門裡的某個團隊就正好有文件說明 C# coding guideline.除了 C# coding guideline 以外,還有其他的文件,例如 code review 文件, database 開發文件等等.在這篇文章中,我將從 C# coding guideline 開始寫起.這些 coding guideline 不是什麼秘密,很多都是來自 MSDN 的文件.若你的團隊也需要一份 C# coding guideline, 希望能派的上用場.

    1. 在一份 C# 原始碼裡,別有 Tab , space 並存.這一個可以善用 Visual Studio 的編輯器設定幫你解決.一般來說,我們用 space 來取代 tab,例如一個 tab 等於四個 spaces.

    2. 一行程式碼的字數通常設定在 120 個字元左右.為了方便閱讀,若有一個 api 有多個參數需要傳入,將多個參數分行排列,如下例


    3. 有關設定變數 (variable),盡可能地將其 scoping 範圍找小一點的.

    4. 變數宣告時不一定要馬上給初始值 (initialize).用到此變數時在給即可.若需要給一個初始值,請給一個有意義的值做為初始值.這邊所謂有意義的初始值不代表該資料結構的預設值.如 int count = 0; ,這是多此一舉的行為.

    5. Global field 前面加上 _ .若是 local variable,則不用.
    如 int _memberCount;  
         int memberCount;

    6. 相同型別的變數要分行宣告.別擠在一行一起宣告,應分行.如:
    int foo;
    int bar;
    int baz;

    7. 對於常數型的變數 (內容不會變動) 記得使用 const 宣告. 如:
    private const int _defaultCount = 100;

    另外,對於這類常數型變數,最好能加上一個 comment 用來說明為何選用此內容. 如:
    // 100 is chosen because of the size limit of the queue
    private const int _defaultCount = 100;

    8. 對於多個性質相關的常數型變數,可以考慮將他們整合在一個 static class 裡宣告並使用,如:

    可改成


    9. 用 string.Empty 來取代 ""

    10. 用 string.IsNullOrWhiteSpace() 來檢查字串是否為 null 或是空白.

    11. 對於一些 “應用值”,不應該 “hard-code”,而是該透過其他較彈性的方式取得 (像 Configuration).如
    網路連線重試次數,timeout 時間, thread 數量, 資料庫連線字串等等

    12. 在 if , while , for, foreach, return 前多個空行,以便於閱讀.

    13. Class 裡的 method 之間有一個空白行.

    14. 若有需要,善用 #region, #endregion 將相關的程式放在同一個區塊裡.同時 #region 之間也該有一個空白行.

    15. 善用 IDE 裡的編輯器幫助你處理好空白的事情.如


    16. 遇到一些特別情況時,善用 comment 以便未來工作.寫 comment 時不用一行一行寫 (inline),請在適當地方用一塊區域來說明程式的運作目的.


    17. 對於 public method 都該檢查輸入參數是否符合你的預期.如:


    18. 該有括號的地方都打上去,別偷懶不打.如:


    19. public method, property 等一律使用 PascalCasing ,而非 public 改用 camelCasing. 如:
    public int GetMyReward();
    public string MyName {get; set;}

    private int getMyReward();
    private string _myName;

    20. 為 variable, property, method, class, interface 取名是件重要的事情.取一個完整的名稱,別用簡稱.如 使用 GetConsoleWindow() 而不用 GetConWin()

    21. Namespace 命名以 PascalCasing 方式,名字應以名詞為主.如: System.Security

    22. Class 命名以 PascalCasing 方式,名字應以名詞為主,如 StreamReader, DataCollector 等

    23. Interface 命名以 PascalCasing 方式,通常在最前面加上 I ,名字應以名詞為主,如 IList, IReadOnlyCollection 等

    24. Variable 與 parameter 命名以 camelCasing 方式,名字應以名詞為主,如:
    public int ToInt32(string itemValue, int itemCount);

    25. Method 命名以 PascalCasing 方式,名字應以動詞為主,如:
    ToString(), Write(), ExecuteCommand();

    26. Property 命名以 PascalCasing 方式,名字應以名詞為主,如:
    public int Length { get; set; }

    27. Event 命名以 PascalCasing 方式,名字應以動詞為主,如:
    public event EventHandler ObjectChanged;

    28. Public field 命名以 PascalCasing 方式,而 private field 以 camelCasing 方式,名字應以名詞為主,如:
    public TimeSpan Timeout;
    private TimeSpan _firstTimeout;

    29. Enum 命名以 PascalCasing 方式,名字應以名詞為主,如:
    FileMode
    {
    Open,
    Create,
    Append,
    }

    30. Class 的名字通常和對應的 Interface 名字有關係,如:


    31. 大部份的情況下, Enum 最好要加上 None 元素用來代表該 enum 用不到的情況下,並且將它設定為 0.如:


    32. Enum 若是 Flags 的屬性,別在名字加上 Flag,可用複數名詞來代表. 如


    33. 為了便於閱讀和 code review,將關聯性高的 class 成員寫在相鄰的位置.

    34. 一個檔案最好只有一個 class,並且檔案名字與 class 名字一致.若是 nested class 或是一些簡單且臨時在程式間用的 class 除外.

    35. 所有的宣告都應加上 public, private, internal.若是只在一個 method 裡使用的臨時變數可以忽略.

    36. 在 switch 裡要加上 default: ,即使它的內容是空的,也要加上.

    37. 要產生準確的 exception.如,當你檢查參數是否為空時,就該用 ArgumentNullException 而不是用 ArgumentException.

    38. 產生 exception 時,要產生有意義且可知道錯誤細節與解決方法的 exception,不該把許多可能會發生錯誤的 code 放在一個 try block 裡,然後只有一個 catch (Exception ex).

    39. 當處理商業邏輯時,很可能找不到適合的 exception type,此時應自行建立自訂的 exception.

    40. Exception 產生時不應該影響程式的正常流程,並且 exception 產生時需被處理,例如 log.

    41. 在 try-catch 裡若使用到一些資源,可在 finally block 裡釋放.如:


    42. 在你的程式裡,在最上層 (可能是在 UI 層) 要能抓住所有可能會發生的 exception,做好相對應的處理或畫面顯示,避免程式中斷.

    43. 在 catch block 裡應該都為該 exception 做些處理動作,而不是空白 (什麼事都不做).除非,程式裡已有邏輯在處理那段錯誤,如:


    44. 不用重覆拋出 exception.應該加一些錯誤處理機制並且只需要 throw 即可.如:


    45. 對於有實做 IDisposable 的 class 應善用 using 來確保資源能適時適當地被釋放.如:


    別在 try-finally 裡使用 Dispose,如:


    46. 盡可能使用 generic collection 來儲存物件,例如使用 List<T> 而不用 ArrayList.

    47. 所有的 public class, property, method 都應該要有 XML 文件註解,如:


    48. 有適合的語法糖時就使用,以便於閱讀.如:


    49. 在不影響程式邏輯的情況下,應把程式碼編排縮排量減少.如:


    50. Public method 的參數應盡量使用 interface,如:


    51. 若無特別需求,為每個非同步呼叫加上 ConfigureAwait(false)

    52. 若無特別需求,不自行建立 Thead ,一律使用 Task 讓 .NET threadpool 來管理相關資源.

    53. 多個 Task 有執行順序時,善用 ContinueWith(), WhenAll(), 或 WhenAny(),而不該用 Task.Delay.

    Share:

    #79 貪心策略 - Greedy (2)

    上一篇文章談了貪心策略的基本想法,但並沒有提到任何的程式碼來說明貪心策略是怎麼進行的.其實貪心策略並沒有一個很明顯程式碼撰寫方式,如果硬是要湊出一個程式碼外型的話,我覺得它的長相可能如下:

    while ( 依問題條件來決定是否要繼續下一步 )
    {
        // 1. 依照問題,在這一個步驟裡取得最佳解
        // 2. 根據步驟一得到的最佳解來決定程式的下一個狀態
        // 3. 將程式目前的狀態移動到下一個狀態,下一個狀態將會更接近最終的答案
    }
    

    老鼠走迷宮是很典型資料結構 Stack 作業,它的內容是假設一個方形的土地,這土地用畫分成許多面積相等的小格子,就像棋盤那樣.每一個格子都是一種地形,如山,河,平地.老鼠只能走平地,不能爬山也不能過河.老鼠將從起點走到終點,起點是在這土地的左上角,而終點是在右下角.這個作業就是要讓老鼠能走出一條路從起點到終點.如果沒有路存在,則最後的答案是 null,若有路存在,則最後的答案是每個格子的座標集合.老鼠走迷宮用貪心策略來展現其演算法,它的程式結構如下:

    while ( 老鼠未到達終點 )
    {
        1. 在目前格子,依順時鐘順序找到一個可以走的格子,並且這個格子沒走過而且其地形不是山或河
        2. 如果所有可走的格子都已走過或都是山河等地形,則下一個格子是上一個步驟的格子.
        3. 將老鼠移動到下一個格子
    }
    

    在老鼠走迷宮的例子中,老鼠在每一個格選擇下一個格子時,此時便是要求一個 “當下” 的最佳解.走過的格子不能走,地形是山或河的格子也不能走,所以只剩下一般的平路.在 “當下” 的情況下,下一個格子是平路的情況可能超過一個方向,此時我們無法得知下一個格子之後的狀態,因此,可以依序或隨機選擇一個格子來走.畢竟都是平路的格子,所以在 “當下” 來說都是最佳解.

    誠如上一篇文章所說,這樣的解法通常不會是最佳解.在老鼠走迷宮的問題中,最佳解通常是指最短路徑.如果老鼠走的土地剛好只有一條路可以走的話,那麼用貪心策略寫出來的程式找到的路徑剛好就是最短路徑,因為只有一條而己.但現實中的問題裡,幾乎很難會遇到這種情況.

    另外,你也能感受到貪心策略只考慮 “當下” 而己,不會再多考慮下一步,所以你也能看到貪心的策略並不用利用其他的資料結構去記錄一些有關那一條才是最佳路徑的事情.也是因為如此,程式寫起來才比較簡單,因為你只需要用一個 Stack 來記錄走過的格子,而不需要為每一個格子去記錄所有可能的狀態.由此,你也能感受到求最短路徑就不是那麼簡單直覺的事情了.

    Hope it helps,
    Share:

    #78 貪心策略 - Greedy (1)

    前面的文章曾提過,在這世界上有很多不同類型的問題,基本上我們太不可能找到一個方法來解決所有的問題.所以,不同類型的問題就會有不同的解法.有的解法很好理解並且單純,有的解法不易理解.解法本身並沒有所謂的好壞,只有適不適合使用的情況.通常來說,難的問題若要有好的執行結果,通常那個解法不見得簡單,就算是簡單,也絕非容易可以想的出來.這也許就是演算法美妙的地方,或許可以說是邏輯之美.廣泛地也可以說成是數學之美,都是宇宙空間裡所擁有的一些特質.

    今天要提的解法是一種貪心 (Greedy) 的 “精神”.若你沒念過演算法這門課,恭喜你可以免除這個宇由特質的迫害,可以遠離那種整晚埋頭寫作業的崩潰時光.我想我是比較笨的,所以我以前寫演算法和計算理論的作業時,常常抱著頭在燒.如今,回頭看看,這些都是人生裡蠻有趣且值得回憶的時光.演算法課本裡,前面一半的內容中主要是提到一般市面上對問題的 “解法” 有那些.一個問題可以有多種不同的解法,就像你的工作上要達成某一個任務,可以用不同的技巧或手法來達成該任務.因此,解法可以說是一種邏輯思考的過程,也可以說是一種寫程式的過程.基本上,寫程式就是一種邏輯思考的具體呈現.因此,演算法的課程裡前面一半就是在教你如何 “邏輯思考” 來解決問題,其中最簡單的思考方式就是 "貪心" (Greedy).

    貪心的精神在於在解決問題的過程中選擇一個 "當下" 最好的決定來繼續往下執行程式.這是什麼意思呢 ? 舉一個相當簡單的例子.假設你對台北的街道並不熟悉,而你現在位於台灣大學的校園裡,你接到一個任務是要找出徒步走路到陽明山的路徑.想一想,你會如何思考來解決這個問題呢 ? 別忘了,前提是你對台北的街道並不熟悉,但是你知道陽明山在北邊,因為天氣好時你能看到陽明山.”貪心” 的精神就在於,位於所在位置,在此時那一條路是最好的選擇就走那一條路.由於不熟悉台北街道,你只好依照陽明山的方向前進,可能沿著敦化南北路一直往北走後,結果你發現松山機場卡在前面,不僅如此,機場旁邊還有一條基隆河.只好在機場前做出往右走或往左走的決定,來找到橋讓你渡過基隆河,然後再一直依著陽明山的方向前進.這種邏輯思考就是每走到一個路口,再來決定下一個方向要如何走.如果運氣不好,剛好走到沒有橋能跨越基隆河的路口,那只好再依當下的情況做出最好的決定.往左走或往右走不代表一定會有橋可以過,所以你也可以感受到這種 “貪心” 的解決方法似乎有點風險. 因為 "貪心" 提供的解答通常不會是最好的答案,所謂最好的答案像是最短路徑,最省時的路徑等.除此之外,你也能感受到依照 "貪心" 方法,要寫出這方法的程式還蠻直覺和容易的. 因此,不同方法都有不同的優缺點.要決定用什麼方法之前就必須對你的問題有完整的了解.

    再舉另外一個例子,在前面的文章裡曾提到 #48 老鼠走迷宮 .在這文章所提供的程式碼就是一種 "貪心" 的解法,因為從這一步走到下一步時,只單純考慮是否可以通行,不會考慮其他因素.因此,經由 "貪心" 得到的路徑是一條 "可以走" 的路,但不一定是 "最短" 或 "最省力" 的路.如果你找到的路剛好是最短或最省力,那只是說明你當下的運氣好,並不代表 "貪心" 解法能帶給你最佳值.

    你可以想一想,在你的工作中,是不是用了很多 "貪心" 的方式來寫程式呢 ? 我相信大部份朋友們的程式碼一定讓 "貪心" 佔據了大部份,因為 "貪心" 並不需要人類特別去想像才能發明出來的方法,它本身就是最單純的思考方式.如果有一個問題連 "貪心" 都無法解決時,那這問題應該真的可以稱上是超級難題了.

    完全沒寫到任何程式碼來解釋 "貪心",不知道這樣效果如何 ?

    Hope it helps,

    Share:

    #77 部落格的原始動機與人生所需的財務智商

    這篇文章來分享二個主題,第一是為何我開始寫這個部落格,第二是人生所需的財務智商.

    我在 "大毛電腦科學筆記" 裡從 2015 年 3 月開始寫下第一篇文章到現在已經有三年半的時間了.剛開始的第一年,由於我沒有設計任何的讀者回饋方式,因此第一年並不知道寫的內容是否有用.後來第二年開始加入 Google Form 讓讀者們可以留下回饋資訊,並且也為網站上加入 Google Analytics 用來查看網站的流量資訊.大約一年前成立了 Facebook 社團以及舉辦公益課程來做為另一種推廣此部落格的管道.從去年 (2017) 開始,我陸陸續續收到一些讀者們的回饋,有些是單純地謝謝我寫這些淺顯易懂的內容,也有些是來問我一些工作上的問題.謝謝大家的捧場和問題讓我知道這個部落格已經發揮了一些作用.其實,我最早的想法並不是寫部落格,而是打算把所有的資訊匯集成冊出版用.早在十年前,我收集了以前在台灣和美國念的上課筆記,打算將這些內容寫成書來出版.但可惜,後來因為搬家緣故,那一大本的筆記已下落不明,所以把筆記匯集成書的想法便中斷了.但我並沒有忘記要分享電腦科學的基礎知識這件事.後來心想,匯集成冊需要大量時間並且有出版時程的壓力,於是 2015 年初便改用部落格的方式進行分享.這樣一來,沒有時間壓力,可以一篇一篇慢慢寫.最主要的想法是要將電腦科學裡的基礎知識分享給在資訊界裡非本科系畢業的資訊人.與其說是分享,也可以說是一種對自己人生中某幾段求學和工作過程的記錄.誠如我在 "有關作者" 的頁面裡所寫的,我自己在大學時念的是機械工程,但因緣際會的人生巧合,我轉換跑道到電腦科學,在台灣待過一般的軟體專案公司,然後也在美國待過所謂的大型軟體公司進行軟體產品的開發工作.這一路走來,像我這樣在大學時學非所用然後因好運氣而進入到大公司參與軟體產品開發的人應該是相當少見,也因此更激勵我把許多知識和心得分享出來.一方面希望能幫助或鼓舞其他人,另一方面也為自己的 IT 人生留下一些深刻而明確的記錄.在這三年半的時間裡,記錄了文章大致上有資料結構,資料庫系統,些許的程式設計,以及正在撰寫的演算法.後續的內容還會有更多的程式設計,作業系統,分散式系統,甚至影像處理,人工智慧,以及其他大家有興趣的內容.我自己並未設限要寫到什麼情況下才算結束,就一切隨緣吧! 根據這一年來的網站流量資料,每個月大約有二百個連線拜訪這個部落格,若以網站經營的角度來看,這是一個流量超級低的網站.不過,這部落格不是以營利為出發的網站,除了 domain name 要花些錢註冊以外,其他都是免費資源,因此沒有營利需求.大部份拜訪到此部落格的使用者都是經由 Google search 而來的.這些網路上來的使用者都是經由關鍵字搜尋而找到此部落格,例如搜尋 Heap file, database B-tree 等等.因此,有緣來拜訪此部落格的朋友都會對這裡的文章感到興趣,也是這樣的情況,我才會從去年開始陸續收到網站拜訪者的留言與回饋.若你有任何建議,也別忘了留言告訴我.

    之前我曾在 IT人生 的系列文章中提到一個與銀行戶頭有關的文章.簡單地講就是 "錢".這也是一般年輕人比較容易忽略的事情,但這件事情卻又是如此地重要.對我自己而言,錢能提供的不是成就感,而是一種安全感.在你依照自己的目標追尋自己的成就感時,有點錢在身邊是一種安全的保障,能幫助你應付一些緊急的狀況.也許你可能會覺得找份工資高的工作不就好了,我也希望事情有這麼簡單就好了.以許多進步的國家來看,來自國家所設計的保障在未來都是有倒閉破產的風險,像是台灣的勞工保險 (非勞工退休金),在未來某一天也會因繳的人少且領的人多而面臨入不敷出的情況,既便是像美國的 Social Security 在未來的十幾二十年後也是會面臨同樣的問題,這樣的問題在許多國家都存在.因此,只想要依靠當初政府所設計的保險制度來領取退休金的人們要小心了,因為錢不一定領的到.我相信大部份的讀者都是二三十歲的人,離退休還有很長的一段路.因此,要讓自己保有良好的 "財務智商" 是相當重要的事情.不論你從事什麼樣的工作或是領多少薪水,財務計畫和規畫是每一個人都不該錯過的課題.自己的退休金最好還是要自己先準備好.所以,我才會特別強調這件事情讓還沒準備的讀者們要想一想這件事.如果你願意花假日的時間去上課學習一些新的軟體產品與開發技術,那何不也花一些時間讓自己學習有關 "錢" 的事情.你花時間學了一個新的產品或技術,頂多只能用個三四年,然後就有新的版本或新的技術需要學習,成本是很高的.若你學習有關 "錢" 的事情,那是一輩子受用的事情,不會有什麼每隔幾年得重新學習的情況.最近,我在 YouTube 上看到兩個年輕的台灣網紅 (柴鼠兄弟),他們錄製了許多的短片,每一個短片都用淺顯易懂的方式來說明與投資理財有關的內容,這就像我喜歡用淺顯易懂的方式來描述許多電腦科學裡的知識一樣,因此我非常喜歡他們的影片.我強烈建議對 "錢" 還沒什麼概念的讀者們可以看看他們的影片來增加自己的財務智商,為你未來的生活增加財務上的安全感.

    Hope it helps,

    Share:

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

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

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



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



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

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



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

    Hope it helps,


    Share:

    #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,


    Share:

    #74 演算法從零開始

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


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


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


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


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

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


    Share:

    #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(n2),空間複雜度是 O(n).也許有更快速的解法等待你的尋找.

    Help it helps,
    Share:

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

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

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

    一個能處理一秒三十八萬筆交易的系統是一個龐大的系統,每個部份都有許多故事可以講,接下來的內容只討論一些與資料庫引擎有關的內容.在網路上我曾看過一篇文章談到阿里巴巴的資料庫交易系統裡為效能改進所做的一些事情,其中最讓我印象深刻的事情是預先建立訂單資料.以資料庫引擎的角度來看,預先建立訂單資料等於把所需要的 page 先建立完成,因此在系統運行的過程中,不會有 page split 的事情產生.請參考之前的文章
    以上這幾篇文章與 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 這能讓資料庫引擎少做許多事情.這方面的內容請參考之前的文章
    當整個系統過了尖峰時刻後,再將結果的資料回復到 normalization 的情況下即可.

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

    Hope it helps,


    Share: