为什么嵌套循环的顺序之间存在性能差异? [英] Why is there a performance difference between the order of a nested loop?

问题描述

我有一个过程遍历两个列表，一个列表相对较大，而另一个列表则较小.

I have a process that loops through two lists, one being relatively large while the other being significantly smaller.

示例:

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

for ll in larger_list:
    for sl in smaller_list:            
        pass

我按比例缩小了列表以测试性能，并且我注意到首先循环浏览哪个列表之间存在很大差异.

I scaled the sized down of the lists to test performance, and I noticed there is a decent difference between which list is looped through first.

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秒.

At first glance, they look identical - however there is 16 second difference between the two functions.

那是为什么?

推荐答案

当您反汇编其中一个函数时，会得到:

When you disassemble one of your functions you get:

>>> 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，看起来这些将在每次内部循环结束时执行.这两个循环看起来基本相同，但是每当内部循环退出时，就会执行这两个指令.在内部使用较小的数字将导致执行这些命令的频率更高，从而增加了时间(而在内部循环中使用较大的数字).

Looking at address 29 & 30, it looks like these will execute every time the inner loop ends. The two loops look basically the same, but these two instructions are executed each time the inner loop exits. Having the smaller number on the inside would cause these to be executed more often, hence increasing the time (vs the larger number on the inner loop).

这篇关于为什么嵌套循环的顺序之间存在性能差异?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！