4

假设您必须使用 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))

此代码运行：

$ python3 code.py 
1000
1000
0.8281264099932741
1.04944919400441

因此，有效地 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 个嵌套循环更有效，因为我花了一些时间b在case1. 所以我不确定我是否以最有效的方式创建这个数组，但撇开它不谈，它真的可以将循环折叠成一个循环吗？我在这里使用 Python，但是像 C++ 这样的编译语言呢？在这种情况下，编译器是否会做一些事情来优化单循环？或者另一方面，当您有多个嵌套循环时，编译器是否会进行一些优化？

4

2 回答 2

2

这就是为什么单循环功能比它应该花费的时间更长的原因

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

只需将整个功能更改为

def case1(n, b):
    c = 0
    for i in range(len(b)):
        c += b[i]
    return c

使 timeit 返回：

case1 : 0.965343249744
case2 : 2.28501694207
于 2015-06-07T18:07:41.573 回答
2

您的案例很简单，各种优化可能会做很多事情。无论numpy是更高效的数组，可能pypy是更好的 JIT 优化器，还是其他各种东西。

通过模块查看字节码dis可以帮助您了解幕后发生的事情并进行一些微优化，但总的来说，如果您的内存访问模式对于中央处理器。如果不是，它可能会大不相同。

Python 有一些便宜的字节码和其他更昂贵的字节码，例如函数调用比简单的添加要昂贵得多。与创建新对象和其他各种事物相同。itertools所以通常的优化是将循环移动到 C，这是有时的好处之一。

一旦你处于 C 级别，它通常归结为：避免紧密循环中的系统调用/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
于 2015-06-07T18:40:14.337 回答