作者JUSer (憲憲)
看板EE_DSnP
標題[問題] 關於BST的performance
時間Wed Dec 9 17:46:59 2009
我用的寫法是parent的BST寫法
跑出來的結果時間大概是ref的2/3 memory用量是3/2
重點是以上是insert的結果
我的erase的速度就反而比ref慢了一點點
但memory用量一樣是3/2
我現在在想我的erase的架構裡長得像
if...pos==begin()
else if...pos==end()
else if...no children
else if...one children
else...two children
用了很多的判斷式切分成五種情形去做
這樣是不是會影響到performance?
因為照理說寫得好的話速度應該也要較ref快!?
畢竟memory多用了1.5倍...
and...因為我的用tree也有用dummy cell
亂數產生跟ref差一個 這樣我需不需要想辦法去改?
感謝回答XD
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.248.225
※ 編輯: JUSer 來自: 140.112.248.225 (12/09 17:47)
1F：→ a3785lexx:但請記得有記_parent就表示還要去maintain他吧XD？ 12/09 18:34
2F：→ a3785lexx:差一個的問題，我的解決方法是：傳參數給constructor 12/09 18:35
3F：→ a3785lexx:畢竟他是dummy也許還好XD 12/09 18:35
4F：→ a3785lexx:insert為甚麼有parent會比較快我反而不明白XDrz... 12/09 18:36
5F：→ a3785lexx:trace派也沒有比存parent還要多作什麼事情的感覺啊@@" 12/09 18:37
6F：推 ric2k1:亂數產生跟ref差一個 沒有關係 12/09 19:53
7F：→ sa072686:我是dummy code只塞NULL，避免對它取值就好..就一樣了 12/10 07:57
8F：→ sa072686:有dummy應該可以不用判斷begin, no child和one child 12/10 07:58
9F：→ sa072686:可以併起來做 12/10 07:58
10F：→ sa072686:切細應該是變快，可以針對性地寫而不用顧慮general.. 12/10 08:00
11F：→ sa072686:不過如果是adtd -r 那iterator的++()影響很大.. 12/10 08:01
12F：→ sa072686:所以我後來改進了某個地方，reference砍2X秒我只花<1秒 12/10 08:02
13F：推 a3785lexx:樓上練成絕世神功？？ 12/10 14:04
14F：推 dryman:是改用不同的traversal方式嗎？ 12/10 15:29
15F：推 dryman:好像不是XD 12/10 15:40
16F：→ sa072686:提示是看adtTest.cpp關於delete的地方，只改bst.h即可 12/10 16:12
17F：→ JUSer:感謝各位大大我的數字問題已經解決...performance努力中 12/10 23:03