#93 平衡樹系列 - AVL Tree

在前面的資料庫文章裡曾介紹過 B-tree,一種平衡的搜尋樹,利用樹狀的結構來達成快速尋找的目的,而且因為是平衡的,所以從 root 出發到每一個樹葉的尋找成本是一樣的,這也是必要的,畢竟資料庫引擎用公平的方式來對待所有的資料.然而,B-tree 的結構並非是 binary 的型式,因此這帶給它很大的彈性可以方便地達成一個完全平衡的狀態.在前幾篇的文章也談過了 binary search tree,若你看過的話,你會清楚地知道 binary search tree 和 binary tree 的不同.在 binary search tree 裡,因為在建立樹的過程中有一個很重要的特性,就是右邊子節點的值大於父節點,左邊子節點的值小於父節點,因此在建立樹或是尋找節點時,到達一個節點時,只需要選擇其中一邊,不是左邊就是右邊,所以也達到 "binary search" 的效果.如前面的文章所說,binary search tree 的特性並不保證樹結構本身是平衡的,所謂的平衡就是其結構會和 complete binary tree 很接近.因為 binary search tree 沒有這樣的特性,因此樹的結構很可能是 "歪" 的.

為了要防止這種 "歪" 的情況,在早期的電腦科學研究裡便出現了許多的點子和做法,其中一個稱為 AVL Tree.這是兩位前蘇聯時代的科學家所發明的方法.發明的時間都是在我們出生之前 (我猜想這部落格的讀者群應該沒人超過 60 歲).首先,先把 AVL tree 的時間複雜度列出來.

Search: O(log n), Insert: O(log n), Delete: O(log n),不論是 average case 或是 worst case 都是一樣的時間複雜度,超級完美的.這也是為什麼在上一篇章的 APCS 考題會拿像 binary search tree 的實做來用,因為就是這麼快.不論是刪除或插入,甚至尋找都是 O(log n),為什麼可以這麼快呢? 接下來將來說重點了.

AVL Tree 是一種 binary search tree 的特例,所謂的特例是指 binary search tree 再加上一些其他的特性之後就能變成 AVL tree.而這一個特性稱為 balance factor.每一個節點上都會有一個 balance factor,它代表的是一個值,其值是右邊子樹的高度減掉左邊子樹的高度.例如:

source: Wikipedia

節點 F ,右邊高度為 1,左邊高度為 2,所以 F 節點的 balance factor 為 1 -2 = -1,其他的節點也是用同樣的公式而得.AVL tree 定義了每個節點的 balance factor 必須為 -1 , 0 或 1.透過 balance factor 的限制,我們能知道這一個樹就 "比較" 不會那麼歪掉了,因為右邊子樹和左邊子樹的高度最多只能相差 1 而己.為了確保這個特性能發生,在插入節點或刪除節點的過程裡便需要採取一些動作.而這些動作如下:

1. 往左轉

source: www.tutorialspoint.com

如上圖,節點 A 的 balance factor 是 2,因此必須降低它,由於這是 binary search tree,所以 C 的值大於 B,而 B 的值又大於 A,因此,要把樹技折下來的話,拿中間者來當新的父節點最好,於是以 B 為中心將 A 往左轉,所以就變成了最右邊的圖,這樣就符合了 AVL tree 的特性.

2. 往右轉

source: www.tutorialspoint.com

往右轉的情況剛好是和第一種相似,只是換另一邊而己.

3. 往左再右
source: www.tutorialspoint.com
第三種情況其實是前面兩種情況的綜合體.若你看懂前面兩個為何要那樣轉的話,我相信你也一定看的懂第三種.其主要目的就是要讓 AVL tree 的特性可以滿足.
最後第四種,可想而知就是往右再往左.

4. 往右再往左

source: www.tutorialspoint.com
第四種情況就是第三種的另外一邊.只要你懂第三種情況,那麼第四種情況自然也不會是問題.

你可能會問我,像這種 AVL tree 要應用在什麼地方.老實說,到處都是,許多程式語言在他們的 standard libary/SDK 裡都會提供這種平衡的 binary search tree.我在工作上時常會用到這類型的資料結構以快速建立資料和尋找資料.前一篇 APCS 的解題就是靠類似 AVL tree 這種的平衡樹才能將時間複雜度降到 O(n log n).別以為 O(n2) 和 O(n log n) 相差不多,一旦輸入的數量到達數以萬計時,你的家用 CPU 就會告訴你他們之間有很大的差距了.

在 Wikipedia 上你也可以找到一個動態的圖來說明 AVL tree 在建立的過程中,這些節點是如何左轉或右轉來達成平衡.AVL tree 將達成平衡這件事分攤在節點插入和刪除的過程中,因為才使得插入節點,刪除節點和尋找節點都有相同的時間複雜度.這的確是很高明的做法,我們大家又再一次站在巨人的肩膀上來看見電腦科學的神奇之處.

Share:

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