作者a3785lexx (Alex)
看板EE_DSnP
標題[閒聊] BST delete的效能......囧
時間Sat Dec 5 04:30:33 2009
本文內容純粹閒聊
如果您：
1)還在寫自己的BST，不想被雷(其實也還好...)
2)還在替BST debug，想要找參考資料或幫助(小弟保證這裡絕對沒有線索)
3)有人生更美好之事物
本文應該不會符合您的期待，請謹慎思考後閱讀
如提，剛剛爆肝爆好久...
就是為了要能夠幫我的BST::adtd提升效能
結果...
把erase從純傳入iterator打掉，擴充成為傳入一堆的BSTreeNode<T>*
效能還是沒有辦法提升多少......(約5%......囧)
我這個砍掉重練的過程可是寫了快三小時耶！╯-____-)╯~═╩════╩═~
雖然效率這麼低落一方面是因為半夜精神不佳容易腦包orz...
其實我原本是想要把原版改成純iterator操作的
因為我的寫法裡...要知道parent是誰只能進入iterator mode = ="
原版是用iterator跟外界接頭，然後裡面換成BSTreeNode<T>*實作
我其實連getLeftChild、getRightChild、getSuccessor、getParent
的iterator版本都備好了...不過後來覺得其實上面這幾個function
實作的時候也都是透過BSTreeNode<T>*的轉換...
所以索性就全部轟掉變成BSTreeNode<T>*的操作了...
結果呢...只有在delete 50000這種超小數字的時候可以很快
(第一發使用會有0的假象)
但是一到了很大的數字的時候就......囧
我都已經把-g關掉了...看來是沒梗了嗎XDrz...
話說大家有沒有什麼妙法可以提升delete的速度呢XD？
我個人覺得嚴重拖垮效能的關鍵在於沒有存parent？
因為如果depth很深的話...trace就要走很久很久才會走到的感覺
可是我已經把找parent的次數壓縮成一整次delete只找一次啊...(大概吧...)
難道還有其他梗不成？？
其他就是找successor可能比較花時間了，但我個人覺得已經很難寫更快了囧
還是說這就是recursive和loop的差距呢...
話說我從以前幾乎沒有用recursive變成現在常常用recursive...
這大概三個月前的我都沒有辦法想像吧XD
(recursive真是好物啊
啊...其實我本來有想要用一個array來實作BST的
這樣就可以不用trace也能夠輕鬆的得到下家和上家的位置了
可是...
1.)大家都說這很作弊(個人覺得還好...)
2.)那樣很耗空間(最糟的情況下會耗用正常的(2^(N) - N)這麼多)
3.)比較不耗空間的版本中，目標物件要用*的形式存起來，不太直覺。
4.)這樣算上下家還要透過BSTree來算，也是不直覺
所以就沒寫了......o.O
不知道如果有偷存parent或是用array這種輔助座標來記錄
delete會不會比較快呢？
很想知道有沒有人有這樣實作的可以分享一下心得XD？
(順帶一提，爆肝三小時的額外收穫：code變好看一點點了...XD)
突然想到有個問題忘了問XD
recursive，然後一次傳很多&參數
跟recursive，然後每級都新增很多變數
到底誰會比較快啊XD？
目前我是用前者...雖然說理論上記憶體吃比較少
(真的嗎= ="？ 我一直在想reference總也該要吃個記憶體來記得
這個alias的關聯吧？？不知道到底有沒有偷偷吃就是了XD)
但是每次recursive call就是4個參數傳進去了...
為了要讓沒有變數在任何一級新增...orz
而且因為都要是&所以也不能說偷懶不傳...
而且效能也沒說多好...T_T
還是說其實我從根本上(iterator的實作？)就是有問題的呢...好奇怪啊
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.37.102.31
1F：推 ric2k1:(咳) 用 array 來做 bst 算是作弊哦~~~ 12/05 10:51
2F：→ a3785lexx:啊..是歐＠＠... 12/05 11:19
3F：→ a3785lexx:我是因為覺得 1.)印象中教授有介紹過BST存array的index 12/05 11:21
4F：→ a3785lexx:的實作方法，好處是64-bit可以省記憶體 12/05 11:21
5F：→ a3785lexx:2.)其實就算用array事情(++、--)也不會比較簡單...orz？ 12/05 11:22
6F：→ a3785lexx:所以覺得作弊的成分好像還好...XDrz 12/05 11:23
7F：→ a3785lexx:只是想到眾多array法中的一種是可以巧妙的不佔記憶體就 12/05 11:28
8F：→ a3785lexx:可以知道到底parent/children在哪裡...所以有點心動XD 12/05 11:28
9F：→ a3785lexx:啊...話說只看內文大概沒有人看的出來我的delete效率 12/05 11:29
10F：→ a3785lexx:差到什麼程度... 簡單來說就是整個do.all跑完大概是 12/05 11:30
11F：→ a3785lexx:教授的2.X倍時間吧.......orz 12/05 11:30
※ 編輯: a3785lexx 來自: 114.37.102.193 (12/05 11:48)
12F：推 ric2k1:oh, 如果你的意思是用 array index 取代 BSTNode*，那是 12/05 11:45
13F：→ ric2k1:沒有關係。背後的操作應該還是 bst 的 operationy 12/05 11:46
14F：推 ric2k1:2.X 倍 OK 呀! size 大一點還是 2.X 倍嗎? 看不懂你最後的 12/05 11:55
15F：→ ric2k1:問題 12/05 11:55
16F：→ a3785lexx:呃...其實就是在size很大的時候會2.X倍 XD 12/05 11:57
17F：→ a3785lexx:恩我最後的問題就是，每級recursive裡面都總要有一個 12/05 11:58
18F：→ a3785lexx:暫時的位置來放東西(目前不知道要怎麼避免) 12/05 11:58
19F：→ a3785lexx:然後就想到recursive萬一跑到幾千幾萬次... 12/05 11:59
20F：→ a3785lexx:這樣就太吃記憶體了。 所以就把他當成參數傳下去 12/05 11:59
21F：→ a3785lexx:然後每級都用&去接他，這樣也許可以省一點？？？ 12/05 12:00
22F：→ a3785lexx:如果運氣好可能還順便省時間？不過我不知道XDrz 12/05 12:00
23F：推 ric2k1:幾萬次 = 1MB memory? Maybe that's not a problem. 12/05 12:15
24F：→ flax00298:如果改成＆可行的話就會少作COPY的時間吧？ 12/05 12:44
25F：→ a3785lexx:目前&是可行可是沒有快到哪裡去XD 12/05 12:51
26F：→ a3785lexx:其實我最原始的版本本來是沒有用&recursive的... 12/05 12:51
27F：→ a3785lexx:而且一直涉及iterator<->BSTreeNode<T>*的轉換 12/05 12:51
28F：→ a3785lexx:結果這兩個版本在大資料量的情況下也才差5%...o.O 12/05 12:52
29F：→ a3785lexx:雖然小資料量的情況下會明顯增快很多就是了... 12/05 12:52
30F：→ a3785lexx:雖然我也不知道為甚麼XD 12/05 12:52
31F：→ a3785lexx:呵呵...剛剛作了個小實驗... 12/05 13:27
32F：→ a3785lexx:強迫讓每一級都一定會找一次parent來 12/05 13:28
33F：→ a3785lexx:結果並沒有變慢多少....居然差不到0.1%... 12/05 13:29
34F：→ a3785lexx:所以其實問題根本不是出在我parent找太慢嗎XDrz... 12/05 13:29
35F：→ a3785lexx:還是說因為我加的太突兀了所以被optimized掉了嗎XD 12/05 13:30
36F：→ a3785lexx:倒是在剛進erase的時候就強迫他找兩次parent還比較慢 12/05 13:37
37F：→ a3785lexx:所以說平均而言一次erase其實不會找超過兩次successor 12/05 13:38
38F：→ a3785lexx:嗎？？ 12/05 13:38
39F：推 keyboardle:根據演算法.一次delete最多找一次succesor 12/05 14:52
40F：→ keyboardle:因為需要找succesor的case的succesor必只有一子或沒有 12/05 14:53
41F：→ a3785lexx:其實好像偶爾會超過一次的樣子XD？最少我的會啦XD 12/05 15:11
42F：→ a3785lexx:不過根據實驗...平均次數其實還低於1說... 12/05 15:11
43F：→ a3785lexx:這樣就不難理解為甚麼我把原版改變之後效率無法提升了.. 12/05 15:13
44F：→ a3785lexx:原版是效率很爛的recursive...不過既然他recursive的 12/05 15:13
45F：→ a3785lexx:機率不高，當然效能提升有限XDrz 12/05 15:14
46F：→ a3785lexx:不過我不能明白的就是...我在recursive的起點強迫多找 12/05 15:16
47F：→ a3785lexx:兩次parent，結果他所需時間也沒有變三倍...(原本只會 12/05 15:16
48F：→ a3785lexx:找一次) 12/05 15:16
49F：→ a3785lexx:所以拖垮效能的倒底是什麼......orz 12/05 15:17
50F：→ a3785lexx:應該不會是我find寫太爛了吧囧 insert的表現還不錯啊XD 12/05 15:17
51F：推 keyboardle:記憶中random delete的話應該最花時間的是iterator++?? 12/05 15:18
52F：→ a3785lexx:原來是這樣！ 恍然大悟！ 12/05 15:23
53F：→ a3785lexx:我一直以為random delete是叫erase(const T&)...... 12/05 15:23
54F：→ a3785lexx:畢竟用內部的find絕對會比外面用iterator還要快很多... 12/05 15:24
55F：→ a3785lexx:感謝key大...我終於能夠把差距拉到10秒內了@@" 12/05 16:14
56F：推 herbert570:其實用 array 實作 bst node 效率很快.... 12/05 22:23
57F：推 herbert570:只要操作數字上的運算就可以找到parent 和 child 12/05 22:25
58F：→ herbert570:不過就是要整理樹就是了.....不然記憶體會區段錯誤... 12/05 22:26
59F：→ a3785lexx:嗯嗯我也是這樣想...想array應該很快吧XD？ 12/06 02:03
60F：→ a3785lexx:不過我沒有array就已經程式記憶體區段錯誤了....囧 12/06 02:03
61F：推 herbert570:array 很快是因為測資少的緣故... 12/06 03:13