軟體學徒forever

今天請假在家休息，複習了一下 Foundations of Computer Science 中關於Set的原理與實作。順手整理一下幾種常見的實作方式以及優缺點。 假設兩個Set的大小分別為m個元素與n個元素： unsorted list：求union、intersection、difference的需要O(m*n)，效率不好，但在很多情況下，輸入就僅是unsorted list，沒得選。算法很直覺，可參考 Foundations of Computer Science 第五章。 sorted list：當m與n很接近時，先將list排序可大幅將Set的三種基本運算降至O(n*logn)。 characteristic vector(bitmap)：當元素範圍是在某個固定範圍，並且數量不會多到不易儲存時(bitmap需要初始化，所以數量必須事先確定，不然反覆copy至更大容量的空間會非常沒效率)，用bitmap可以將Set運算降到O(m+n)。 hash table：妥善設計的hash table，可以同時獲得bitmap的效能以及sorted list的彈性，但必須將hash function以及collision的處理設計的有效率，而這需要依據應用進行實驗。 除了用到的資料結構以外，作者還逐步擴展Set的概念，為relational model奠定基礎。

原文作者： Rob Landley 原文連結： http://lxr.linux.no/linux+v3.2.1/Documentation/rbtree.txt red-black tree是什麼？它們有什麼用？ red-black tree是一種self-balancing binary search tree，用來儲存可被排序的key/value資料組合。與radix trees不同（用來有效地儲存sparse arrays，所以會用長整數的索引來安插/存取/刪除節點），也與hash tables不同（沒有保持在有序的狀態，所以無法輕易地以有序的方式巡訪，並且必須以特定的大小與hash function來微調效能，而rbtresss則可以優雅地擴展並儲存任意的key值）。 （譯註：雖然是很基本的觀念，但小弟還是要囉唆一下。資料結構的選用是因時制宜的。千萬不要以為rbtrees比上述兩種結構好，rbtrees基本上算是對各種操作最四平八穩的結構，但應用時，往往可以挑選更佳的資料結構。舉例來說，如果我們只需要安插/搜尋節點，那麼幾乎沒有什麼資料結構比hash table更合適了，複雜度只要O(1)。） red-black tree跟AVL trees很像，不過為最糟狀況下的安插與刪除提供了較佳的時間表現（個別最多兩次旋轉與三次旋轉便可讓tree恢復平衡），不過對於搜尋會有一點點的損失（不過還是保持在O(logn）)。 引用自Linux Weekly News： 在kernel中有許多red-black trees的應用。deadline與CFQ I/O排程器用rbtrees追蹤請求；ext3檔案系統使用rbtrees紀錄directory entries。Virtual memory areas (VMAs) 也是以rbtrees追蹤、epoll的檔案描述器、密碼學用的key值、以及在"階層式token bucket"的網路封包。 這份文件涵蓋Linux rbtress的使用方式。更多有關red-black tree的原理與實作資訊可參考：     Linux Weekly News上的文章     http://lwn.net/Articles/184495/  ...

在讀書時，只要有修過資料結構課程，一定都有接觸過 Priority Queue 的概念，priority queue的應用範圍很廣泛，也知道高效的Priority Queue一般都會以 Heap 來實作，但隨著遠離學生時代，每天在繁雜的軟體架構中求生存，不斷地把時間花在debug、了解現存介面的使用，有時不免讓人覺得有些疲憊(當然啦，有時開發某些模組還是頗有挑戰性，但我一般80%的時間的確都是勞力為主:P)。所以為了讓自己保持清醒，今晚就來複習一下Priority Queues的概念吧~ Priority Queues通常至少支援兩個操作：insert和delete_min。如果需要動態改變元素的priority，那麼還會再支援increase_priority, decrease_priority。甚至，有時會需要頻繁的合併多個Priority Queues，所以merge_priority_queue有時也是必要的，而高效的merge需要更複雜的heap，像是 binomial heap 或是 Fibonacci heap 。 讓我們先考慮基本操作：insert以及delete_min就好。如果只要支援這兩個操作，我們可以簡單地利用 binary heap 來完成。由於binary heap的結構通常非常精簡，可以array來實作，所以從任一元素找尋其parent與children都非常快速。以下是我用C語言的試作代碼。 注意：雖然我有針對使用的型別別作了一般化，但對於內建型別(如整數)可能會帶來些許性能損失。當然啦，如果用C++，就可以用 template specialization 把這個問題去除。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92...