大家好
今天去面試主管問我一題
第一個狀況
for i=1~100
for j=1~1000000
s=s+i*j
第二個狀況
for i=1~100000
for j=1~100
s=s+i*j
哪一個比較快
我是回答第一個狀況
因為我覺得跳出迴圈回到上個迴圈比較少次
所以會比較快
主管說是正確答案
然後有解釋一番
但我有點忘記了
想請問各位大大有沒有詳盡的解釋
謝謝

1000000^100=10^600 < 100^1000000=10^2000000

為啥是指數

兩種狀況迴圈跑不一樣多次耶 是否有一邊多一個0

對抱歉少一個0，因為在捷運上急急忙忙發文沒看清楚

branch prediction的問題吧

實際上有很高的機率 這兩個會一樣快i 跟 j 都是 local 很容易被編譯器優化掉s 也沒被存取 基本上可能被判定為 dead code (DCE)

-Ofast會直接回傳答案XD https://godbolt.org/g/da8rbt

第一種會比較快可能是沒優化情況j生成毀滅次數較少但像矩陣運算等 可能會與cache access有關 效率就不一定誰好 內層loop次數少 也可能優化時直接unrolling有錯誤請糾正小弟

把狀況極端化 2x1000000 跟 1000000x2 哪個比較快

算一百萬個常數實在沒什麼意思

branch prediction是你要的關鍵字