#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. Local variable 前面加上 _ .若是 global 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 演算法裡的貪心方法 part 2

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

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

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

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

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

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

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

    Hope it helps,
    Share:

    #78 演算法裡的貪心方法

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

    今天要提的解法是一種貪心 (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: