作者ric2k1 (Ric)
看板EE_DSnP
标题Re: [问题] array中-random产生数字的问题
时间Sun May 11 11:38:53 2008
: : 另外在test时
: : 若是
: : adtr 100000
: : adta -r 100000
: : 就荡在那边不动了
: : 数字比较小的话就没这个问题
: : 是因为我的insert太慢吗??
: : 能请知道的各位指点一下吗
: : 谢谢
:
: 应该是你的 insert 太慢了... 可以跟参考程式的 adtTest.dlist 比一下,
:
: 如果你比他还慢 (35 sec in my machine), 表示你的 insert 比 O(n) 还慢,
:
: 那真的是有问题, 可以用 static int + cout + debugger 来观察一下.
:
: My adtTest.array runtime < 1 sec...
:
: --
:
※ 发信站: 批踢踢实业坊(ptt.cc)
: ◆ From: 59.121.130.151
: 推 lendlicewang:谢谢教授 05/10 23:41
: 推 lendlicewang:似乎是有没有开O3的问题... 05/11 03:34
: 推 lendlicewang:请问老师的执行档有开O3吗? 05/11 03:50
: → ric2k1:嗯, 我有开 -O, 不过有差很多吗? (我想大概两倍吧?) 05/11 09:42
: 推 bnsblue:老师 我用linear search是37.5 s, 改用binary search之後 05/11 10:59
: → bnsblue:只改进到32.75.... 05/11 11:00
: → bnsblue:P.S.我跑ref档也是0.94s而已 05/11 11:01
: → ric2k1:测了一下, 有没有 -O 只差 0.02s 而已 (0.92s vs 0.94s) 05/11 11:13
: → ric2k1:你确定你写的bin search 正确吗? O(n)跟O(log n)应该差很多 05/11 11:14
: 推 bnsblue:我再检查一下XD 05/11 11:17
试了一下...
[dofile]
adtr 100000
adta -r 100000
usage
adtd -r 100000
usage
Binary search:
Opt mode : 0.92 (add) 0.89 (delete)
Debug mode: 0.94 (add) 0.90 (delete)
Linear search (改了我的 array.h):
Opt mode : 4.47 (add) 0.89 (delete)
Debug mode: 27s (add) 0.90 (delete)
1. Linear search 的确慢不少...
2. Linear search 的 opt 跟 debug mode 还差蛮多的... 这是蛮怪的.
3. Delete 都很快, 因为我直接 randomly generate positions for delete,
然後用 _data + pos 直接指到要 delete 的 iterator, 不用 find(),
所以都很快.
4. 我有用 tests/do 输出的结果比对过, output 的结果是一样的, 所以应该是没写错.
5. Memory usage 都是 0.2695 M Bytes.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 59.121.130.151
1F：推 bnsblue:为什麽linear search的结果会比dlist的快那麽多呀@@ 05/11 11:45
2F：推 timrau:100000次new是很可怕的... 05/11 13:46
3F：→ ric2k1:刚刚看了一下 code, delete 是直接 randomly delete pos, 05/11 14:26
4F：→ ric2k1:并没有 find(), 难怪那麽快... 改一下文章... 05/11 14:26
※ 编辑: ric2k1 来自: 59.121.130.151 (05/11 14:29)
5F：推 lendlicewang:delete之後不是也要做搬移的动作吗??位什麽速度差这 05/11 15:19
6F：→ lendlicewang:麽多啊?? 05/11 15:19
7F：推 bnsblue:我也想问..而且我insert现在5秒左右 可是已经用binary了 05/11 19:14
8F：→ bnsblue:还是无法像老师的一样，我想可能也是因为搬移东西的原因 05/11 19:15