作者mh2ant (環球科大扛壩子)
看板C_and_CPP
標題[問題] 兩層for迴圈的效果
時間Thu May 25 12:39:02 2017
大家好
今天去面試主管問我一題
第一個狀況
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://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1495687144.A.1B0.html
1F:→ andrenvq57: 1000000^100=10^600 < 100^1000000=10^2000000 05/25 13:41
2F:→ moebear: 為啥是指數 05/25 13:53
3F:推 libertyleave: 兩種狀況迴圈跑不一樣多次耶 是否有一邊多一個0 05/25 14:21
4F:→ mh2ant: 對抱歉少一個0,因為在捷運上急急忙忙發文沒看清楚 05/25 14:55
5F:推 kokal: branch prediction的問題吧 05/25 15:13
6F:→ Hazukashiine: 實際上有很高的機率 這兩個會一樣快 05/25 15:27
7F:→ Hazukashiine: i 跟 j 都是 local 很容易被編譯器優化掉 05/25 15:28
8F:→ Hazukashiine: s 也沒被存取 基本上可能被判定為 dead code (DCE) 05/25 15:29
10F:→ ersfw4418: 第一種會比較快可能是沒優化情況j生成毀滅次數較少 05/25 16:43
11F:→ ersfw4418: 但像矩陣運算等 可能會與cache access有關 效率就不一 05/25 16:44
12F:→ ersfw4418: 定誰好 內層loop次數少 也可能優化時直接unrolling 05/25 16:44
13F:推 ersfw4418: 有錯誤請糾正小弟 05/25 16:48
14F:→ feeya: 把狀況極端化 2x1000000 跟 1000000x2 哪個比較快 05/26 16:52
15F:→ MOONRAKER: 算一百萬個常數實在沒什麼意思 05/28 10:43
16F:推 friendever: branch prediction是你要的關鍵字 05/30 17:51