python - 为什么嵌套循环比扁平循环执行得快得多？

Question

更新

抱歉各位，但之前的数字是不准确的。当我测试之前的代码时，我使用了 tqdm当可迭代对象很长时，查看预期的时间和函数会损害性能。所以我得到 18.22s，这是 2.43s 的 9 倍。

然而，结论是一致的:嵌套循环要快得多。当迭代时间为 100^5 时，差异显着:321.49 vs 210.05。它们之间大约有 1.53 倍的差距。一般来说，我们不会面临这种长迭代，我只是想知道异常情况的原因。


我的 python 版本是 3.7.3。我使用 13 英寸 MacBookPro2019 和 2.4 GHz Intel Core i5。操作系统为 macOS Mojave 10.14.6

我在python中发现了一个奇怪的情况，如下所示:

import time

start = time.time()
# flattened loop
for i in range(100**4):
    pass
print(time.time() - start) # 18.22(Wrong! Should be 3.09)

# nested loop
start = time.time()
for i in range(100):
    for j in range(100):
        for k in range(100):
            for l in range(100):
                pass
print(time.time() - start) # 2.43

上述两种循环具有相同的迭代次数。然而，嵌套循环(2.43 秒)的运行速度比扁平循环(18.22 秒)快得多。随着迭代时间的增加，差异更大。锄头会发生这种情况吗？

Answer 1

首先，这不是衡量代码执行的可靠方法。让我们考虑一下这段代码(在 IPython 中运行)，它不包括循环中的功率计算，并且有一些计算只是为了确保它不能被“优化”到“请什么都不做”。

def flattened_loop(n):
    x = 0
    for i in range(n):
        x += 1
    return x


def nested4_loop(n):
    x = 0
    for i in range(n):
        for j in range(n):
            for k in range(n):
                for l in range(n):
                    x += 1
    return x


print(f'{"n":>4s}  {"n ** 4":>16s}  {"flattened":>18s}  {"nested4":>18s}')
for n in range(10, 120, 10):
    t1 = %timeit -q -o flattened_loop(n)
    t2 = %timeit -q -o nested4_loop(n)
    print(f'{n:4}  {n**4:16}  {t1.best * 1e3:15.3f} ms  {t2.best * 1e3:15.3f} ms')

   n            n ** 4           flattened             nested4
  10             10000            0.526 ms            0.653 ms
  20            160000            8.561 ms            8.459 ms
  30            810000           43.077 ms           39.417 ms
  40           2560000          136.709 ms          121.422 ms
  50           6250000          331.748 ms          291.132 ms
  60          12960000          698.014 ms          599.228 ms
  70          24010000         1280.681 ms         1081.062 ms
  80          40960000         2187.500 ms         1826.629 ms
  90          65610000         3500.463 ms         2942.909 ms
 100         100000000         5349.721 ms         4437.965 ms
 110         146410000         7835.733 ms         6474.588 ms

这表明差异确实存在，并且越大 n越大。 .

第一个运行更多字节码吗？不。我们可以通过 dis 清楚地看到这一点。 :

flattened_loop()

import dis


dis.dis(flattened_loop)

  2           0 LOAD_CONST               1 (0)
              2 STORE_FAST               1 (x)

  3           4 SETUP_LOOP              24 (to 30)
              6 LOAD_GLOBAL              0 (range)
              8 LOAD_FAST                0 (n)
             10 CALL_FUNCTION            1
             12 GET_ITER
        >>   14 FOR_ITER                12 (to 28)
             16 STORE_FAST               2 (i)

  4          18 LOAD_FAST                1 (x)
             20 LOAD_CONST               2 (1)
             22 INPLACE_ADD
             24 STORE_FAST               1 (x)
             26 JUMP_ABSOLUTE           14
        >>   28 POP_BLOCK

  5     >>   30 LOAD_FAST                1 (x)
             32 RETURN_VALUE

nested4_loop()

