如何找出哪个嵌套for循环更好?
有人问我一个问题:在以下两种情况中,哪一项是最快的:
情况1:假设int count = 0;
for (int i = 0; i < 10; i++) { for (int j = 0; j < 5; j++) { count++; } }
情况2:假设int count = 0;
for (int i = 0; i < 5; i++) { for (int j = 0; j < 10; j++) { count++; } }
在这两个场景中,计数的最终值将为50.但我不确定哪一个会更快? 我认为CASE II更快但不确定……
如果有人能对它有所了解,那将是很棒的。 这更快,为什么?
这是我能想到的最重要的例子,你在哪里重复哪个变量
int array[n][m]; //fast for (int i=0;i
第二个是较慢的,因为你不是一个接一个地迭代内存中的位置,而是因为你一次跳过m
位置。 处理器缓存位于访问位置之后的存储位置。
好的,在我的系统上测试了这个。 通过完全优化,编译器只计数= 50,没有问题。 如果没有优化,第二个版本通常会稍微快一点,但它完全可以忽略不计。
反汇编:两个循环都有完全相同的代码,除了比较一次是100,一次是50(我稍微增加数字以允许更长的执行时间)
for(int i = 0; i< 100; i++) { 00F9140B mov dword ptr [i],0 00F91412 jmp main+5Dh (0F9141Dh) 00F91414 mov eax,dword ptr [i] 00F91417 add eax,1 00F9141A mov dword ptr [i],eax 00F9141D cmp dword ptr [i],64h 00F91421 jge main+88h (0F91448h) for(int j = 0; j< 50; j++) 00F91423 mov dword ptr [j],0 00F9142A jmp main+75h (0F91435h) 00F9142C mov eax,dword ptr [j] 00F9142F add eax,1 00F91432 mov dword ptr [j],eax 00F91435 cmp dword ptr [j],32h 00F91439 jge main+86h (0F91446h) { count++; 00F9143B mov eax,dword ptr [count] 00F9143E add eax,1 00F91441 mov dword ptr [count],eax } 00F91444 jmp main+6Ch (0F9142Ch) } 00F91446 jmp main+54h (0F91414h)
外部大循环,内部小循环和内部小循环以及外部大循环之间的唯一区别是你需要经常跳转的频率
00F91439 jge main+86h (0F91446h) to 00F91446 jmp main+54h (0F91414h)
并且循环变量的初始化:
00F91423 mov dword ptr [j],0 00F9142A jmp main+75h (0F91435h)
对于每个新循环,同时跳过下面的部分。
00F9142C mov eax,dword ptr [j] 00F9142F add eax,1 00F91432 mov dword ptr [j],eax
内循环的每次迭代的附加命令:mov,add,mov,但没有mov / jmp
初始化每个内部循环的附加命令:mov,jmp,更常见的是使JGE为true。
因此,如果你运行内循环50次,你将使JGE只实现50次,因此在那里进行50次跳跃,而内循环运行100次,你将不得不跳100次。 这是代码中的唯一差异。 在这种情况下,它几乎没有任何区别,并且大多数时候你会遇到内存访问导致速度下降比循环排序多得多。 唯一的例外:如果你知道你可以正确地订购你的循环以避免分支预测。 所以有两件事值得以这种或那种方式命令你的循环:
- 内存访问
- 分支预测
对于其他一切,影响完全可以忽略不计。
实际上,尝试优化自己以获得这些细节通常不是一个好主意,因为大多数编译器在这方面要好得多(只要算法没有改变)。
循环次数相等。
可能是第二个更快一点,因为第二个循环的初始化只发生了5次而不是10次,但我怀疑这会真正获得一些明显的变化。
最好的方法是使用分析器甚至更好:分析生成的汇编代码。
如果你真的想知道,使你的外循环成为一个具有最大循环计数(5或10)的单个参数的函数,你的内循环是一个函数,它接受一个最大内循环计数(10或5)的参数,然后编译没有任何优化,运行两百万次,并计时。
根据任何优化,您的编译器将内联函数,扩展循环,并计算count
作为优化过程的一部分。 我的猜测是,他们会完成相同数量的工作,你会看到完全相同的时间。
你真的尝试过吗?
我认为理论上案例II会稍微快一些,因为在外循环中只有一半的基于堆栈的变量创建/销毁比案例I更好,但更好(和更清晰)将是:
for(int k = 0; k < 50; k++) { count++; }
确切地说,你的例子是如此抽象,以至于答案很可能没用。 这在很大程度上取决于具体情况。