一些不常見但是很重要的資料結構
這篇文章是stackoverflow的一篇帖子 。上面提到了很多有用的資料結構。有的聽過了,經常用,有的沒有聽過,記錄下來。
-
Trie樹。應用比較多,一個比較cool的trie的應用TRASH-A dynamic LC-trie and hash data structure。
-
Bloom filter。wiki連結 刪除某一項是不允許的,不過可以實現可計數的counting bloom filter
-
在BigTable,Cassandra中都有使用
-
可以用來快速檢查是否拼寫錯誤
-
Rope :rope 資料結構表示不能修改的字元序列,與 Java 的 String非常像。但是 ropes 效率奇高的字串變換操作使得它與 String及其同一體系的可修改的 StringBuffer和 StringBuilder大不相同,非常適合那些執行繁重字串操縱的應用程式,尤其在多執行緒環境下更是如此。ibm文章 包含java實現。
-
stl實現:http://www.sgi.com/tech/stl/Rope.html
-
skip list :這裡有一個演示:http://iamwww.unibe.ch/~wenger/DA/SkipList/
-
Cassandra的索引
-
redis的SortedSet
-
Bit Array :壓縮儲存bit,支援快速的bit操作。
-
Zippers : 在函數語言程式設計中非常有用。
-
Suffix tries : 字串搜尋非常有用。更酷的是suffix tree,可以O(n)的時間構建
-
Splay trees:非常酷的結構
-
非常小巧,僅需要類似二叉樹的左右孩子指標
-
相對容易實現
-
效能良好,wiki地址
-
Heap-ordered search trees
-
鄰接表:O(1)計算無向圖的鄰居節點
-
lock-free:
-
http://stackoverflow.com/questions/2101789/implementation-of-a-work-stealing-queue-in-c-c
-
一個非常好的這方面的部落格:Mike Acton‘s
-
並查集
-
fibonacci堆
-
BSP Trees:應用在3D渲染領域
-
霍夫曼樹:壓縮
-
Finger Trees:在函式式結構中使用,wiki地址
-
Ring buffer
-
Merkle trees
-
Cukoo Hashing :用來提升hash方法的空間利用,基本思想是利用多個hash函式,降低衝突。
-
快取引數無關資料結構:Cache Oblivious datastructures
-
Left learning Red-Back Trees:論文
-
O(1) size, union, insert, minimum
-
O(logn) deleteMin
-
Interval Trees : 在Cassandra中有應用
上面僅僅寫了一半,就有好多我不熟悉的了。剩下的一半不是很火,更是沒有聽過。就先這些吧。
本文連結:http://www.cnblogs.com/sing1ee/archive/2012/10/12/2765064.html ,轉載請註明。