作者victoret (戲言~)
看板EE_DSnP
標題[請益] 關於執行速度（效能）
時間Sun Dec 4 17:39:56 2011
關於效能方面
個人有個問題...ˊˋ
首先是拿原來的 Makefile 和 Makefile.in 做測試
執行 do2 的時間是 dlist > bst > array
然而在依照
#1A2Qnj-T 教授的說明修改了 Makefile 和 Makefile.in 之後
就變成 dlist > array > bst 了...
由於現在正要著手寫 report
想請問一下究竟要以哪個為準會比較妥當？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.4.181
1F：→ e124553423:三個都寫?重點放bst吧，另外兩個大家應該不會差太多 12/04 17:47
2F：→ victoret:問題是長在...array 比 bst 快啊ˊˋ 12/04 17:56
3F：→ djshen:我-O3 array也比較快 主要是慢在adtd -r 12/04 18:16
4F：→ djshen:不知道為什麼= = 12/04 18:19
5F：→ victoret:++ 的問題，個人 ++ 裡的判斷式換一下...就快了 30 % 12/04 19:06
6F：→ victoret:還有 call 一些要跑個半天的 function 的時候，把回傳的 12/04 19:07
7F：→ victoret:值存起來也可以省下不少時間（array 的部分） 12/04 19:07
8F：→ victoret:array 是時間變成原來的 2 / 3...超誇張@@ 12/04 19:08
9F：→ rf0914:還是資料不夠多的問題?? 我用adta -r 500000 高下立判XD 12/04 19:09
10F：→ rf0914:不過等了一個多小時... 12/04 19:10
11F：→ djshen:insert絕對是bst快 adta -r 1000000不用兩秒 array就... 12/04 19:14
12F：→ victoret:現在是想要知道修改 makefile 到底影響到什麼？？？ 12/04 19:17
13F：→ shryuhuai:是看各個指令需要花的時間吧,bst大部分都花在delete 12/04 19:21
14F：→ djshen:adtd -r 在adtTest.h的getPos array是constant time 12/04 19:22
15F：→ djshen:bst就麻煩了 看++寫得怎樣 12/04 19:22
16F：→ shryuhuai:我的bst就是在最後一個指令被array逆轉的 12/04 19:23
17F：→ victoret:很妙的，用了 O3 之後我跟同學的比較一下發現差不多 12/04 19:24
18F：→ djshen:erase的話 array要往前移 bst就看哪個case 最多也logn吧? 12/04 19:24
19F：→ victoret:但是 O3 之前...他的 2 秒...我的 6 秒...不解ˊˋ 12/04 19:24
20F：→ shryuhuai:bst在其他指令應該都會大勝array吧? 12/04 19:24
21F：推 alvin1019127:借標題問一下，老師的array是不是用binary search? 12/04 19:24
22F：→ victoret:要到那個速度應該要用 binary search 吧... 12/04 19:25
23F：→ shryuhuai:一定是吧,不然不會比dlist快那麼多 12/04 19:25
24F：→ djshen:我insert跟erase(T)的某個地方有用 12/04 19:26
25F：→ shryuhuai:dlist因為search太慢,連insert都會輸array = = 12/04 19:26
26F：推 ric2k1:回 alvin1019127: 當然囉! 12/05 00:32
27F：→ ric2k1:dlist 如同有些人的討論一樣，我改了一兩行判斷式之後 12/05 00:33
28F：→ ric2k1:也快了一些，但我懶得再上傳 ref 了 12/05 00:33
29F：推 ric2k1:推專業的五樓! 大家可以選擇 -g 或 -O3 其中一種來討論即可 12/06 14:13
30F：→ ric2k1:但如果要去探討為什麼 -g 與 -O3 之間會什麼會有差別， 12/06 14:14
31F：→ ric2k1:也是很歡迎啦! 12/06 14:14
32F：推 AlexCYW:順便問一下 如果使用有parent的BST是不是memory會比ref多 12/06 22:19
33F：→ AlexCYW:我使用adtr 100 adta -r 100000 ref是13.03M 我是13.8M 12/06 22:20
34F：→ AlexCYW:雖然看起來好像每個NODE多8B 但是我電腦是32-bit的 12/06 22:21