python - 为什么嵌套循环的顺序之间存在性能差异？

Question

我有一个循环遍历两个列表的过程，一个相对较大，而另一个则小得多。

例子:

larger_list = list(range(15000))
smaller_list = list(range(2500))

for ll in larger_list:
    for sl in smaller_list:            
        pass

我缩小了列表的大小以测试性能，我注意到首先循环遍历哪个列表之间存在很大差异。

import timeit

larger_list = list(range(150))
smaller_list = list(range(25))


def large_then_small():
    for ll in larger_list:
        for sl in smaller_list:
            pass


def small_then_large():
    for sl in smaller_list:
        for ll in larger_list:
            pass


print('Larger -> Smaller: {}'.format(timeit.timeit(large_then_small)))
print('Smaller -> Larger: {}'.format(timeit.timeit(small_then_large)))

>>> Larger -> Smaller: 114.884992572
>>> Smaller -> Larger: 98.7751009799

乍一看，它们看起来是一样的 - 然而这两个函数之间有 16 秒的差异。

这是为什么？

Answer 1

当你反汇编你的一个函数时，你会得到:

>>> dis.dis(small_then_large)
  2           0 SETUP_LOOP              31 (to 34)
              3 LOAD_GLOBAL              0 (smaller_list)
              6 GET_ITER
        >>    7 FOR_ITER                23 (to 33)
             10 STORE_FAST               0 (sl)

  3          13 SETUP_LOOP              14 (to 30)
             16 LOAD_GLOBAL              1 (larger_list)
             19 GET_ITER
        >>   20 FOR_ITER                 6 (to 29)
             23 STORE_FAST               1 (ll)

  4          26 JUMP_ABSOLUTE           20
        >>   29 POP_BLOCK
        >>   30 JUMP_ABSOLUTE            7
        >>   33 POP_BLOCK
        >>   34 LOAD_CONST               0 (None)
             37 RETURN_VALUE
>>>

查看地址 29 和 30，看起来它们会在每次内部循环结束时执行。两个循环看起来基本一样，但这两条指令是在每次内层循环退出时执行的。内部循环中的数字较小会导致它们更频繁地执行，从而增加时间(与内部循环中的较大数字相比)。