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

#92 今年一月份 APCS 程式設計第三題 - 切割費用

前陣子,我的小徒弟去報名他人生第一次的 APCS 考試,可以說是他學習電腦科學以來第一次的正式上機考試.一共有四題的程式設計題目,前面兩題算是簡單的,第三題算中等,第四題比第三題再進階一點點.這篇文章就來談談第三題的解題思考.

完整的題目在 https://zerojudge.tw/ShowProblem?problemid=f607 ,首先,要解題之前,請先確定自已己經百分百了解題目.這一個題目的解決過程可以分成下列 2 個部份,

1. 讀取輸入參數,因為輸入參數並非按照切割次序而輸入的,我們要進行切割時是按照次序來切割的.因此,我們必須對輸入參數做處理,以讓沒有次序的參數集合變成有次序的參數集合.

2. 每一次切割時,都需要知道左右兩端的長度,這樣才能算出該次切割的費用,而知道左右兩端的長度,這需要一個快速的行為才能符合題目的要求.因為題目提到切割次數最多會到二十萬次,並且棍子的長度可以到 10 7 那麼長.

有關讀取輸入參數的內容,基本上有兩種做法,可以把切割資料全部讀進來之後,再以切割次序做排序.若是這樣做,這個動作將花費 O (n lg n)  ,假設是用 quick sort. 除此以外,我們可以換個角度思考,題目給的切割次序不會出錯,也就是說當切割資料讀進來時,切割次序就是一種 key,不會重覆,因為第 n 次切割只會發生一次.所以可以用 (key, value) 的 hash table 來存放切割資料.由於 hash table 的 set , get 都是 O(1) ,所以這讀取動作將花費 O(n).

因此,第一個部份的時間複雜度最小可以到 O(n).

接下來,第二部份是計算每一次切割的費用.可以想像正在發生第 k 次的切割,也就是我們要想一個快速的方法讓我們可以查到在第 k 次切割時,當時所在的位置往左邊和往右邊走碰到的第一個切割點. 假設一開始用一個 boolean array 來代表被切割的點,

index :  0    1    2    3    4    5  ......98   99  100    101    102    103  ........ n

value:   f     f     f     f    f     t  .....  t     f       f        f        t         f      .......  f

一開始 array 的都是 false ,被切割過的點就變成 true,假設第 k 次的點要切割在第 100 個位置,而 98 和 102 是 true,所以這一次的切割費用是 102 - 98 = 4.如果以程式的角度來看的話,你得寫一個 for loop 從 100 往右邊走,找到第一個 true ,然後再往左邊走找到第一個 true,然後再做減法.這樣的尋找方式是 O(n),而這個會發生在切割資料的迴圈裡,假設切割資料是 m 筆,因此這一段的時間複雜度是 O(nm),一旦 n 和 m 都很大時,這就相當於是 O(n*n).而 n 最大的值會到 20 萬,因此 O(n*n) 是不能接受的.因此,用 array 做搜尋是不合格的,所以我們必須用其他的資料結構,並且這個資料結構所花費的成本要小於 O(n) (比 array 一個一個找再快).

這時候,答案其實已很明顯了,能夠比 array O(n) 還要快的只有 binary search tree O(lg n) 或是 hash table O(1) .在這一個動作的過程中,我們需要能 "往左走" 和 "往右走" ,Hash table  顯然不會是個好選擇,因為 hash table 無法儲存元素之間的 "順序",因此,就剩下 binary search tree 了.binary search tree 在儲存的過程花費 O(lg n) 時間,而尋找的過程也是花費 O(lg n) 時間,而且 binary search tree 的特性讓我們可以 "往左走" "往右走" 來找到最近被切割過的位置.因此,採用 binary search tree 之後,時間複雜度可變成 O (m lg n) ,如果 m 和 n 都很大時,就是 O( n lg n),這個比剛剛的 O(n*n) 快上很多.

最後,以下的程式碼是我的小學徒提供的,在很大的測試資料下仍花費了 0.25 秒完成,雖然不是最快,但也符合了題目 2 秒內的要求.

Share:

#91 如何寫有影響力的履歷表

