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