dis.dis(nested4_loop)

  9           0 LOAD_CONST               1 (0)
              2 STORE_FAST               1 (x)

 10           4 SETUP_LOOP              78 (to 84)
              6 LOAD_GLOBAL              0 (range)
              8 LOAD_FAST                0 (n)
             10 CALL_FUNCTION            1
             12 GET_ITER
        >>   14 FOR_ITER                66 (to 82)
             16 STORE_FAST               2 (i)

 11          18 SETUP_LOOP              60 (to 80)
             20 LOAD_GLOBAL              0 (range)
             22 LOAD_FAST                0 (n)
             24 CALL_FUNCTION            1
             26 GET_ITER
        >>   28 FOR_ITER                48 (to 78)
             30 STORE_FAST               3 (j)

 12          32 SETUP_LOOP              42 (to 76)
             34 LOAD_GLOBAL              0 (range)
             36 LOAD_FAST                0 (n)
             38 CALL_FUNCTION            1
             40 GET_ITER
        >>   42 FOR_ITER                30 (to 74)
             44 STORE_FAST               4 (k)

 13          46 SETUP_LOOP              24 (to 72)
             48 LOAD_GLOBAL              0 (range)
             50 LOAD_FAST                0 (n)
             52 CALL_FUNCTION            1
             54 GET_ITER
        >>   56 FOR_ITER                12 (to 70)
             58 STORE_FAST               5 (l)

 14          60 LOAD_FAST                1 (x)
             62 LOAD_CONST               2 (1)
             64 INPLACE_ADD
             66 STORE_FAST               1 (x)
             68 JUMP_ABSOLUTE           56
        >>   70 POP_BLOCK
        >>   72 JUMP_ABSOLUTE           42
        >>   74 POP_BLOCK
        >>   76 JUMP_ABSOLUTE           28
        >>   78 POP_BLOCK
        >>   80 JUMP_ABSOLUTE           14
        >>   82 POP_BLOCK

 15     >>   84 LOAD_FAST                1 (x)
             86 RETURN_VALUE

单个循环中的数字是否变得太大？不。

import sys


print([(n, sys.getsizeof(n), n ** 4, sys.getsizeof(n ** 4)) for n in (10, 110)])
# [(10, 28, 10000, 28), (110, 28, 146410000, 28)]

电源操作(不是在我的代码中计时，而是在您的代码中计时)是否解释了时间差异(仅计时一次，因为常量计算被缓存在 Python 中)？不。

%timeit -r1 -n1 100 ** 4
# loop, best of 1: 708 ns per loop

那么，发生了什么？

在这一点上，这只是猜测，但是，鉴于我们已经排除了至少一些潜在的候选者，我相信这是由于嵌套版本中正在发生的一些缓存机制。
这种缓存可能是为了加速众所周知的相对缓慢的显式循环。

如果我们用 Numba 编译重复相同的测试(其中循环被取消，即在没有 Python 所需的样板文件以确保其动态性的情况下执行)，我们实际上得到:

import numba as nb


@nb.jit
def flattened_loop_nb(n):
    x = 0
    for i in range(n):
        x += 1
    return x


@nb.jit
def nested4_loop_nb(n):
    x = 0
    for i in range(n):
        for j in range(n):
            for k in range(n):
                for l in range(n):
                    x += 1
    return x


flattened_loop_nb(100)  # trigger compilation
nested4_loop_nb(100)  # trigger compilation


print(f'{"n":>4s}  {"n ** 4":>16s}  {"flattened":>18s}  {"nested4":>18s}')
for n in range(10, 120, 10):
    m = n ** 4
    t1 = %timeit -q -o flattened_loop_nb(m)
    t2 = %timeit -q -o nested4_loop_nb(n)
    print(f'{n:4}  {n**4:16}  {t1.best * 1e6:15.3f} µs  {t2.best * 1e6:15.3f} µs')

   n            n ** 4           flattened             nested4
  10             10000            0.195 µs            0.199 µs
  20            160000            0.196 µs            0.201 µs
  30            810000            0.196 µs            0.200 µs
  40           2560000            0.195 µs            0.197 µs
  50           6250000            0.193 µs            0.199 µs
  60          12960000            0.195 µs            0.199 µs
  70          24010000            0.197 µs            0.200 µs
  80          40960000            0.195 µs            0.199 µs
  90          65610000            0.194 µs            0.197 µs
 100         100000000            0.195 µs            0.199 µs
 110         146410000            0.194 µs            0.199 µs

嵌套循环的执行速度稍慢(但很大程度上独立于 n )(如预期)。