根據 Facebook 社團上的成員資料,目前三百多位成員裡有將近 40% 成員的年紀在 34 歲以下,因此,希望這篇文章可以提供年輕人有關撰寫履歷表內容時的參考.

一般來說,我會把履歷表的寫法分成兩種,一種是屬於年輕工程師的寫法,另一種是資深工程師的寫法,我將年資不到十年的人定義為年輕工程師,所以可能是在 32 - 36 歲之間,就看你在幾歲從學校畢業.在這年資以下的人,撰寫履歷表時應該要著重在技能的部份.也就是說,你得在履歷表上說明你用過了那些工具與方法來製造軟體系統,以及你運用了那些專業知識 (課本上學的) 在你的工作上.比如,某個年輕工程師從事電商系統前端功能的開發,屣歷表上就需要清楚說明用 Javascript/TypeScript 寫了什麼東西,是否用到其他的 framework,如 Angular 等等,並且做過那些功能,如購物車系統,付款流程,購物體驗等等.把這些東西寫清楚來,讓看履歷表的人明確知道你過去曾用過的工具以及熟悉的產業環境是什麼,這樣能幫助雇主加快認識你的速度.

為什麼年輕工程師要寫這樣的內容呢 ? 因為年輕工程師通常被給予的任務是小而明確的,如解 bug 或做一些小功能.履歷表上寫一些技能類的事情可以幫助未來的雇主知道你過去做過些什麼,也能幫助雇主評估是否要找你來進行面試.

如果 32 - 36 歲以上的工程師 (超過十年的業界經驗),理論上來說,在業界工作了十年應該要達到資深工程師的水準了.我猜想在台灣的公司對於職稱上的給定標準並沒有一致且較寬鬆,所以中小企業或是非資訊科技領域的公司做了三五年後就能得到資深工程師的職稱.在規模大且制度嚴謹的公司裡,要在三到五年內拼到資深工程師是件不容易的事情,資深工程師的履歷表就應該著重於有關 "影嚮力" 的事情,比如,製造一個付款交易系統,讓整個網站可以在一分鐘之內完成 n 筆交易,使得網站可以承受 m 個使用者的流量.再舉另一個例子,重新製造了購物車系統,讓原本客戶評價極差的用戶體驗變成零負評的新體驗,並且讓網站提升 n % 客戶滿意度.再舉另一個例子,製造了一套基礎建設程式庫用於處理公司內所有系統的溝通機制,將原本平均一分鐘執行時間的動作提升至十秒鐘完成.或是一個更利害的例子,製做了一個很利害的 open source software,放在 Github 上得到了 n 顆星星,造福了世界上許多的軟體工程師.透過這些簡單例子,我相信你一定明白我所謂的 "影響力" 是什麼意思了.

回過頭來,並不是說年輕工程師就不用寫影響力.對於年輕工程師而言,如果你可以寫出令人信服的影響力,一定要寫下來,因為那些都是能讓你換到新公司時談職位與薪水的利器.

不論你寫的是技能比較多或是影響力比較多,千萬要記得別亂寫或是誇大地寫.若有機會面試時,這些技能和影響力是很容易被檢查出來的,一旦面試官發現你在 "唬爛" 時,你有可能永遠不會出現在這公司的面試名單裡.

履歷表內容的基本上包含了你的個人基本資料,工作經歷,學歷,技能以及一些參考資料.以我的經驗來說,我會將影響力放在工作經歷的內容裡,所以每一個工作都會是一段描述,而不是一行文字只包含公司名稱,職位名稱和時間而己.通常來說,一到兩頁的履歷表就應該要把你自己說明清楚,過長的內容,雇主很容易跳過不看,因為有名的公司每天都會收到很多履歷資料,沒有人會把細節看完.同時也要告訴一些年輕的工程師,工作要慎選,常常換工作並不是一件好事情,技能的程度高低也許不會受到換工作的影響,但我相信影響力是需要時間累積的,若常常換工作,則很難說明與說服其他人你在短時間裡能在一家公司做出有影響力的事情! 所以,找新公司時要好好想清楚,工作經歷就像是學歷一樣無法抹去也無法作假的,因此,在換公司時也要好好想想你該如何在新公司做出影響力的事情.同時這個題目也可能當成你和你老闆一對一面談時間裡的內容.

