作者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/cn.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