#97 Segment Tree

在 binary tree 的文章時曾提到從 tree 開始後的資料結構文章將會開啟另一個大門，看來許多問題可以透過 tree 結構來解決．今天要介紹的 segment tree 就是一個例子．

試想一個情況，在現實生活中一定常常會遇到一個工作，一堆資料裡面，在某一個特定範圍依照某一個資料特徵來尋找資料．例如，在公司組織結構裡，找出 A 老闆底下的員工數總和．假設你已經有了員工組織樹狀結構，第一件要做的事情便是尋找 A 老闆節點，找到 A 老闆節點後，再從這裡出發將所有子節點計算個數，便能得到答案．一旦這樣的查詢工作常常發生的話，你會發現前面說的動作並不能馬上回應答案，因為還是要對員工組織樹狀結構進行 traversal 的動作．公司員工組織樹狀結構有一個特別的特性，員工的流動率正常來說都是小的．一家正常的公司不可能每天有很大比例的人員異動．公司員工組織樹狀結構不需要常常更新，並且需要更新時，也都是小比例的更新．當問題有這樣的特性時，segment tree 便是一個很好的資料結構用來解決這問題。

首先，為了簡單起見，讓我把上面描述的問題簡化，將人名變成一個數字的 array, 然後將非 leaf 的 node 變成是將兩個小孩節點之值的總和，因此，相對應的題目就變成在這個 array 裡面某個連續的空間找出值的總和。這個過程是一個特別的 reduction，專為這個題目做的一個轉換。

Segment tree 是一種 binary tree，它的 leaf node 就是 array element 的值，如下圖，

將它製做成 segment tree，其長相如下，

在中間節點的值就是底下兩個小孩節點的值總和。所以，在上圖中最左邊的 leaf node 是14 和15，他們的上一層節點就是14+15=29，依此類推。同時，在每個節點裡有一個特別的資料，用橘色來表示。橘色的字串代表的是一組位置，array 的index 編號的開始編號與結束編號。例如，上面提的29節點，它的橘色字串為1-2，代表了29的值是從array element 的第一個加到第二個，依此類推。再舉個例子，當你需要第三個到第六個的值時，你只需要找到兩個節點，3-4和5-6這兩個，就可以得到答案。當這個 segment tree 變得很大時，就省下了不少 traversal 步驟，以節省時間。

當 array 的某一個 element 的值改變了時，也只需要更新這個 leaf node 往上的值，一路更新到 root 即可，並不是全部的 tree node 都要更新。

以上談的 segment tree 雖然是用數字來作為例子，但實務上是可以有許多變化的，例如，每個node 的值不一定是數字,也可以是其他種類的資料型別，只要在往上資料彙聚的過程中可以用一個不複雜的方式將下一層的資料會聚在一起寫在上一層的結果。同時，這些結果一定要對你需要的搜尋結果有意義就行了。

Hope it helps,

閱讀全文

#95 Priority Queue 是不是 Queue ?

 在日常生活的情況中，排隊是一件很常見的事．原因是提供資源的人少，而使用資源的人多．例如，一堆人到便利商站買東西，買完後要結帳，而櫃檯人員只有一個，所以結帳得一個一個來，因此買商品的人就得排隊．在此時，如果出現一個文化水準低落的人來插隊，想必你一定會很生氣去跟對方說．在便利商店的排隊結帳來說，插隊通常不是件好事，但日常生活裡，某些特殊情況下，插隊是需要的，比如在醫院的急診室，或是馬路上遇到救護車救火車之類的，這種特殊情況，不緊急的必須先讓給緊急的．

當我們撰寫程式碼時，一般情況下我們會使用 Queue 資料結構來達成 "排隊" 的目的，然後，因應需求，如同急診室或救護車的例子，我們必須提供一個方法讓 "插隊" 可以成真．試著想一下，如果我們要用 Queue 結構的概念來達成插隊這件事，該怎麼做呢 ? 

假設我們用 Linked list 來實現 Queue 結構,

 

source: https://en.wikipedia.org/wiki/Linked_list

上面的 List 一共有三個元素，當實做 Enqueue() 時，我們可以把最新的元素加到最後面，這個動作的時間複雜度是 O(n)，n 是元素數量，當實做 Dequeue() 時，我們把前最面的元素讀取出來，然後第二個元素將變成第一個元素，時間複雜度是 O(1)．當我們要實做 "插隊" 時，我們該怎麼插隊呢 ? 首先，我們需要了解如何定義優先順序．以 List 而言，它的 index 位置就是優先順序 (Priority)，因為排在越前面會越先被 dequeue．假設我希望有一個元素能插隊在第二個位置，這表示我們得走到第二個元素，然後做插入的動作．這樣子有一個小缺點，我們必須知道每個元素的優先順序才能正確給出位置．如果我們必須先知道優先順序，這表示我們需要了解每一個元素的內容，這樣才能幫助你決定正確插入的位置是什麼．這顯然有點缺點，因為我們還得寫更多的程式碼來記錄每一個元素的意義，然後來決定該元素是重要還是不重要．

另外一個方法，我們可以將元素的內容改成兩個東西，一個是元素值和另一個是優先順序值．

上面的數字代表優先順序值，下面的數字是原來的元素值．當我們需要 Enqueue() 時，優先順序值就必須先指定．執行時間一久之後，你就會發現這方法也是有問題，因為若我們要將新元素指定到最後面，優先順序值就必須不斷新增，總有一天，這個數字將會超過 integer 的範圍．因此，用這個方法並不好，原因就在於我們必須指定優先順序值．如果我們不要指定優先順序值，同時有這樣的效果，那豈不是更好嗎 ? 此時，你就該了解到用  Queue 結構來實做並不是個好方法．

在資料結構的世界裡，有那一個結構能做到 Queue 的行為並且能定義優先順序的能力呢 ? 有的，它的名字叫 Heap，其範例如下圖所示:

source: https://en.wikipedia.org/wiki/Heap_(data_structure)

Heap 是一種特別的 Tree結構，它有一個很重要的特性，任何一個節點的值都必須大於等於或小於等於該節點以下所有的節點值．以上圖為例，這是一個大於等於的例子，意思就是每一個節點值都會比在它之下所有的節點值還要大或一樣．我們稱它為 max heap，若是小於等於，稱為 min heap．

節點值就是優先順序，只要我們能將需求面的優先順序定義清楚，就能把每一個工作 (節點) 建立 (Enqueue)  max heap，而建立的時間複雜度是 O(lg n)，其中 n 是所有節點的數量，這樣效能就比前面說的 Linked list 要來的好．取資料時 (Dequeue)，就直接將 root 取出，因為當下 root 是最大值的節點，然後再從 root 的子節點中挑出一個較大的節點做為新的 root 即可，以上圖例子而言將是 36，取出的時間複雜度是 O(1)．

