[問題] 兩層for迴圈的效果

看板C_and_CPP作者 (環球科大扛壩子)時間7年前 (2017/05/25 12:39), 編輯推噓5(5推 0噓 11→)
留言16則, 11人參與, 最新討論串1/2 (看更多)
大家好 今天去面試主管問我一題 第一個狀況 for i=1~100 for j=1~1000000 s=s+i*j 第二個狀況 for i=1~100000 for j=1~100 s=s+i*j 哪一個比較快 我是回答第一個狀況 因為我覺得跳出迴圈回到上個迴圈比較少次 所以會比較快 主管說是正確答案 然後有解釋一番 但我有點忘記了 想請問各位大大有沒有詳盡的解釋 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.210.58 ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1495687144.A.1B0.html
→
05/25 13:41, , 1F
1000000^100=10^600 < 100^1000000=10^2000000
05/25 13:41, 1F
→
05/25 13:53, , 2F
為啥是指數
05/25 13:53, 2F
推
05/25 14:21, , 3F
兩種狀況迴圈跑不一樣多次耶 是否有一邊多一個0
05/25 14:21, 3F
→
05/25 14:55, , 4F
對抱歉少一個0，因為在捷運上急急忙忙發文沒看清楚
05/25 14:55, 4F
推
05/25 15:13, , 5F
branch prediction的問題吧
05/25 15:13, 5F
→
05/25 15:27, , 6F
實際上有很高的機率 這兩個會一樣快
05/25 15:27, 6F
→
05/25 15:28, , 7F
i 跟 j 都是 local 很容易被編譯器優化掉
05/25 15:28, 7F
→
05/25 15:29, , 8F
s 也沒被存取 基本上可能被判定為 dead code (DCE)
05/25 15:29, 8F
推
05/25 15:36, , 9F
-Ofast會直接回傳答案XD https://godbolt.org/g/da8rbt
05/25 15:36, 9F
→
05/25 16:43, , 10F
第一種會比較快可能是沒優化情況j生成毀滅次數較少
05/25 16:43, 10F
→
05/25 16:44, , 11F
但像矩陣運算等 可能會與cache access有關 效率就不一
05/25 16:44, 11F
→
05/25 16:44, , 12F
定誰好 內層loop次數少 也可能優化時直接unrolling
05/25 16:44, 12F
推
05/25 16:48, , 13F
有錯誤請糾正小弟
05/25 16:48, 13F
→
05/26 16:52, , 14F
把狀況極端化 2x1000000 跟 1000000x2 哪個比較快
05/26 16:52, 14F
→
05/28 10:43, , 15F
算一百萬個常數實在沒什麼意思
05/28 10:43, 15F
推
05/30 17:51, , 16F
branch prediction是你要的關鍵字
05/30 17:51, 16F
‣ 更多 mh2ant 的文章
文章代碼(AID): #1P9b_e6m (C_and_CPP)
‣ 更多 mh2ant 的文章
文章代碼(AID): #1P9b_e6m (C_and_CPP)