作者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