使用 max/min heap 來做為具有優先順序功能的 Queue，就稱它為 Priority queue．在主要的程式語言裡 C++/Java 等的 library 都有實作 priority queue，所以讓大家可以直接用，方便許多．所以，當你需要一個有插隊功能的 queue 時，別忘了 priority queue．

閱讀全文

#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(n²) 和 O(n log n) 相差不多，一旦輸入的數量到達數以萬計時，你的家用 CPU 就會告訴你他們之間有很大的差距了．

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

閱讀全文

#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 也算是蠻有用的資料結構，不光是學術價值，其工業應用價值也是頗高，以後會寫文章來介紹它們.

閱讀全文

#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 的特別需要.
範例程式碼如下

閱讀全文

#48 老鼠走迷宮 (mouse maze)

在大學的資料結構的課程裡，大約在教過 Stack, Queue 和 List 這些基本的資料結構之後會有一個老鼠走迷宮的作業．這份作業說難不難，說簡單也沒那麼簡單，對一個正在學習資料結構的學生來說，花個一兩個晚上來寫這份作業是很正常的．如果寫程式正是你的工作，而且你以前沒念過資料結構的話，不妨試著做做看這份作業．

老鼠走迷宮的內容是，要隨機產生一個矩陣，矩陣的大小最好由使用者輸入設定的．然後在矩陣裡的每個位置也會隨機產生三種不同的地形，例如平地，河流與高山．你可以再設計其他不同的地形，老鼠在每一個地形上走動時會花費不同的體力，例如平地是 1 ，河流是 2，而老鼠是無法穿越高山．老鼠的出發點是矩陣的左上角，也就是 (0,0) 的位置, 然後終點在右下角，也就是 (n,m) 的位置，n,m 代表的是矩陣的兩個邊長．

你所要寫的程式是讓使用者輸入矩陣的大小，然後為矩陣的每一個格子隨機產生地形，接著老鼠從出發點開始移動，看看老鼠是否可以走到終點．因為地形中會有高山，所以老鼠不一定都會有一條路可以走到終點．然而，老鼠能走的路也可能不只一條能到終點，你可以試著找出一條就行了．

整個題目的重點在於兩個地方．第一，移動的方向要定出一套規則，第二，要能夠記錄走過的路跡．移動方向的規則可以用最簡單的方式來實行，除了在邊邊與角落以外的格子，每個格子都可以有八種移動方向，上，下，左，右，左上，左下，右上，右下．每到達一個格子時，就可以依照固定的順序來移動到下一個格子，如果在下一個格子都沒有路走或是每個方向都試過了，那就回到上一個格子．因此，路跡的記錄是很重要的，因為需要回到上一個格子．

以下我提供十多年前寫的版本

如果你順利寫完之後，還有一個延伸題目給你繼續挑戰，那就是如果有多條可以走的路跡時，列出最省力的路跡．這延伸題目就不是那麼簡單了，未來再來寫篇文章來討論．

閱讀全文

#42 資料庫基礎 - Index 所用的資料結構 B tree

在前面的文裡談了有關資料庫 Index，說明了為什麼 index 能加速尋找資料，也說明了 index 有那些種類．在這篇文中，將來簡單談一下 index 所使用的資料結構．

看了前面的文章後，想必你也可以很容易猜出 index 所使用的是像 tree 那樣的資料結構．在前面的文章中也談到了最基本的 tree 資料結構概念．tree 其實在電腦科學的領域裡應用的相當廣泛，不論是學術上或工業界裡，因為 tree 帶來的好處實在很多，但要把 tree 寫出來其實也不是一件很容易的事．不同的應用會衍生出不同的 tree，而在資料庫的 index 所採用的 tree 叫做  B-tree．所謂的 B 就是平衡 balance 這英文字，所以中文你可以用平衡樹來叫它．

B-tree 所指的平衡是指樹的每一個 leaf 到 root 都是一樣的高度，所以整顆樹看起來站的很穩，不會有缺一角的感覺．

source: http://cis.stvincent.edu/html/tutorials/swd/btree

為什麼 index 要選擇這樣的 tree 來做為資料結構呢 ? 原因就在於這個 tree 是平衡的，所有 data pointer 都是在 leaf 的地方，也就是說當資料庫引擎在 B-tree 上找資料時，不論它要去那一個 leaf，它所花的成本都是一樣的，也就是樹的高度．所以，以使用者的角度來看，你今天打 select * from student where studentID ='1' 或 select * from student where stuentID='100' ，在 index 上所花的成本都是一樣的．簡單的說就是把所有的資料一視同仁，讓大家都有一樣的存取時間成本．我想這對資料庫使用者來說是件重要的事情，因為你應該不會想讓某些資料有特權來得到較低的存取成本．

接下來的問題就是，我們怎麼會知道這顆樹會一直平衡呢 ? 這並不是資料庫引擎所要擔心的事情，因為保持平衡是 B-tree 本身就要具有的能力，也就是說當一個新的節點新增到這顆樹來後，樹的平衡機制就要啟動來調整樹本身的結構以保持平衡，同樣地刪除節點也是．所以，要實做 B-tree 的重點就是要看保持 "平衡" 的程式碼是不是寫的夠好．在這裡，我就不談論太多保持平衡的細節，若你有興趣知道 B-tree 是如何保持平衡的，可以參考 http://cis.stvincent.edu/html/tutorials/swd/btree/btree.html ，這個學校用圖案來表示當 B-tree 新增和刪除節點後是如何保持平衡的．

以外，B-tree 還有一些小變形，如 B+ tree，它是在 leaf 之間再加上一個 pointer 可以從一個 leaf 到下一個 leaf，這樣做的好處是我們可以在找到資料後，很快地再移到下一個資料而不需要每次都從 root 出發．我想這應該是大部份資料庫產品會採用的資料結構．

希望透過這篇文章的說明能讓你對資料庫 index 為什麼能為你快速找到資料有幫助．在了解了基本的原理之後，相信以後你在操作資料庫設定 index 時，心裡會有一種踏實的感覺，因為你知道資料庫引擎對這項工作運行時的基本原理了．

閱讀全文

#34 資料結構 - 非電腦科系的工程師們，你們體會多少了呢 ?

我第一次念資料結構時是因為準備台灣的資工研究所考試而念的，當時為了考試再加上時間也不夠多，所以念的很匆忙，沒有太多的時間思考著這門課程的精華．後來，念了研究所之後，研讀了一些學術論文，才慢慢了解到資料結構的精華．在許多學術論文裡都是討論著許多真實世界上的問題，通常這些問題會用一個數學公式或模型來表示，所以接下來的內容討論就可以直接在這數學公式或模型上直接去模擬．而這類的數學公式或模型若要用電腦程式來表達時，通常會發展出適合的演算法與資料結構．所以，這類的論文看多了之後，反而有幫助自己漸漸了解資料結構的精華．

