更深入地理解循环(for、while、do while、foreach、递归等)

好吧,很难解释循环背后的逻辑。

为了优化循环,编译器会为您做一些了不起的事情,所以如果您使用 while 或 for 因为编译器无论如何都会转换为汇编程序。

为了更深入地理解,您应该学习一些汇编程序,然后学习基本处理器的工作原理、它如何阅读指令以及如何处理指令。

为了改进流水线,最好将变量相同的语句放在彼此远离的地方。这样,当计算一条语句时,如果下一条语句独立于第一条语句,处理器就可以接受它并开始计算它。

例如:

a=0;
b=3;
c=5;
m=8;
i=0;
while(i<10){
a=a+b*c;
b=b*10+a;
m=m*5;
i++;
}

我们之间有依赖关系 a 和 b 这些陈述就在一起。但是我们看到了 m 和 i 独立于其他人,因此我们可以:

a=0;
b=3;
c=5;
m=8;
i=0;
while(i<10){
a=a+b*c;
m=m*5;
i++;
b=b*10+a;

}

所以当 一 正在计算,我们可以开始计算 米 和 我 . 大多数情况下,编译器会检测到这一点并自动执行(这是调用代码重新排序)。对于小循环,编译器有时会根据需要复制和粘贴循环内的代码,因为没有控制变量更快。

我的建议是,让编译器处理这些事情,把重点放在您使用的算法的成本上,最好从 O(n)! 到 o(登录) 而不是在循环中进行微观优化。

根据修改的问题更新

嗯,依赖关系必须是写/写或读/写依赖关系。如果它是读/读依赖关系,则没有问题(因为值不会更改)。看看[数据依赖项文章]。( http://en.wikipedia.org/wiki/Data_dependency )

在您的示例中,这两个代码没有区别, 米 取决于 c 和 乙 但这两个函数从未被写入,所以编译器在进入循环之前就知道它们的值。这被称为读/读依赖关系,而不是依赖关系本身。

如果你写过:

...
m=c+GetAvarage(a);
...

然后我们将有一个写/读依赖关系(我们必须写 一 然后读 一 ,所以我们必须等到 一 是计算出来的),你做的优化会很好。

但是,编译器再一次为您和其他许多事情做这个。很难说高级代码中的微优化会对汇编程序代码产生真正的影响,因为也许编译器已经为您做了这件事,或者可能正在为您重新排序代码,或者可能正在做比我们一眼就能想到的更好的上千件事。

但不管怎样,只知道地毯下的东西是如何工作的就好了:)

更新以添加一些链接 查看这些链接,进一步了解编译器可以做些什么来提高代码性能:

Loop unwinding

Dependency Analysis

Automatic parallelization

Vectorization

我将逐一解释每一个循环案例,

1。 for循环: 当你确信 某些 迭代次数然后继续 对于 循环。

2。 循环时: 当您不确定迭代次数时,继续执行while循环,或者您希望循环直到条件为false。

三。 做而不做 :这与while循环相同,但该循环至少执行一次。

尽管如此,也可以为另一个案例编写一个循环。

4。 递归 :如果您正确理解递归,递归将导致优雅的解决方案。 递归比直接向前迭代慢一点。

for和while之间没有性能差异。如果有,则可以忽略不计。

您应该编写最自然、最惯用和最易读的代码,清楚地表达您的意图。在大多数情况下,没有一个循环比另一个循环执行得更出色,以至于你会牺牲上面的任何一个循环来获得很小的速度增益。

大多数主流语言的现代编译器在优化代码方面都非常聪明,尤其能精确地定位人们应该编写的可读代码类型。代码越复杂,人类就越难理解,编译器也越难优化。

大多数编译器可以优化 tail recursion 离开,允许您递归地表达您的算法(在某些场景中这是最自然的形式),但实际上是迭代地执行它。否则,递归可能比迭代解慢,但在进行优化之前,您应该考虑所有因素。

如果一个有效的,正确的,但可能稍微慢一点的递归解决方案可以很快地被写出来,那么它通常比一个复杂的迭代解决方案更可取,这个迭代解决方案可能更快,但可能不明显是正确的和/或更难维护。

不要过早优化。

任何合适的编译器都会生成相同的代码 .

为了测试这个,我创建了一个名为 loops-f.c :

void f(int array[])
{
    for(int i=0; i<10; i++) {
        array[i] = i+1;
    }
}

和一个名为 loops-g.c :

void g(int array[])
{
    int i = 0;
    while(i<10) {
        array[i] = i+1;
        i++;
    }
}

我把文件汇编成汇编( gcc -std=c99 -S loops-f.c loops-g.c )然后我比较了生成的汇编代码( diff -u loops-f.s loops-g.s ):

--- loops-f.s   2010-08-06 10:57:11.377196516 +0300
+++ loops-g.s   2010-08-06 10:57:11.389197986 +0300
@@ -1,8 +1,8 @@
-   .file   "loops-f.c"
+   .file   "loops-g.c"
    .text
-.globl f
-   .type   f, @function
-f:
+.globl g
+   .type   g, @function
+g:
 .LFB0:
    .cfi_startproc
    pushq   %rbp
@@ -30,6 +30,6 @@
    ret
    .cfi_endproc
 .LFE0:
-   .size   f, .-f
+   .size   g, .-g
    .ident  "GCC: (GNU) 4.4.4 20100630 (Red Hat 4.4.4-10)"
    .section    .note.GNU-stack,"",@progbits

正如您所看到的,代码实际上是相同的。

循环的名称本身给出了有关用法的概念。

当你只需要执行一个操作时,不需要问任何问题,一个for循环做得很好。

如果您正在对数据结构进行迭代,并且有一个约束,比如中断条件或类似的条件,那么应该选择while或do while循环。

这只是个人偏好和编码风格的问题——首选的风格也很大程度上取决于您所使用的语言。

例如,在Python中,执行上述循环的首选方法看起来有点像:

for i in range(0, 9):
    array[i] = i + 1

(实际上,在python中,您可以在一行中完成上述操作:

array = range(1,10)

但这只是一个例子…)

在上述两种情况中,我倾向于第一种情况。

至于性能,你不太可能看到区别。

这当然取决于您使用的语言,但是请记住,任何代码中最慢的部分都是编码它的人,所以我建议为每种情况选择一个标准并坚持下去,然后当您开始更新代码时,您不必每次都考虑这个问题。

如果您试图以这样的方式节省开支,那么您要么已经以接近100%的效率运行,要么可能正在寻找错误的地方来加快代码的速度?

在Patterson和Hennessy的《计算机组织和设计:硬件/软件接口》一书中,作者将上面的循环转换为装配,并且两个循环在MIPS中具有相同的装配代码。

如果编译器在不同的汇编语句中编译这两个循环(如果它们的性能不同),则会出现差异。