python - 循环的运行时间分析

考虑以下循环：

def func1(xs, ys, zs):
    for x in xs:
        for y in ys:
            pass

        for z in zs:
            pass

运行时间应该取size of xs * (size of ys + size of zs)，可以用big-o表示法写成O(X) * (O(Y) + O(Z))。

def func2(xs, ys, zs):
    for y in ys:
        for x in xs:
            pass

    for z in zs:
        for x in xs:
            pass

这个函数的运行时间应该是size of ys * size of xs + size of zs * size of xs在big-o，O(Y) * O(X) + O(Z) * O(X)中。
问题是，这些运行时间分析是否正确如果是，这些函数的运行时间是否相等因为从算术x * (y + z) = x * y + x * z。
从ipython的%timeit函数得到的结果显示我似乎错了。

In [8]: ys1 = range(1, 500)

In [9]: zs1 = range(1, 1000)

In [11]: xs1 = range(1, 1000000)

In [12]: %timeit func1(xs1, ys1, zs1)
1 loop, best of 3: 15.7 s per loop

In [13]: %timeit func2(xs1, ys1, zs1)
1 loop, best of 3: 19.1 s per loop

想知道我的分析有什么问题。谢谢。

最佳答案

您所测量的是for循环本身执行所需的时间，而不是循环中的虚语句。
当循环的结构如下所示时：

for x in xs:
    for y in ys:
        pass

    for z in zs:
        pass

考虑每个列表迭代多少次：
xs从外部循环迭代一次
ys在内部循环中迭代X次
zs在内部循环中迭代X次
所以总的迭代次数是X * (1 + Y + Z)展开到X + XY + XZ
其中，pass语句执行的次数是X * (Y+Z)或XY + XZ，这与总迭代次数不同。
如果循环的结构是这样的：

for y in ys:
    for x in xs:
        pass

for z in zs:
    for x in xs:
        pass

ys从第一个外循环迭代一次
xs在第一个内环中迭代Y次
zs从第二个外循环迭代一次
xs在第二个内环中迭代Z次
这意味着迭代的总数是Y*(1+X) + Z*(1 + X)，它扩展到XY + XZ + Y + Z，这与第一个方程大不相同。
但是，执行的pass语句的数目是相同的：XY + XZ
因此，基本上：实际执行的语句数量是相同的，但是对于第二个示例，迭代次数（获取列表的下一个元素）通常更大，并且由于pass花费的时间比for循环开销少，因此后者是您实际测量的。

关于python - 循环的运行时间分析，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/39089761/