基本上，電腦有二個基本的東西，一個運算器，一個是儲存空間．運算器就是大家所知的 CPU，而儲存空間就是記憶體和硬碟，其中記憶體是速度快但記憶時間較短，而硬碟是速度慢但記憶時間較長．這兩個東西你可以想成他們是長長的紙條，運算器可以在這長長的紙條上寫下資料，也可以讀取資料．

資料結構基本上就包含了兩件內容，一個是你需要用的資料是要寫在紙條上的何處，另一個就是如何在這些資料之間進行讀取或寫入．舉個例子，之前的文章提到 Array 這個資料結構．它的特性就是當你建立這個資料結構時，你必須先在紙條上找到一個符合你需要的足夠大的空間，而在資料之間進行讀取寫入的方式就是直接透過計算要讀或寫第幾個元素，就可以直接算出在紙條上的位址．例如，宣告了一個 byte array，一個有 20 個元素，如果第一個 byte 就是紙條上第 1000 個 byte 的位址，當我們要讀取第 5 個元素時，我們就知道要去 1005 byte 的位址上去讀取資料．

再舉另一個例子，Linked List．當你宣告了一個 Linked List 時，一開始你會先加入一個元素，這個元素可以寫在紙條上任何足夠空間的地方，而當你再加入另一個元素時，此時運算器就在紙條上任意一個足夠空間的地方把資料寫下，然後再回到第一個元素的位址上，把第二個元素的位址寫在第一個元素的空間中．所以，你可以知道在每個元素的空間中，除了元素的資料以後，還有下一個元素的地址．因此，當你想知道這個 Linked List 有多少元素時，你就必須從第一個元素一直讀到最後一個元素．

因此，課本裡面教的都是一些最基本的資料結構，就好像數學裡的四則運算一樣．電腦世界裡面的執行過程都是把紙條上的資料讀過來寫過去．當你發現你需要的問題很難用這些基本的資料結構來表達時，這時就是可以發明新的資料結構的時候了．

也許你會問，那這些跟平常的工作有什麼關係嗎 ? 比如，每天都在寫 JavaScript 搞前端畫面或是都在寫 java 寫後端程式．其實，多多少少會有關係的，尤其是你用物件導向在寫程式時，你所宣告的 class 就像是你定義了一種資料結構，這個 class 裡面所用到的儲存方式和運算方式都會大大地對程式在各方面有影響．就像是你知道了 Array 和 List 有何不同，你才會選得較適合的資料結構，也才能寫出比較快的程式碼．

未來的文章，不論是討論資料庫或是面試題目，你們都可以好好地思考一下是否還有其他可用的資料結構．不同的資料結構就代表程式的內容是不同的，可能會更好，也可能一樣，但也可能更差．所以，非電腦科系的工程師們，你們體會多少了呢 ?

閱讀全文

#15 資料結構 Tree

Tree 應該是我們所需要介紹的最後一個基礎的資料結構了．在資料庫的領域中，你可以看到 Tree 在那裡發揮的淋灕盡致．以我個人來說，我喜歡把 Tree 看成是一種 List 的變形金鋼．前面在談論到 List 時，你可以發現 List 的元素後面只會接著一個元素，就這樣一個一個串接下去，這種情況就可以用在作業系統的檔案儲存．你可以把一個檔案想成是一個 List，而檔案的內容就會依照固定的大小分割成很多個元素，然後依照順序排好串在一起，這些元素就會散落在硬碟空間中，他們不需要排列在一起，所以同一個檔案的內容在放置時，可能是最後的元素放在硬碟空間前面的位置，因為元素之間都有一個 link 記錄下一個元素的位置在那裡．

對 List 來說，如果一個元素有一個 link 的空間來記錄下一個元素在什麼地方，這稱為 Single link list，也就是說元素往下走了之後就回不來了，除非從頭開始．如果一個元素有兩個 link 空間，一個用來記錄下一個元素在那裡，另一個用來記錄上一個元素在那裡，這稱為 Double link list，可能在一個元素上往前走或是往後走，但這種的實務上的應用比較少些．對於 Tree 來說，它有多個 link 可以記錄下一階層的元素在那裡，所以用畫圖來表示的話，看起來就像下圖．

以上圖來說，Tree 的資料結構是:

Class TreeNode {
    public TreeNode left;
    public TreeNode middle;
    public TreeNode right;
    public string Data;
}

一個元素可以連結到三個元素，這個跟 List 的元素只有連結到一個元素是不太一樣的．也許你會提出問題，連結到一個元素和連結到三個元素或是更多的元素有什麼差別呢 ? 差別當然很多項，以我目前來看，我覺得最大的差別在於找到元素的速度．舉個例子，如果你用一個 List 來儲存一系列的數字，即便是這些數字已經依照某一個規則排列好，你在找時還是要從 List 裡的第一個元素開始，然後一個一個往下找．所以，如果都沒找到的話，你所花費的時間複雜度就是 O(n)．現在，相同的數字依照某個特定的規則製做成 Tree 的結構，而當你找某個數字時，只要從 TreeNode 某一個節點繼續往下找即可，所以每當經過一個節點往下一階層時，你就已經捨棄了 2/3 的內容，只剩下 1/3 的內容要找．所以找起來的時間複雜度是 O(logN)，這裡的 log 是以 3 為底，因為 TreeNode 可分為三個節點．

這時你可能會認為如果 Tree 在搜尋資料上是這麼好用的話，那我們是不是可以多用 Tree 少用 List ? 這就很難有一個正確答案了．雖然 List 的搜尋時間複雜度是 O(n)，不過建立 List 是相當簡單的，但要建立一個 Tree 就不像 List 那麼單純了．如果你建了一個 Tree 而只拿它來用一兩次的話，這實在是不太符合效益原則．而且，Tree 的結構是適合用來做資料尋找的速度加快用的，而不太適合用來儲存資料，你想想如果今天有一堆數字要存在電腦裡，你把它儲存成 Tree 的結構，而接下來要把所有的內容讀出來，你覺得 Tree 結構所採用的方法會比 List 或 Array 來的更方便和簡單嗎 ? 答案顯然是不會的．再說，你把資料弄成 Tree 結構來儲存，在空間使用上並沒有佔到任何便宜．

所以，通常你看到一些資料索引的技術背後的基礎資料結構一定會採用 Tree 結構，原因就是加速資料尋找速度，但真正的資料並不會用 Tree 結構來儲存，只是索引所使用的資料是以 Tree 結構來儲存．許多資料庫的產品為了加速資料尋找的速度，便採用了許多 Tree 結構．我們這邊講的是一個較廣泛的 Tree 結構，在不同的應用情況下，會有特製的 Tree 做為在那些特定情況下的解決方案．以後的文章內容會再談到那些細節．

閱讀全文

#14 資料結構 Queue