Hope it helps,

Share:

#90 淺談 Dynamic Programming (2)

 前面說過 dynamic programming 的應用很多,這一篇文章來說明其中一種應用,Maximun subarray sum.這個問題是在一個整數的 array 裡找一個連續空間的元素,其元素的總和的值是最大的.如下圖:


source: https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

從 index 2 到 index 6 之間的元素總和等於 7,這個區間是這個 array 裡最大的區間總和. 要解決這個問題其實不難,因為用最直接的暴力法就可以解決了,其程式結構如下:

這一個暴力法的時間複雜度是 O(n*n*n) ,n 是 array 的長度. 如果 n 很小,影嚮不大,但若 n 很大,這一個運算雖然在空間複雜度很表現的很好,但浪費許多 CPU 的運算資源,因為許多加法的計算是重覆了. 將這個問題的時間複雜度降低的方法不只一種,在這篇文章裡,我們用 dynamic programming 的策略來試著降低時間複雜度.如前一篇文章提過的內容,dynamic programming 的策略在於用空間換取時間,所以我們必須找出在什麼地方可以減少重覆的計算.要減少重覆計算之前,我們可以先從暴力法來看到底真正的計算是花在什麼地方了. 從上述的程式碼,你可以看到決定 subarray 的總和值是從最裡面的迴圈來運算的,所以第一圈會計算 start = 0 , end = 0 的總和值,第二圈會計算 start = 0, end = 1 的總和值, 第三圈會計算 start = 0, end = 2 的總和值,以此類推下去.透過觀察,你便能發現第二圈要計算的內容在第一圈已經算過了部份答案,第三圈要計算的內容在第二圈已經算過了部份的答案,因此,最裡面的迴圈其實是重覆了做了許多相加.

Loop 1: -2 

Loop 2: -2 + -3 = -5  (Loop 1 + -3)

Loop 3: -2 + -3 + 4 = -1 (Loop 2 + 4)

Loop 4: -2 + -3 + 4 + -1 = -2 (Loop 3 -1)

因此,透過以上的運算呈現,便能知道最後一個迴圈是可以去除的.我們只要將上一圈計算後的內容先暫存起來,留到下一圈時便能拿出來用,直接做一次加法就可以得到這一圈的答案了.因此,那個查表法的 "表" 也只不是一個臨時的變數,在空間複雜度上並沒有增加,而時間複雜度卻降了一階變成了 O(n*n),如下列的程式碼.

接著,或許你還會問,空間複雜度還仍再降嗎 ? 剛好這一個題目是可以的,它的名字是 Kadane's algorithm,這個演算法在許多讀者還沒出生之前就已經發明了,這演算法能用 O(n) 的時間複雜度解決這問題,而發明人是一位教授,現在已經非常高齡了. 若你晚些才看到這篇文章, Kadane 教授也許不在人世了,我們大家都是站在巨人的肩膀上.

最後,你可能會問這個演算法我們該用在那裡.這完全取決於你是否會遇到類似的題目.如果你遇到一個問題,而這問題剛好可以 Reduce 成 maximum subarray sum 時,Kadane's algorithm 便能幫助你寫一個超快速的程式來解決問題,例如,你老闆要你找出過去十年裡,那幾個連續的月份其營業額是最好的.

Dynamic programming 的策略確實應用在許多地方,未來介紹更多的主題時,一定都還會碰到 dynamic programming 策略所產生的解法.

Share:

#89 淺談 Dynamic Programing (1)

Dynamic programming 是大學部演算法課程裡相當重要的一個主題,也是典型用空間換取時間的策略.但奇怪的是,這個策略一點也不 dynamic ,一點也不 programming.老實說,我不知道為何這個策略叫 dynamic prograaming,我倒覺得它比較適合叫 "查表法". 接著就來看看為何說它是查表法.

Fibonacci number 是許多演算法課本用來解釋 dynamic programming 最簡單的例子.Fibonacci number 是以數學多項式來表達的數字集合,以數學式來表達就可以寫成如下:

F(n) = F(n-1) + F(n-2) 

