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