在基礎的資料結構裡，Stack有一個好兄弟，長的跟它有一點像，但是提供的行為結果卻剛好相反，它的名字叫 Queue．在 Stack 中有一個可以把資料放入的行為叫 push，而把資料讀出來的行為叫 pop，並且最重要的重點是最先放進去的資料將會後最後被讀取的，所以這是一種先進後出或後進先出的情況．

類似於 Stack，Queue 也提供了方法可以將資料寫進去和讀出來，習慣稱為 Enqeueue 和 Dequeue．而跟 Stack 最大的不同就是 Queue 先寫進去的資料將會是先被讀出來，是一種先進先出或後進後出的情況．

你可以在資料結構的課本看到以上的內容，也可以找到 Queue 是如何被實做的，通常來說用 Array 來實做 Queue 會比較單純一點，只要一個 Array 加上兩個 index 用來記錄資料的起點和結束點．

我們在這邊不談論 Queue 實做的細節，我們來談談在什麼情況下它會派上用場．

在 Stack 的文章裡，你曾聽我講故事提到有關文字編輯程式中常用的 "上一步" 功能，透過 Stack 的實作讓我們可以清楚地製做 "上一步"． 所以，你可以感受到當你在用 Stack 的時候，資料的順序會被倒過來．例如，你放 A B C 三個資料到 Stack，而讀出來時的順序是 C B A．所以，當你遇到需要這種資料巔倒的特性時，別忘了使用 Stack．

那 Queue 的特性呢 ? 你會很直覺地發現它並沒有提供什麼特別的效果，因為 A B C 的資料寫進去之後，讀出來的順序也是 A B C，那它有什麼過人之處需要我用到它呢 ? 若你能這樣直覺地想，其實也沒錯，因為若沒有什麼特別考量的話，資料先進先出的行為是帶來不了太多的好處． 但我想到了一個情況，如果你今天撰寫一個 API ，而你回傳的資料有規定必須要從頭開始讀取，如果你只是回傳一個 List 或一個 Array，那麼拿到資料的人就很容易違反規則，可以從中間或是從最後面開始讀取資料， 如果你回傳的資料結構是一個 Queue，那麼就等於限制了使用資料的人必須要從第一個資料開始讀，而且讀過之後就不能再重覆讀取相同的內容．我想這才是 Queue 所要展現的特性．

所以，Queue 的特點之一就在於第一個資料要被讀取之後，第二個資料才能被讀取． 這樣的特性似乎可以帶來某種程度的資料準確性，因為中間不會有資料被忽略而未被讀取．所以某些作業系統裡面或是某些商業產品便會依據這種特點來做成一個功能或產品，稱為 Queue system，例如在 Windows 作業系統中有 MSMQ (Microsoft Message Queue)，而 IBM 也有 MQ 的產品．只不過這些產品的範圍更大，是用在多台電腦環境下的資料傳送，而傳送的特性就是跟 Queue 一樣，前面的資料要先讀取，後面的資料才能讀取．

在不同的需求情況下，我們可以依據資料結構的特性來找出適合應用的地方，到目前為止，我介紹了基本的資料結構有 Array, List, Stack, Queue 以及 Hash table. 這些基本的資料結構常常在日常的工作中被使用到，而且也幾乎滿足了大部份的工作需要．所以，好好了解這幾個資料結構，對一個不複雜的軟體開發工作來說就相當足夠了．

不過，因為我後面有許多內容會談到資料庫，所以還需要多介紹一個基本的資料結構叫 Tree，這是下一篇的內容.

閱讀全文

#13 利用 Hash Table 來增加你的資料處理速度

還記得十多年前參加一個專案時，自己做了一件不好的資料處理方式，當時的我還不知道什麼是 hash function．在那時候專案部份的工作需要快速地處理大量的資料，透過資料庫連線讀取資料，然後再讀取相關的參考資料，再經過運算，最後把結果再寫回資料庫，如果你的方法是讀一筆寫一筆的話，那肯定會造成大量的資料庫 I/O，所以比較適合的方法是做批次的處理，也就是一次讀取某個足夠數量的資料筆數，處理完成之後再一次寫回去，這樣可以減少資料庫的 I/O，也可以讓程式運行起來速度可以快些．

以上的想法是可行的，但當時有一個小小的挑戰是有關參考資料，因為資料在運算的過程中必需依靠其他的數據才能計算，而這些數據多達 8 萬多筆資料，簡單的說，它是三個欄位構成，第一個是分行 ID，第二個是一個會計科目 ID，第三個資料值．

分行 ID

會計科目 ID

資料值

第一個 ID 和第二個 ID 是有相關的，它們之間是一個 many to many 的關係，也就是說當我要尋找資料值時，我必須要知道這兩個 ID 才行．當時專案所運用的伺服器還有相當足夠的記憶體空間，算一算資料量後，我就決定把那 8 萬多筆資料全部載入到記憶體，心裡想若一開始就把這些資料載入到記憶體之後，這樣資料在批次運算的過程中就可以直接到記憶體取得相關資料，如果一來更大大地減少資料庫的 I/O．心裡打的如意算盤正是如此，但當時我卻笨笨地用 List 結構把載入這 8 萬多筆資料到記憶體中，所以每當我要找資料時，我就用一個 for loop 把這個 List 結構從頭找到尾，只要前面兩個 ID 是相等時，就抓出第三個資料值．當時心裡，資料都在記憶體裡了，就算跑一個 for loop，以 CPU 對記憶體的速度來說也算是很快了．事後跑起來，運算速度也還是改進蠻多的，所以當時不但沒對 List 結構做改善，還一直以為自己做了一件相當聰明的事情．

後來當自己念了資料結構之後才發現到當初用 List 結構是多麼笨的事情，用時間複雜度的角度來看，那是一個 O(n)，其實可以做到 O(1)的．那要怎麼做到 O(1)呢? 以這個例子來說的話，我們就要做一個 hash table 裡面包著一個 hash table.

以 Java 語法為例子的話，其資料結構定義就變成

HashMap< UUID, HashMap<UUID, Integer>>

所以在讀取的時候就變成 hashMap.get( 分行 ID ).get( 會計科目 ID ) ，如果這兩個 ID 都存在的話，則使用 O(1) 就可以得到資料值．雖然資料都載入到記憶體了，透過 Hash function 的運用，我們還是可以讓整個運算再快一點．

Hash 在一般的軟體專案中用途非常的廣泛，常常是我們利用空間來換取時間的最常見的手法，因此熟悉它並且善用它一定會對你的程式執行有極大的幫助．

閱讀全文

#12 利用 Hash Table 來改進 FindSum4()

在 #2 的文章裡曾寫到 FindSum4() 的 Optimization 寫法，其程式碼再重新呈現如下：

當時我們用了 if ( i != j ) 的方式來做為一種 Optimization 的做法，當 ary 的元素越來越多時，整個程式的時間複雜度還是會往 O(n²) 靠近．理論上，這樣程式的時間複雜度還是 O(n²)．

