PTT數位生活區 / Programming

[請益] 演算法運算量 vs 執行時間

看板Programming作者時間11年前 (2013/12/03 02:56), 編輯推噓7(7推 0噓 6→)
留言13則, 6人參與, 最新討論串1/1
各位高手們, 小弟請教一個最近很困惑的問題 我用計量分析方式分析了兩個演算法的運算量 假設這兩個演算法稱為A跟B方法好了 如果分析過程無誤的話, 理論上可以證明方法A的運算量比B少 但奇怪的是, 用程式實作這兩個演算法後, 在同一個平台上跑 方法A的執行時間都比B還要多 程式方面我已經盡量把兩個方法都最佳化了(全都沒有用到浮點運算,動作流程也最簡化) 測試平台也試了好幾種, 從windows到linux, 從cpu到gpu 結果都一樣... 因為分析過程跟程式最佳化我都再三確認過沒有錯誤 但就是找不出一個合理的解釋這個詭異現像 想說請教一下有沒有高手可以分享一下經驗 是不是真的會有演算法的運算量跟執行時間為反比的情況發生? 可能是由甚麼原因造成的呢? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 111.243.12.103
推
12/03 07:33, , 1F
cache存取速度, 單一運算的指令週期
12/03 07:33, 1F
→
12/03 07:33, , 2F
不一定一樣啊
12/03 07:33, 2F
推
12/03 14:47, , 3F
運算的次數不夠多?
12/03 14:47, 3F
推
12/03 17:31, , 4F
有可能是data dependency,造成pipeline stall
12/03 17:31, 4F
→
12/03 17:35, , 5F
有看過compile出來的assembly code嗎?
12/03 17:35, 5F
推
12/03 17:38, , 6F
還有應該要先自己做一下校正,你估計的運算數
12/03 17:38, 6F
→
12/03 17:38, , 7F
跟assembly code的指令數, 跟實際跑的cycle數
12/03 17:38, 7F
→
12/03 17:39, , 8F
這三者的一致性如何.
12/03 17:39, 8F
推
12/03 18:54, , 9F
不管是code cache還是data cache都有影響
12/03 18:54, 9F
→
12/03 18:55, , 10F
兩者使用到的code,stack,heap size為何?
12/03 18:55, 10F
推
12/03 22:03, , 11F
有時候data n不夠大 複雜度前面被省略
12/03 22:03, 11F
→
12/03 22:03, , 12F
的常數 就會有影響
12/03 22:03, 12F
推
12/08 02:32, , 13F
自己耍笨
12/08 02:32, 13F
‣ 更多 ack 的文章
文章代碼(AID): #1IdDVttH (Programming)
Programming 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 ack 的文章
文章代碼(AID): #1IdDVttH (Programming)