Linux內(nèi)核中的紅黑樹

dreamice

原帖由 蚊見蚊愛 于 2009-1-3 16:45 發(fā)表
這種數(shù)據(jù)結(jié)構(gòu)的東西，還是看教材，代碼參考產(chǎn)品代碼 (STL 中也有 這個數(shù)據(jù)結(jié)構(gòu)， )，最好不要使用未經(jīng)嚴格測試的代碼，

STL確實比較強大
Linux內(nèi)核中的這部分代碼，應(yīng)該是比較穩(wěn)定可靠的了:wink:

lbaby

原帖由 Godbach 于 2009-1-2 12:50 發(fā)表
請教prolj兄一個問題：
如果我想統(tǒng)計一段時間內(nèi)和我本地主機通信的IP總數(shù)，你覺得用哪種方式實現(xiàn)更好？

這個rb_tree 和hash 都好，  hash 的難點就在于估算總數(shù)，在數(shù)量級可以預(yù)見的情況下，hash的性能可以令人非常滿意

Godbach

原帖由 lbaby 于 2009-1-3 22:33 發(fā)表


這個rb_tree 和hash 都好，  hash 的難點就在于估算總數(shù)，在數(shù)量級可以預(yù)見的情況下，hash的性能可以令人非常滿意

可以預(yù)見的情況下？
那如果我設(shè)定了hash表項最多為500,000個，應(yīng)該也算可預(yù)見吧。這個時侯lbaby兄會在hash和rb_tree之間選擇那個？

dreamice

原帖由 lbaby 于 2009-1-3 22:33 發(fā)表


這個rb_tree 和hash 都好，  hash 的難點就在于估算總數(shù)，在數(shù)量級可以預(yù)見的情況下，hash的性能可以令人非常滿意

如果樹建好了后，不存在插入和刪除的話，其實AVL樹的性能比rbtree還占優(yōu)勢:wink:

Godbach

是嗎。不過很多情況下建樹主要就是用來動態(tài)的插入和刪除吧。

dreamice

原帖由 Godbach 于 2009-1-3 22:44 發(fā)表
是嗎。不過很多情況下建樹主要就是用來動態(tài)的插入和刪除吧。

也有用靜態(tài)樹的情況，這樣的話用avl樹性能上稍微好一些，但沒有數(shù)量級的提升，都是log（N）級的。

Godbach

原帖由 dreamice 于 2009-1-3 22:49 發(fā)表


也有用靜態(tài)樹的情況，這樣的話用avl樹性能上稍微好一些，但沒有數(shù)量級的提升，都是log（N）級的。

OK，以后有對應(yīng)的應(yīng)用可以嘗試一下。

lbaby

原帖由 Godbach 于 2009-1-3 22:36 發(fā)表


可以預(yù)見的情況下？
那如果我設(shè)定了hash表項最多為500,000個，應(yīng)該也算可預(yù)見吧。這個時侯lbaby兄會在hash和rb_tree之間選擇那個？

可預(yù)見的意思是，  你可以根據(jù)歷史或經(jīng)驗估算出你要處理的數(shù)據(jù)的數(shù)量級，和你想出來的設(shè)定的那個數(shù)無關(guān)

比如：你的站點每日訪問量100萬，那我們就在大于 150萬 小于200萬之間選一個素數(shù)作為hash表項大小
如果我上邊沒說清，我這里補充一下

hash 表的實現(xiàn)簡單，用起來也好用，現(xiàn)在的內(nèi)存都是白菜價，不用白不用。
省下的時間都是自己的，泡泡妞，灌灌水， 何樂而不為捏？

lbaby

http://lxr.linux.no/linux+v2.6.28/include/linux/hash.h

另外內(nèi)核里也有不錯的 hash 實現(xiàn)，Godbach 兄可以去看看

Godbach

譬如說我的設(shè)備最多就防50萬個鏈接，再多的我都直接放過。不用添加表項。

也就是我知道我的設(shè)備就可以處理的上限。我以這個上限建表，也算固定的了

[ 本帖最后由 Godbach 于 2009-1-4 10:07 編輯 ]