评估嵌套“for”迭代的成本

Question

假设我必须执行由五个嵌套的for循环组成的代码。我们打电话给他们：

• A- 10次迭代(元素)
• B- 15次迭代(元素)
• C-16迭代(元素)
• D- 20次迭代(元素)
• E-100次迭代(元素)

当我按这个顺序循环它们时，有什么区别吗？

A(C(D(E()

和

E(D(C(B(A()

或者不同的循环顺序是最优的？

我的问题是语言独立。我想知道如何评估这段代码的成本，编写最优(快速)的代码。

根据循环大小的顺序，调用(迭代)成本是否有任何不同？

从哪里开始寻找解决办法，了解更多这类问题呢？

Answer 1

是的，是有区别的。考虑选择循环顺序，这使内存访问缓存友好。如果您有一个在循环中访问的多维数组，则应该按照连续访问访问相邻内存位置的顺序来访问它。

然而，完全回答你的问题是不可能的，因为这取决于你在循环中做什么。如果它不是多维数组的内存访问，那么前面的答案就不适用了。

我建议采用基准的方法。每次您需要嵌套for循环时，都会对哪个顺序进行基准测试，从而获得最佳性能。实际上，这很简单，尽管对于5循环，您有5！= 120种可能的订单。然而，我认为5个嵌套循环不是一个典型的用例，在更典型的情况下，例如3或4个循环，基准测试的方法是可行的。

Answer 2

考虑到有近200亿次通过内部循环，我怀疑juhist关于缓存友好数组访问的评论是否相关--很不可能涉及到一个5D，200亿个元素数组。但是，有可能涉及较小的数组，其中缓存效率仍然可以帮助您。

我要找的最重要的事情是如何修剪这个任务的一部分。不仅不需要运行循环，还可以在某些外部循环中计算值，而不是在更深的嵌套级别上反复重新计算。寻找甚至部分的表情可以抽出。对任何循环变量的引用都要非常谨慎，其级别要高于执行引用的代码。

如果这些优化都不可能的话，我会把它们按顺序排列--虽然顺序对内环运行的次数没有影响，但对循环本身运行次数的影响很小--交换A和E意味着另一个20亿循环的设置。