循环数影响效率（解释语言与编译语言？）

Question

假设你必须使用2个甚至3个循环来执行一个计算。直觉上，有人可能会认为用一个循环来做这件事更有效。我尝试了一个简单的Python示例：

import itertools
import timeit

def case1(n):
    c = 0
    for i in range(n):
        c += 1
    return c

def case2(n):
    c = 0
    for i in range(n):
        for j in range(n):
            for k in range(n):
                c += 1
    return c

print(case1(1000))
print(case2(10))

if __name__ == '__main__':
    import timeit

    print(timeit.timeit("case1(1000)", setup="from __main__ import case1", number=10000))

    print(timeit.timeit("case2(10)", setup="from __main__ import case2", number=10000))

此代码运行：

^{pr2}$

所以有效的1个循环似乎更有效率。然而，我的问题有一个稍微不同的场景，因为我需要使用数组中的值（在下面的示例中，我使用函数range进行简化）。也就是说，如果我把所有的东西都压缩成一个循环，我就必须从另一个数组的值创建一个扩展数组，这个数组的大小在2到10个元素之间。在

import itertools
import timeit

def case1(n):

    b = [i * j * k for i, j, k in itertools.product(range(n), repeat=3)]
    c = 0
    for i in range(len(b)):
        c += b[i]
    return c

def case2(n):

    c = 0
    for i in range(n):
        for j in range(n):
            for k in range(n):
                c += i*j*k
    return c

print(case1(10))
print(case2(10))

if __name__ == '__main__':
    import timeit

    print(timeit.timeit("case1(10)", setup="from __main__ import case1", number=10000))

    print(timeit.timeit("case2(10)", setup="from __main__ import case2", number=10000))

在我的计算机中，此代码运行于：

$ python3 code.py 
91125
91125
2.435348572995281
1.6435037050105166

所以这3个嵌套循环似乎更有效，因为我花了一些时间在case1中创建数组b。所以我不确定我是否以最有效的方式创建了这个数组，但抛开这一点，是否真的值得将循环压缩为一个呢？我在这里使用Python，但像C++这样的编译语言呢？在这种情况下，编译器是否会对单循环进行优化？或者另一方面，当你有多个嵌套循环时，编译器会做一些优化吗？在

Answer 1

您的案例非常简单，各种优化可能会起到很大作用。无论是numpy对于更高效的数组，也许{}对于更好的JIT优化器，或者其他各种东西。

通过dis模块查看字节码可以帮助您理解幕后发生的事情，并进行一些微优化，但通常情况下，如果您的内存访问模式对CPU有一定的可预测性，那么不管您是执行一个循环还是嵌套循环。如果不是，可能会有很大的不同。

Python有一些便宜的字节码，还有一些更贵的字节码，例如函数调用比简单的加法要贵得多。与创建新对象和其他各种东西一样。所以通常的优化是将循环移到C，这是itertools的一个好处。

一旦进入C级，通常可以归结为：避免在紧循环中使用syscalls/mallocs（），使用可预测的内存访问模式，并确保算法对缓存友好。

因此，由于内存分配和缓存访问量的原因，如果使用较大的N值，上述算法的性能可能会有很大的变化。

但对于上述具体问题，最快的方法是为函数找到一个闭合形式，为此迭代似乎是浪费，因为必须有一个更简单的公式来计算“c”的最终值。像往常一样，在进行微优化之前，首先得到最佳算法。

例如，Wolfram Alpha告诉你，你可以把两个循环替换成，可能这三个循环都有一个闭合形式，但是Alpha没有告诉我。。。

def case3(n):
    c = 0
    for j in range(n):
        c += (j* n^2 *(n+1)^2))/4
    return c

Answer 2

这就是为什么单循环函数要比它应该花费的时间更长

b = [i * j * k for i, j, k in itertools.product(range(n), repeat=3)]

只需将整个函数改为

^{pr2}$

使返回时间：

case1 : 0.965343249744
case2 : 2.28501694207