[閒聊] BST delete的效能......囧

[a3785lexx (Alex)]

        本文內容純粹閒聊

        如果您：

        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
推 ric2k1:(咳) 用 array 來做 bst 算是作弊哦~~~
→ a3785lexx:啊..是歐＠＠...
→ a3785lexx:我是因為覺得 1.)印象中教授有介紹過BST存array的index
→ a3785lexx:的實作方法，好處是64-bit可以省記憶體
→ a3785lexx:2.)其實就算用array事情(++、--)也不會比較簡單...orz？
→ a3785lexx:所以覺得作弊的成分好像還好...XDrz
→ a3785lexx:只是想到眾多array法中的一種是可以巧妙的不佔記憶體就
→ a3785lexx:可以知道到底parent/children在哪裡...所以有點心動XD
→ a3785lexx:啊...話說只看內文大概沒有人看的出來我的delete效率
→ a3785lexx:差到什麼程度...     簡單來說就是整個do.all跑完大概是
→ a3785lexx:教授的2.X倍時間吧.......orz
※ 編輯: a3785lexx       來自: 114.37.102.193       (12/05 11:48)
推 ric2k1:oh, 如果你的意思是用 array index 取代 BSTNode*，那是
→ ric2k1:沒有關係。背後的操作應該還是 bst 的 operationy
推 ric2k1:2.X 倍 OK 呀! size 大一點還是 2.X 倍嗎? 看不懂你最後的
→ ric2k1:問題
→ a3785lexx:呃...其實就是在size很大的時候會2.X倍  XD
→ a3785lexx:恩我最後的問題就是，每級recursive裡面都總要有一個
→ a3785lexx:暫時的位置來放東西(目前不知道要怎麼避免)
→ a3785lexx:然後就想到recursive萬一跑到幾千幾萬次...
→ a3785lexx:這樣就太吃記憶體了。   所以就把他當成參數傳下去
→ a3785lexx:然後每級都用&去接他，這樣也許可以省一點？？？
→ a3785lexx:如果運氣好可能還順便省時間？不過我不知道XDrz
推 ric2k1:幾萬次 = 1MB memory? Maybe that's not a problem.
→ flax00298:如果改成＆可行的話就會少作COPY的時間吧？
→ a3785lexx:目前&是可行可是沒有快到哪裡去XD
→ a3785lexx:其實我最原始的版本本來是沒有用&recursive的...
→ a3785lexx:而且一直涉及iterator<->BSTreeNode<T>*的轉換
→ a3785lexx:結果這兩個版本在大資料量的情況下也才差5%...o.O
→ a3785lexx:雖然小資料量的情況下會明顯增快很多就是了...
→ a3785lexx:雖然我也不知道為甚麼XD
→ a3785lexx:呵呵...剛剛作了個小實驗...
→ a3785lexx:強迫讓每一級都一定會找一次parent來
→ a3785lexx:結果並沒有變慢多少....居然差不到0.1%...
→ a3785lexx:所以其實問題根本不是出在我parent找太慢嗎XDrz...
→ a3785lexx:還是說因為我加的太突兀了所以被optimized掉了嗎XD
→ a3785lexx:倒是在剛進erase的時候就強迫他找兩次parent還比較慢
→ a3785lexx:所以說平均而言一次erase其實不會找超過兩次successor
→ a3785lexx:嗎？？
推 keyboardle:根據演算法.一次delete最多找一次succesor
→ keyboardle:因為需要找succesor的case的succesor必只有一子或沒有
→ a3785lexx:其實好像偶爾會超過一次的樣子XD？最少我的會啦XD
→ a3785lexx:不過根據實驗...平均次數其實還低於1說...
→ a3785lexx:這樣就不難理解為甚麼我把原版改變之後效率無法提升了..
→ a3785lexx:原版是效率很爛的recursive...不過既然他recursive的
→ a3785lexx:機率不高，當然效能提升有限XDrz
→ a3785lexx:不過我不能明白的就是...我在recursive的起點強迫多找
→ a3785lexx:兩次parent，結果他所需時間也沒有變三倍...(原本只會
→ a3785lexx:找一次)
→ a3785lexx:所以拖垮效能的倒底是什麼......orz
→ a3785lexx:應該不會是我find寫太爛了吧囧  insert的表現還不錯啊XD
推 keyboardle:記憶中random delete的話應該最花時間的是iterator++??
→ a3785lexx:原來是這樣！   恍然大悟！
→ a3785lexx:我一直以為random delete是叫erase(const T&)......
→ a3785lexx:畢竟用內部的find絕對會比外面用iterator還要快很多...
→ a3785lexx:感謝key大...我終於能夠把差距拉到10秒內了@@"
推 herbert570:其實用 array 實作 bst node 效率很快....
推 herbert570:只要操作數字上的運算就可以找到parent 和 child
→ herbert570:不過就是要整理樹就是了.....不然記憶體會區段錯誤...
→ a3785lexx:嗯嗯我也是這樣想...想array應該很快吧XD？
→ a3785lexx:不過我沒有array就已經程式記憶體區段錯誤了....囧
推 herbert570:array 很快是因為測資少的緣故...