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

#88 資訊工程系的大學先修考試 APCS

在美國加拿大的大學入學測試中心成立了一種測驗,名為 Advanced Placement,裡面分成多個不同的專業考試,主要用來測驗高中生在該專業領域的 "程度" 如何.這些專業領域如生物,歷史,物理,語言,統計等等,其中電腦科學也是其中一個專業領域.簡單地說,就是要測驗那些資優班的高中學生,當他們申請大學時,可以附上 Advanced Placement 的成績用來代表他們有多少的能力在這些專業領域裡.詳情可參考 https://en.wikipedia.org/wiki/Advanced_Placement

在數年前,台灣教育部也發動了一樣的計畫,其中電腦科學的專業是由台師大資工系來執行,詳情可參考 https://apcs.csie.ntnu.edu.tw/

到今年 2020 為止,大部份在台灣有比較好的資工系學校都會參考這個成績,並且設下了門檻,例如台大資工要求觀念題和實作題都要達到 4 級分以上.這個考試結果一共分為五級,依照學生答案的內容來分級.若要達成 4 級分的話,基本上要熟練一個程式語言,如 C++,並且會用基本的資料結構,如 Array, List 等,除此之外,還要知道如何寫 recursive code 來解決問題,例如 binary search 等.對於正在讀文章的你,可能已經工作多年,這些並不是什麼難事,但對一個高中生,除了要面對高中的課程,還要花時間學習這些 "課外讀物",這的確不是件容易的事. 在師大的 APCS 網站裡,提供了歷史考題.我會在這網站裡貼出參考答案. 如果你是打算以後念資工系的高中生,或是你們家有這樣的高中生,歡迎你分享給他們.

程式實作題: 三角形辦別

日期: 2016/10/29


參考答案

程式實作題: 矩陣轉換

日期: 2016/3/5

參考答案

以上的答案是 C++ 搭配 STL,答案並不是我寫的,是我一位小徒弟寫的答案,他在二個月前剛升上高一,以他目前的能力要應付台灣 APCS 題目算輕鬆.我這位小徒弟是個小學霸,以後再來介紹我是如何訓練他電腦科學的知識.

以上兩題對於已經在工作的你來說應該都是很簡單的題目,只是一些基本的數學應用題.台灣 APCS 的歷史題目還有好多題,未來文章會介紹.


Share:

#87 Binary Search Tree 簡介

在 "資料結構" 系列文章裡寫過了 Binary search ,也寫過了 Tree.Binary search 能幫助我們在一個 "排序" 好的資料序列做快速的資料尋找.Tree 提供我們一個資料儲存 (放置) 的結構,當這兩個碰在一起時,產生了一個相當有用的資料結構.

Binary Search Tree 的發明比起我和絕大部份的讀者的都還要來的老,它出現在 1960 年代,在那個電腦硬體仍不太發達的年代,這個超級有用的資料結構就被發明出來了.誠如之前談的 binary search 內容,當你要進行 binary search 時,有一個很重要的前提就是被尋找的資料需要以某種排序好的順序存在,不論是從小排到大,從大排到小,或是從中排到小,再排中排到大,只要是資料依照某種屬性而排序好,就可以進行 binary search. 它的尋找資料的時間複雜度也在前面文章提過了,是 O (log N) 的複雜度,因為每一次尋找都可以捨棄掉一半非尋找目標的資料,這對尋找是個很大的幫助.然後,別忘了剛剛說的前題,資料必需是以某種方式排序好的.若你要在一堆沒有排序好的資料,把它排序,再執行 binary search 來找資料的話,這顯然有點過頭了,因為光是較快的排序都要花費 O(nlogn) 時間.因此在使用 binary search 之前,資料已是排序好的方式存在則能馬上使用 binary search,

當要讓資料以某種排序的方式建立起來時,可想而知,在建立的過程中可能要花費較多的時間,畢竟這不是隨便把資料加上去就好,而是要找到一個適當的位置才能加上去,以維持排序的狀態.你可以想像一個 integer single link list ,當你要加資料進去時,你得找到適當的位置並執行 insert 的動作,如下圖所示:

因此,只要我們能找一個適合的資料結構將資料依排序的目標建立起來,binary search 就可以派上用場. 在 Tree 的應用裡面,有個基本的結構叫 binary tree,也就是每個樹節點除了資料本身的空間外,還有另外兩個空間,一個是指向左邊節點的空間,另一個是指向右邊節點的空間. Binary tree 本身並不涉及任何資料排序的概念,但若我們為它加上一個限制,資料大的往右邊節點方向去建立,而資料小的往左邊節點方向建立,那麼這個 binary tree 便存在了排序的特性,如下圖所示,在任一個樹節點上,若左邊存在一個節點,則左邊節點的值將比較小,同理,右邊節點的值將比較大.

當 binary tree 加上了 "順序" 的特性時,這時就稱它為 binary search tree. 當尋找資料的動作發生時,從 root 開始出發,假設我們在上圖的 binary tree 上找 44,我們會在 root node 往右邊走,因為 44 > 11.以此類推,只要經過兩個樹楖點,我們便能找到 44. 如前面所說,這個動作的時間複雜度是 O(logn). 在大部份的應用裡,這個速度已經夠快了.

此時,你可能會發現在 binary search tree 要找資料時, root 的值是很重要的,因為你可能會看到如下圖的情況,

如上圖,倘若我們選到了一個不適合的值來當 root 時,此時 binary search tree 就長 "歪" 了.所謂的歪並不是壞掉的意思,而是大量傾向某一邊造成不平衡的情況.所謂的不平衡的意思就是某一樹節點左邊的 subtree 和右邊的 subtree 在高度上有大的落差.這會造成搜尋成本的不平均.比如,若你要找 44,它剛好是 root,所以一下子就找到了,若你要找 7,中間要經過 44 -> 33 -> 11 -> 6 ,最後到 7,若是你要找 11,中間經過 44 -> 33 就到 11. 所以,每個節點被找到的成本存在的大差異,因為我們稱之為不平衡的樹.這是我們希望能避免的情況,畢竟你希望的是每一個資料在被尋找時,每個資料被找到的時間成本和平均成本是很接近的,這樣才是公平.倘若資料本身需要不公平的情況,那就另當別論了.

Binary search tree 幫助我們將資料能用某一種順序的方式儲存起來,並且在尋找時也能達成 binary search 的效果.有些程式語言的程式庫裡都會提到這一個好用的資料結構,例如 C++ 的 map 就是典型的 binary search tree 實作. 如果你常用的程式語言裡沒有提供 binary search tree 的實作,我強烈建議你應該要在網路上找找是否有其他人做好成熟度夠高的實作,因為 binary search tree 的應用實在很多而且很好用. 當然 binary search tree 並無法為你自動達成 "平衡",所以才會有其他的資料結構產生用來解決這個平衡的事情,如 AVL tree, red back tree, B tree 等等. AVL tree, red black tree, B tree 也算是蠻有用的資料結構,不光是學術價值,其工業應用價值也是頗高,以後會寫文章來介紹它們.

Share:

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