简洁的优化技巧:减少嵌套循环中的跳转次数
简洁的优化技巧:减少嵌套循环中的跳转次数
通过重新排序嵌套循环，你可以很容易地获得更高效的代码，也就是说，代码跳转更少。最初的想法归功于史蒂夫·麦康奈尔写的《代码完整》,但我打算用数学进一步扩展它…
该书中的示例比较了同一嵌套 for 循环的这两个版本:
int a, b;
for (a = 0; a < 10; a++)
for (b = 0; b < 500; b++)
printf("hi");和
int a, b;
for (b = 0; b < 500; b++)
for (a = 0; a < 10; a++)
printf("hi");你很容易看到第一个例子跳了 10 + 10500 = 5010 次，第二个例子:500 + 50010 = 5500 但是两个例子循环的次数是一样的。这意味着即使它们完成了同样的事情，第一个嵌套循环还是要快一点。但是到底快了多少呢？我们能计算一下吗？
计算可能的效率增益
首先，我们假设 X 和 Y 是两个自然数。例如，我们有两个循环。A 循环:
int a, b;
for (a = 0; a < X; a++)
for (b = 0; b < Y; b++)
printf("hi");B 循环:
int a, b;
for (b = 0; b < Y; b++)
for (a = 0; a < X; a++)
printf("hi");A 循环循环 X + X * Y 次，而第二循环循环Y+**X***Y次。B 回路和 A 回路的区别是 Y - X 。如果 X > Y 那么差值为负，如果 X == Y 那么差值为零，如果 X < Y 那么差值为正。这意味着，如果 X < Y ，那么我们在 A 循环中执行的 Y - X 跳转指令比在 B 循环中少。
通过检查原始示例，您可以看到这确实是真的。在原来的例子中 X = 10， Y = 500。 X < Y 为真， Y - X 为 490。第一个循环循环 5010 次，而第二个循环循环 5500 次。两者相差 490 也就是 Y - X ！
总之，你可以说 X 和 Y 之间的差异越大，通过重新排序循环，在 Y 之前的 for 循环中使用较小的数字 X ，你就可以获得更多的效率。
更深的嵌套循环呢？
对于更深层次的嵌套循环，我们可以继续同样的推理，但让我们这样来描述这个问题:我们需要证明像a+a*b+*ab*c这样的和是最小的，当且仅当是自然数我的证明将类似于数学归纳法。我们之前已经确立了b+*bc在 b < c 时较低。所以我们可以这样重组求和:a+a(b+bc)。我们已经知道了圆括号:为了使总和最小， b 必须小于 c ，或者换句话说， b < c. 显然可以看出 a 必须尽可能小，以使总和最小。这意味着 a 必须低于 b 和 c 。因此，我们得到当 a<b<c时，和最小。可以将这个相同的逻辑扩展到a+a*b+*abc+abcd等等。**
摘要
规则是这样的:当编写嵌套循环时，确保变化最大的变量在最内层循环中，而变化最小的变量在最外层循环中。如果循环数很大，这将显著减少跳转次数。
如果您喜欢该内容，请按心形图标。它鼓励我写更多这样的东西。另外，如果你在我的推理中发现任何错误，请评论。
**
**