先前的文章介紹了 Hash function 的好處，我們可以運用 Hash 的概念在這一個程式，

(以上是C#程式碼) 整個程式是 O(n).

從時間複雜度的角度來看，我們利用 hash 將程式的 O(n²) 變成 O(n)，而付出的代價是什麼呢 ? 付出的代價就是我們使用了 hash 在記憶體上的空間，最上面的程式是不需要有特別額外的記憶體空間，但第二個程式使用 hash 付出了 O(n) 的空間複雜度，這種用空間換取時間的情況在軟體的世界是非常常見的，因為在大部份的情況下我們比較在乎程式能在多久的時間內完成．

希望這個用 hash 來改進程式空間複雜度的例子能夠激發出你在日常工作上的想像力．

閱讀全文

#11 如何快速搜尋資料 - 利用 Hash function/Hash table

前面文章講了 binary search，這篇文章來介紹另一個好用而且非常常見的分類方法，它叫做 Hash．談到 Hash 時，通常包含兩個部份，一個是 Hash function，另一個是 Hash table．在業界的產品上，如 .Net/Java 等，都有提供業界標準的 hash function 以上一些 Hash table 的應用，如 .Net 的 HashSet, Dictionary 等就是 Hash table 的應用．首先，我們先談 Hash function．

Hash function 有一個很重要的特點是運算快速，那要多快呢? 最好是  O(1)，也就是指運算的速度不應該與輸入量的大小有關．換言之，你可以想像成你有兩個字串要輸入 hash function，其中一個字串很長，另一個字串很短，當你同時輸入到 hash function 運算時，得到結果的時間是一樣的．若用數學來表示，它就是 output = H (intput) ，其中 H 就是 hash function．

實行 Hash 的方法有無數種，你可以寫一個很簡單的．Hash 的實作要怎麼寫，這必須取決於你用 hash function 的目的是什麼．例如，你只是希望把一大堆的資料做一個簡單的分類，那麼你的 hash function 就可以用簡單的 mod (數學的求餘數) 來達成．舉個例子，有一些整數，而你要把他們分類到三個籃子裡，最簡單的方法就是求 3 的餘數，餘數如果是 0，那就放在第一個籃子，如果是 1，那就放在第二個籃子，以此類推．所以，你的整數數字經過 hash function 運算後就會被分成三個群組．今天若有人要找這些整數數字中有沒有 77 這個數字，那麼他只要到第三個籃子 ( 77 mod 3 = 2)，然後把第三個籃子裡面的數字全部找過一遍就知道有沒有 77了．以這例子來看，在尋找 77 的過程中，我們只需要尋找 1/3 的數字，另外有 2/3 的數字放在另外兩個籃子裡是不需要去找的，這等於加快了找資料的時間．所以，從這個例子來看，Hash 的分類法還蠻好用的，如果今天籃子夠多的話，這樣等於每個籃子裡面所儲存的數字越更少，因此找到數字的速度就會更快．

如果你的 hash function 的目的不像前面談的做分類這麼單純的話，則 hash function 的實作就得符合你的目的才行．在一般基本的加解密裡，多多少少會用到一點 hash function 的功能，如果此時 hash function 寫的太過簡單，這將造成加解密不夠 "強"．什麼樣才叫做夠 "強" 的 hash function 呢? 前面說的，output = H(input)，input 是你所定義的輸入範圍，可能是所有的字串，可能是所有的數字，也可能是所有的正整數．output 也是你定義的輸出範圍．通常來說一個夠強的 hash function 都會給出相同長度的 output．也就是說，H(1) = KI87CJDL , H(-100) = O9DI3KJ4 等等．Hash function 的目的並不是要加解密，output / input 的關係不用是一對一，所以一個 hash function 很有可能讓兩個或多個 input 得到相同的 output，例如 H(54839) = H(abcd)，只要你 "很難" 能找到兩個 input 會得到相同的 output，我們就可以稱這個 hash function 夠強，其中 "很難" 的意思就是你得花很多時間才能找到．

當一個 hash function 夠強時，它就具有單向和不可逆的特性，也就是說因為 "很難" 找到兩個 output 會得到同一個 input，因此當你看到 hash function 的 output 時，你就 "很難" 知道 input 會是什麼，就算你找到了一個，也不代表它就是目標 input，因為多個 input 會得到相同 output．"很難" 不代表不可能，只是很難而己．

你只要選到一個適合的 hash function，便能幫你處理很多的事情，適合不等於要夠強，主要符合你的需求即可，如前面說的資料分類功能．Java 和 .Net 平台都提供了業界裡常用的 Hash function，比如 MD5 或 SHA 演算法，提供了不同運算位元長度 ．而 Hash table 就是讓 input 經過 hash function 計算之後，讓 output 值做為放到籃子的依據，就像 Java 的 Hashmap 或 .Net 的 HashSet 之類的資料結構．如前面所說的，籃子越多，資料就能分更多的群組，所以當一樣數量的資料量要分類時，籃子越多的，裡面放的資料就更少．

接下來，你認為把 input 透過 hash function 得到 output 放到一個籃子裡，它的 Big O 怎麼算呢 ? 如果籃子都是空的，那就是 O(1)，因為此時只是一個簡單的數學運算，如前面提的求餘數 mod．這個運算跟資料數量大小沒有關係，如果你自己寫的 hash function 不是 O(1)，那就問題大了，因為這失去了 hash table 的意義．如果籃子不是空的呢 ? 這就要看籃子是用什麼資料結構做的．一般來說都會用 List，所以有一個新的資料放到籃子時，如果籃子已經有資料了，那麼新的資料就會被加到 List 的最前面，這動作也是 O(1)，所以使用 Hash table 時，平均來說，它的 Big O 就是 O(1)，也就是說當你使用 Hash table 時，平均來說，你找到資料是 O(1)，這個比用 Array 的 O(n) 來的快，也比用 Binary search (Olog(n)) 的方式要來的快．

閱讀全文

#10 資料結構 List

List 一般稱為 Linked List，這樣稱呼是因為在 List 裡面的每個元素都是一個連結連到下一個元素，這也稱為單向的 Linked List，如下圖所示：

這種單向的 List 應用在許多的情況下，例如作業系統的檔案寫入到硬碟時所採用的方式就是這樣單向 List 的概念．每個 List 都是由一個或多個元素所組成，而每個元素都有相同的資料結構，以上圖為例，元素裡包含了一個 decimal 和一個 pointer，這個指標所代表的是下一個元素的記憶體位址．所以，如果你要找 List 裡一共有多少元素時，就必須要從第一個元素一直移動到最後一個元素才能得知這個 List 一共有多少的元素．如果要尋找 List 中是不是有某一個元存在，唯一的方法也是得從第一個元素開始，然後沿著 pointer 到下一個元素一直找到最後．以上的動作若用 Big O 來表達都是 O(n)，其中 n 是元素的個數．

顯然跟 Array 比起來，List 在數元素的個數和尋找元素都慢了許多，但 List 也有其優點，由於 List 裡的元素之間是透過 pointer 來指向下一個元素的位址，所以下一個元素的位址可以隨意變更．也就是說當你想要插入或刪除一個元素到 List，這動作就變得相當有簡單．

上圖就是一個刪除元素的結果，只要把 pointer 指向到下下一個元素時，略過中間那一個元素就可以了，最後記得把中間元素從記憶體中釋放即可．其程式碼看起來如下：

nextNode = currentNode.next;
currentNode.next = currentNode.next.next;
free(nextNode);

如果新加入一個元素的話，其程式碼看起來如下：

ListNode newNode = new ListNode();
newNode.next = currentNode.next;
currentNode.next = newNode;

以上兩段程式碼中的 next 就是 pointer 所指向下一個元素的記憶體位址．由於 List 中的元素在實體的記憶體或硬碟空間中不需要相鄰在一起，因此讓插入元素和刪除元素的動作變得簡單．

閱讀全文

#9 Binary search 的 Big O ?

這是一個相當有趣的題目，前面講了 Binary search，因為它利用資料已排序好的特性，所以每次在尋找時可以中候選資料的中間切入來尋找，所以它的 Big O 該如何評估呢 ?

我們之前講到，如果現在找資料的方法是一個一個找，也就是說有十個資料時，最多要找十次，有十萬個資料時，最多要找十萬次，因此我們知道這方法和輸入的資料量成正比，所以是 O(n)．

Binary search 的 Big O 顯然一定比 O(n) 要快，那到底有多快呢 ? 我們可以來觀察一下．每次 binary search 在進行尋找時會從候選資料的中間尋找，然後依照目標值的大小來決定下一次尋找的候選資料是在前面一半還是後面一半，所以每次尋找後都可以將一半的資料給排除，比如說一開始有 100 個資料，經過第一次尋找後，下一回的候選資料就變成 50 個，再下一個就變成 25 個，以此類推．用數學的角度來看就形成了 2^y = n，其中 n 是資料輸入量，而 y 是尋找的次數，把式子轉變一下就形成了 y = log(n) ，其中這個 log 不是以 10 為基底，是以 2 為基底．所以，Binary search 的 Big O 就是 O(log(n))．

未來，寫程式的時候，如果你發現你的資料已排序好，那就記得多利用 Binary search 來做資料尋找，而不要一個一個找．因此，你也知道 O(log(n)) 的程式是比 O(n) 的程式還要來的快．

一般來說，寫 Binary search 有兩種寫法，一種是 recursive，另一種是 iterative.

Recursive :
          bool BSearch(int[] A, int target, int start, int end)
         {
             if (start < end) return false;
             int mid = (start + end) / 2;
             if (A[mid] == target)
                 return true;
             else if (target > A[mid])
                 return BSearch(A, target, mid + 1, end);
             else
                 return BSearch(A, target, start, mid - 1);
         }

Iterative :
         bool BSearch(int[] A, int target)
         {
             int start = 0;
             int end = A.Length - 1;
             while (start < end)
             {
                 int mid = (start + end) / 2;
                 if (A[mid] == target)
                     return true;
                 else if (target > A[mid])
                     start = mid + 1;
                 else
                     end = mid - 1;
             }
             return false;
         }

在沒有其他特別條件限制的情況下，Iterative 的寫法比較容易懂也比較好維護，同時也能避免 stack overflow (未來文章會再介紹) 的問題，所以多建議使用 Iterative 的寫法．

閱讀全文

#8 如何快速搜尋資料 - Binary Search

在以前還沒念電腦科學之前，對於快速搜尋這件事情完全沒什麼概念，唯一知道就是在一堆資料裡面一個一個找了，對於沒念過電腦科學的人來說，一個一個找是最直覺也是最簡單的方法．想像一個情況，一個 Array 裡面有一百個整數，假設每一個整數的值都不一樣，那麼我們想要知道這個 Array 裡面有沒有 77 這個數字，最直接的方法就是從 Array 的第一個元素找到最後一個元素，最好的情況是 77 這數字剛好在 Array 的第一個位置，那麼很快就可以找到了，若最壞的情況是 77 落在 Array 的最後一個位置或是 77 根本不在這裡面，那麼我們就必須從第一個元素找到最後一個元素．從我們之前講的 Big O 來看，這樣的搜尋所花的時間複雜度是 O(n)．這樣的情況有沒有可能更有效率呢?

如果我們今天很幸運得到一個已經排序好的 Array，那麼我們還需要從第一個找到最後一個嗎? 看來不一定喔! 想一想，如果是一個已經排序好的 Array，我們要從什麼地方開始找會比較好 ? 看看下圖的 Array，如果你要找 77 的話，你打算要怎麼找才能快一點．

在電腦科學的基礎課程中提供了一個簡單的方法，簡單的說就是用二分法來找，也就是 binary search．這個方法很簡單，一開始先從中間的位置開始找，以上圖的例子來看，中間是 55，如果我們要找 77 ，我們就知道 77 一定會在後面，不會在前面，原因就是這些元素都已經從小到大排序好了．接著，再用相同的方法，把後面的內容 (64,77,82,97) 再從中間找，而上述的例子剛好就找到了 77，所以一下子就找到了目標.

Binary search 是一個很簡單的概念，也是許多搜尋技術最基礎的想法．當我們再在一堆資料裡面去找某一個特定目標時，如果這一堆資料沒有特別的分類方法時，則很難產生出一個有效率的尋找過程，但如果這一堆資料經過了特別的分類方法，則就有機會產生出一個有效率的尋找過程．以 Binary search 來說，把資料排序好就是這個分類方法，而每次從中間元素開始找就是依這個分類方法而提出的有效率的尋找過程．

如果把層次拉到資料庫的產品，資料庫會有一堆的資料，而資料庫可以建立 B-tree，然後透過這個 B-tree 來尋找資料，所以資料庫引擎才能快速找到目標資料．B-tree 就是上述所說的分類方法，而在 B-tree 上游走就是上述的有效率的尋找過程．

如果把層次拉到像 Google 那樣的搜尋引擎，他們一定有很多的伺服器做索引之用，然後這些伺服器可以為同一個使用者要求來服務，所以當你輸入某個關鍵字時，才能如此快速得到結果，只不過這種層次的分類方法和有效率的尋找過程都是相當複雜的分散式程式．

閱讀全文

#6 資料結構 - Stack - part 2

承接上一篇的內容，我們要用什麼方式來做 Stack 的 "容器" 呢? 我們前面提過 Array 和 List，你覺得那一個用來做為 Stack 的容器比較適當?

我們在前面談過 Array 和 List，兩者最大的差異在於物件位於記憶體上的位置是緊連在一起還是允許分散的．如果緊連在一起，則讀取速度快，如果是分散的，則讀取速度慢．光是這一點，我想 Array 就足夠成為我們做為 Stack 容器的人選了．接下來我們用一個簡單的模型來談如何用 Array 做 Stack 的容器．

上圖是一個 Array，這裡頭一開始宣告了 5 個空間，所以可以放 5 個物件，然後有一個變數用來記錄目前最新儲存物件的位置，在上圖用箭頭來表示它，所以一開始並不會有箭頭出現，因為一開始 Array 都是空的．當使用者呼叫 Stack 的 push() 時，就會寫入一個物件，此時箭頭沒有出現，所以這個物件就被放在編號 0 的位置，同時箭號也會出現在這個位置上．接著更多的物件會再進來，於是就往 Array 空的位置上放，但要照順序放，也就是編號 0 放完，就換到編號 1，同時箭頭也更新到編號 1 的位置．

如果使用者呼叫了 Stack 的 pop()，則 Stack 只要將箭頭所在位置的物件回傳出去，然後箭頭往左邊移動就行了，也無需刪除該物件，若有新物件再進來時，那位置上的舊物件就會被覆寫．

透過這樣的方式，你就可以簡單地實做了一個 Stack，透過一個容器和一個箭頭就能達成讓先進來的物件最後才被讀出．

接下來你可能會問一個問題，如果 Array 滿了怎麼處理? 你可以有兩個選擇，第一是丟出錯誤訊息說容器滿了，裝不下新東西了，第二個選擇是再建立更大的容器好應付更多的物件．第二點就和之前談過的 ArrayList 蠻相近的，當 Array 滿的時候，就要建立更大的 Array 或是更多新的 Array，然後再把新進來的物件放到新Array中．

由於宣告一個新的且更大的 Array 並且再把舊 Array 上的元素搬到新的 Array 上，這其實算是個蠻費力的工作，所以我們總不希望這樣的事情常常發生，因此，一開始的 Array 或許不會太大，但我們再建立新的 Array 時，我們可以建大一點．比如說，一開始 Array 長度像上圖一樣是 5，當這個 Array 滿了需要建立新的 Array 時，我們可以建立長度 15 的 Array，如果再滿了，則可以建立長度 45 的 Array．所以你可以看到要建立新的 Array 時，新的長度一定要比原長度還要再多 2 倍以上．因為我們也不知道使用者最後到底要多大的 Stack 來裝他的物件，因此這種循序漸進的變大方式對電腦效能的衝擊會小一點．

所以，當你有機會需要做類似 "undo" 功能的時候，記得用 Stack，比較方便也比較好懂，對後面維護的人來說也易於了解．

閱讀全文

#5 資料結構 - Stack - part 1

還記得以前工作時曾有個一個經驗．有一天，我到同事的辦公室閒聊，聊著聊著他就跟我說他正在做一個新功能，當時我們正在做 Windows desktop應用程式，在這個程式裡面有一個編輯功能的頁面，讓使用者可以輸入產品的許多資料，而我同事正在做的就是為每個編輯動作留下記錄，好讓他可以做出 "undo" 的功能，而且要能一直 "undo" 下去．接著，他展現給我看他的成果，一切都運作的蠻好．接著，我就很好奇問他程式碼是怎麼寫的，接著他就展示相關的程式碼給我，他用了一個 .Net 的 DataTable，然後在這個 DataTable 裡建立了相關的欄位，如動作的序號，資料名稱，資料內容．因此，只要使用者一變動了某一個資料後，這個 DataTable 裡就會多了一筆資料，當使用者執行 "undo" 時，就會從這個 DataTable 裡尋找最大的序號，讀出該序號的資料並且更新 UI，然後將這筆資料從 DataTable 中刪除．如果這是你要做的功能，你會怎樣做呢？

聽完他的解釋之後，我滿臉的疑問馬上問他，你做了這麼多東西，你不覺得累嗎？ 你為什麼不用 Stack 呢? 你知道什麼是 Stack 吧! (因為他是數學系畢業的，我怕他不知道什麼是 Stack) 其實，我倒也不怎麼在乎他如何去實做這功能，只是想到未來有一天我和他都會離開這份工作，總有一天這些程式碼都會交給後面的人繼續開發和維護，我常在想如何未來的工程師們看到這樣的實作方式，不知道他們容不容易懂．

其實，像這樣的功能很常遇到，用 Stack 就對了．人們常說 "凡走過必留下痕跡"，而在軟體世界裡，用 Stack 來留下痕跡就相對地輕鬆．為什麼比較輕鬆呢？ 原因很簡單，抽象上來說 Stack 只提供兩種方法，一個是 push (放物件進去)，另一個 pop (把物件拿出來)，而最後放進去的物件將會是第一個被拿出來的．以上述我那位同事的例子來說，如果他用 Stack，那麼他根本不用去管理序號，也不用在 DataTable 裡去尋找最大的序號，也不用做讀出來的資料在 DataTable 裡刪除，因為 Stack 都幫他做了這些工作．

如果你的工作是程式設計相關，我相信你一定知道什麼是 Stack，這一個基本的資料結構在各大平台與作業系統中都會提供，當然在 java 和 .net 平台也有．接下來，我們討論一下 Stack 是什麼做的? 如果你沒看過 Stack 的實做，先思考一下，如果今天你的工作是寫出一個 Stack，你打算怎麼做呢? Stack 最基本的要求就是可以寫入物件，也可以讀出物件，但是物件的寫入讀取順序一定要按照先進後出，也就是後進先出的方式來進行．因此，我們首先可以想像的是 Stack 一定像是一個容器一樣，因為它要可以容納物件，同時還要有一個管理的機制，好讓先寫入的物件在讀取出會被優先讀出去．如果你能想到這樣，就差不多完成了一半的思考.

待續...

閱讀全文

#3 我需要懂資料結構嗎 ?

如果你的工作是系統管理或是網路工程領域，那麼資料結構可能對你不會有太大的影響，如果你的工作是程式設計或資料庫方面的領域，那麼資料結構對你將會是很重要的主題．若你的工作是程式設計類或資料庫類，即便你沒念過書本上的內容，我相信你對資料結構也有基本的認識．資料結構可以說是整個電腦科學裡相當基礎的知識，如果你把電腦科學用國中國小數學來比喻的話，則資料結構就像小學的四則運算一樣的基礎，必須要了解它才能通往更高級的方程式．

以目前的電腦架構來看，你可以把CPU視為一個做運算的單位，比如做加法運算或除法運算等等，而記憶體和硬碟的空間就像是一條有限長度的磁帶，你可以將資料寫在這條磁帶上，而記憶體這條磁帶比較短，但它讀取寫入速度較快，硬碟這條磁帶比較長，它讀取寫入速度較慢，所以當 CPU 運算時所需要的資料都是在記憶體和硬碟這兩條磁碟裡．接下來，當 CPU在運行時，要透過什麼規則來讀取寫入以及運算資料，那就會因為不同的程式應用而不同，所以在電腦科學裡就會因為不同的應用而定義出適合的資料結構．因此，簡單的來說，資料結構就是定義資料該如何儲存，該如何讀取，以及如何運算．

不論是那一種電腦系統，運行在該電腦上的作業系統一定都會提供一些基本的資料結構，例如 Array, Stack, Queue, List等等，而每個資料結構都有個自的特色以及運用的時機和技巧．比如，Array 的特色就是它的元素在記憶體空間中需要連在一起，也就是只要找到了 Array 的開始位置後，找第一個元素和找最後一個元素所需的時間都是一樣的，因為 Array 裡面的元素都是同一種 data type，所以每個元素在記憶體所佔的大小也都相同，因此很簡單就可以算的出來．List 跟 Array 在這方面剛好就有點不同，List 裡面的每個元素也都是一樣，但它並不需要把每個元素把放在記憶體中連續的空間，List 的元素可以東放一個，西放一個，在儲存位置的選擇上比較有彈性空間，也正是因為這樣的彈性空間，所以每個元素裡面需要有一個特別的位置 (我們稱它為pointer)，用來記錄下一個元素的位置在那裡，透過 pointer，我們才能從第一個元素一直走到最後一個元素，所以當你要存取 List 裡面某一個元素時，它的位置就不能像 Array 是用算出來，而必須從第一個元素開始走，一直走到你要的元素為止，所以每個元素的尋找時間是不一樣的．

接下來你可能會問，Array 和 List 看起來有點像，其實又不太一樣，我們該怎麼知道什麼情況下要用那一種呢? 這是一個很好的問題，有時很難給出很好的答案，但基本上我能給的答案是，如果你知道你所需要的元素個數，那麼你就用 Array，因為 Array 一開始必須要宣告它裡面能裝幾個元素，若情況剛好相反，你不確定你要裝多少個元素，而且存取元素的時間也不是你所在意的，那麼用 List 就提供了一些彈性．

如果你曾用過 java 或 .net 平台提供的 ArrayList，你可能曾想過這到底是 Array 還是 List 呢? 簡單地說，它是長的像 List 的 Array，本質上它還是 Array，但也提供了一些 List 的存取方式讓你來寫入或讀取裡面的元素．同時，它加上了改變 Array 長度的功能，也就是說你一直新增元素進去的話，那勢必會塞滿原有的 Array，所以若要再裝進更多的元素，則需要改變 Array 的長度．但是 Array 一旦宣告了之後就不能改變長度，所以有兩個可能的解決方法．
第一，宣告一個更長 Array，然後把原有 Array 的元素放到新的 Array 上，此時新的 Array 就有更多空間可以裝新的元素，然後把原有的 Array 從記憶體中釋放．
第二，宣告另一個一樣長度的 Array 來裝新的元素．此時就要做一些管理的動作，這樣 ArrayList 來讀取寫入資料時，才知道那一個 Array 是第一個，那一個 Array 是第二個．
可能還會有其他的方法，總之都是在做類似 Array 管理的動作，主要就是解決 Array 長度的問題．

未來文章再機會來談談這些基本的資料結構.

閱讀全文

#2 BIG O - 有關程式執行的快慢 - Optimization

從上一次寫的文章中可以看到如何辦別一個程式執行的好壞，那些都是相當基本而簡單的例子，但在工作中時，我們需要利用這技巧嗎? 答案當然是 YES，但在一般業界中 BIG O 的評估，有時並不是那麼單純，因為我們都習慣用了其他公司寫好的 framework 來進行我們的程式撰寫，比如用 Java platform 或 .Net platform ，所以一個 API 內部會如何執行，我們看不到原始碼就不太能準確知道，所以這一部份只能靠著多使用這些 framework 所得的經驗來知道那一個 API 比較好．

比如，前一篇文章曾講到 string1.Contains(string2)，要寫 Contains() 可以很簡單，你可以把 string 看成是一個 array，在這個 array 裡的元素就是字串裡的每個字母，而今天你要在這字串裡面尋找是否包含另一個子字串時，最簡單的方法就是寫 2 個 loops，外面的 loop 是用來記錄目前比對的位置，裡面的 loop 是用來比較 string1 從記錄點開始有沒有跟 string2 一樣的字元．以 Contains() 的角度來看，我們在評估 BIG O 時只看輸入參數的影響，所以我們不會去管 string1 的長短，在 string1 一樣的情況下，去看 string2 從很短到很長時對執行步驟的變化．這個是最簡單的寫法，難道你認為你用的 framework 就一定這樣寫嗎? 那可不一定. 這些產品工程師們總是有可能想到更好的寫法，所以有時候若有機會去看看這些 framework 的原始碼時，相信會對於你寫程式的功力將大有幫助.

BIG O 談的是輸入參數變化量對程式本身影響的一個趨勢，在業界中，當然會利用這個技巧來討論，除此之外，在業界中還更需要做一些 optimization. 什麼是 optimization 呢? 簡單的說，就是去掉一些沒有用的執行. 讓我們來看上一篇 FindSum4() 的例子.

bool FindSum4(int[] ary, int target) {
    for (int i = 0; i < ary.length ; i++) {
        for ( int j = 0 ; j < ary.length ; j++) {
            if ( i != j ) 
            {
                int sum = ary[i] + ary[j];
                if ( sum == target ) {
                    return true;
                }
            }
        }
    }
    return false;
}

你看看上面寫的例子還有沒有可以改進的地方呢? 可以改進的地方就是有些運算其實是重覆了．其實重覆的地方很多，比如 i = 0 , j = 1 和 j = 0 , i = 1 的運算是一樣的，因為都是抓 ary 的第一個元素和第二個元素來做加法運算. 所以你可以看到 loop 的次數其實可以不用跑那麼多次的，我們只要改一下

bool FindSum4(int[] ary, int target) {
    for (int i = 0; i < ary.length ; i++) {
        for ( int j = i + 1 ; j < ary.length ; j++) {
            if ( i != j ) 
            {
                int sum = ary[i] + ary[j];
                if ( sum == target ) {
                    return true;
                }
            }
        }
    }
    return false;
}

把第二個 loop 的 j = 0 改成 j = i + 1，這樣就大大減少了 loop 內容執行的次數了，而且 if ( i != j ) 還是多餘的．雖然這不一定是最完美的 optimization，但相信你抓住我所要講的重點，那就是去除掉一些重覆的執行動作，雖然以上的兩個程式的 BIG O 都是一樣的，但在工作時，我們還是會要求工程師要做優良的 optimization. 畢竟你輸入的 ary 不可能是無窮大，電腦記憶體是有限的，所以做優良的 optimization 的確是可以幫助你讓程式別重覆做同樣的動作．

話說回來，那像 FindSum4() 是不是還有更好的寫法呢? 答案是有的，以後在適當的內容時會再說明．

閱讀全文