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

閱讀全文