也就是說求第 10 項 (n=10) 的答案時,你必須要先算出來第 9 項和第 8 項. 如果要求第 1 項呢 ? 難道要找出第 0 項和第 -1 項嗎 ? 在 Fibonacci number 上,我們會為這個 number 定義起始點,也就是說第 1 項和第 2 項的值是早被確定的,往後的項次皆由這兩項為基礎而算出來,所以不會有第 -1 項的情況. 假設, F(0) = 0, F(1) = 1 ,那麼數列的答案如下:

F(2) = F(1) + F(0) = 1 + 0 = 1

F(3) = F(2) + F(1) = 1 + 1 = 2

F(4) = F(3) + F(2) = 2 + 1 = 3 

F(5) = F(4) + F(3) = 3 + 2 = 5 

F(6) = F(5) + F(4) = 5 + 3 = 8  以此類推

當你要算第 n 項時,就按以上的方法一直算到第 n 項就能得到答案. 接著,數學公式 F(n) = F(n-1) + F(n-2) 寫出來了,那麼寫程式碼就變得相當簡單.

透過一個 recursive function 就能快速完成  Fibonacci number 第 n 項的計算程式.這一個程式碼沒有使用額外的記憶體空間,所以 space complexity 是 O(1),但仔細看一下 time complexity,卻發現超乎想像的大,因為有許多重覆的步驟:

            F(5)  
          /     \
       F(4)      F(3)
      /    \    /    \
   F(3)   F(2) F(2)  F(1)
   /  \
 F(2) F(1)

上圖是整個 recursive 的關係. 意思就是,當程式在 F(5) 那一個層次要往下呼叫時,程式會呼叫自己兩次,並傳送 4 和 3 為輸入參數,當第一個 recursive call 再進去時,又會再呼叫自己,並傳入 3 和 2 為輸入參數,以此類推.所以你可以看的出來,有許多重覆的計算在這 recursive 的過程中一直發生.以上圖來說,F(3) 發生了 2 次,F(2) 發生了 3 次.當 n 是一個大的數字時,你就可以發現比 n 越小的數字,重覆計算的次數越多,並且是以指數趨勢來增加.上述的程式碼雖然很簡單,但是 time complexity 卻是很可怕的.上述的程式碼是由上而下計算下來的,假設我們繼續用由上而下的計算方式,改良此程式碼的方法就是將 "重覆" 的計算步驟讓它不要重覆計算.如上圖,如果 F(3) 只真正地被計算了一次,而 F(2) 只真正地被計算了一次,那麼就不會有重覆計算的事情了.為了達成這目標,最簡單的方法便是把計算後的結果儲存下來,等到要計算一樣的內容時,去 "查表" 即可.也就是說第一次 F(3) 計算的結果儲存下來,當程式遇到第二次的 F(3) 時,直接去查詢,若有答案,直接將答案拿來使用,這樣就不用計算了.同時,為了確保不會造成過多的 time complexity,我們也需要確認答案的儲存和查詢所花費的 time complexity 要非常小,如 O(1).這種 "查表" 的精神也是 dynamic programming 所代表的策略.

若將上述的程式碼加入 "查表" 的功能,它將看起來如下:

或是直接改成由下往上計算

以上兩個程式碼雖然結構有點不太一樣,但都是用了一個 array 來記錄每一個項次計算的答案,因此 time complexity 省下來了,而且 space complexity 也增加了,但這樣的空間增加似乎是值得的.當然也可以再把上述的程式碼繼續改下去讓 space complexity 變的更小,不過這並不是這篇文章的重點.透過以上的簡單例子讓大家方便了解 dynamic programming 的 "查表" 意義是什麼.許多世界上有名的演算法都是基於 dynamic programming 的精神所發展出來的,例如你幾乎每天都在用的字串比對演算法就是基於 dynamic programming 所發明出來.

這篇文章用 Fibonacci number 的例子來說明 dynamic programming 的精神,這是相當簡單的例子,下篇文章我們用較難的例子來說明 dynamic programming 的用法.


Share:

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

    #78 貪心策略 - Greedy (1)

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

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

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

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

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

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

    Hope it helps,

    Share: