作者ack ()
看板Programming
标题[请益] 演算法运算量 vs 执行时间
时间Tue Dec 3 02:56:52 2013
各位高手们, 小弟请教一个最近很困惑的问题
我用计量分析方式分析了两个演算法的运算量
假设这两个演算法称为A跟B方法好了
如果分析过程无误的话, 理论上可以证明方法A的运算量比B少
但奇怪的是, 用程式实作这两个演算法後, 在同一个平台上跑
方法A的执行时间都比B还要多
程式方面我已经尽量把两个方法都最佳化了(全都没有用到浮点运算,动作流程也最简化)
测试平台也试了好几种, 从windows到linux, 从cpu到gpu
结果都一样...
因为分析过程跟程式最佳化我都再三确认过没有错误
但就是找不出一个合理的解释这个诡异现像
想说请教一下有没有高手可以分享一下经验
是不是真的会有演算法的运算量跟执行时间为反比的情况发生?
可能是由甚麽原因造成的呢?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 111.243.12.103
1F：推 rebaudiana:cache存取速度, 单一运算的指令周期 42.74.8.15 12/03 07:33
2F：→ rebaudiana:不一定一样啊 42.74.8.15 12/03 07:33
3F：推 moremusic:运算的次数不够多? 27.105.100.16 12/03 14:47
4F：推 bxxl:有可能是data dependency,造成pipeline stall118.160.233.164 12/03 17:31
5F：→ bxxl:有看过compile出来的assembly code吗?118.160.233.164 12/03 17:35
6F：推 bxxl:还有应该要先自己做一下校正,你估计的运算数118.160.233.164 12/03 17:38
7F：→ bxxl:跟assembly code的指令数, 跟实际跑的cycle数118.160.233.164 12/03 17:38
8F：→ bxxl:这三者的一致性如何.118.160.233.164 12/03 17:39
9F：推 jackace:不管是code cache还是data cache都有影响 1.169.172.164 12/03 18:54
10F：→ jackace:两者使用到的code,stack,heap size为何? 1.169.172.164 12/03 18:55
11F：推 janice001:有时候data n不够大 复杂度前面被省略 123.195.90.78 12/03 22:03
12F：→ janice001:的常数 就会有影响 123.195.90.78 12/03 22:03
13F：推 plover:自己耍笨 61.231.1.6 12/08 02:32