为什么解包比通过索引访问更快?

40

我参考了这个问题,特别是来自@David Robinson和@mgilson的第一个答案下面的评论:Sum the second value of each tuple in a list

原始问题是要对列表中每个元组的第二个值求和:

structure = [('a', 1), ('b', 3), ('c', 2)]

首先回答:

sum(n for _, n in structure)

第二个答案:

sum(x[1] for x in structure)

根据讨论,第一个答案要快50%。

当我弄清楚第一个答案的操作(来自Perl,我搜索了一下在python中特殊的“_”变量的含义),我想知道为什么那些看起来只是纯子集任务的操作(获取每个元组的第二个元素而不是获取并绑定两个元素到变量中)却更慢?这是在Python中优化索引访问的机会缺失了吗?还是我漏掉了第二个答案需要耗费时间的操作?

2个回答

43
如果您查看Python字节码,很快就会明显地了解为什么拆包更快:
>>> import dis
>>> def unpack_or_index(t=(0, 1)):
...     _, x = t
...     x = t[1]
... 
>>> dis.dis(unpack_or_index)
  2           0 LOAD_FAST                0 (t)
              3 UNPACK_SEQUENCE          2
              6 STORE_FAST               1 (_)
              9 STORE_FAST               2 (x)

  3          12 LOAD_FAST                0 (t)
             15 LOAD_CONST               1 (1)
             18 BINARY_SUBSCR       
             19 STORE_FAST               2 (x)
             22 LOAD_CONST               0 (None)
             25 RETURN_VALUE        

元组解包操作是一个简单的字节码 (UNPACK_SEQUENCE),而索引操作必须在元组上调用一个方法 (BINARY_SUBSCR)。解包操作可以在 Python 评估循环中内联进行,而订阅调用需要查找元组对象上的函数以检索值,使用PyObject_GetItem

UNPACK_SEQUENCE 操作码源代码 特殊处理 Python 元组或列表解包,其中序列长度与参数长度完全匹配:

        if (PyTuple_CheckExact(v) &&
            PyTuple_GET_SIZE(v) == oparg) {
            PyObject **items = \
                ((PyTupleObject *)v)->ob_item;
            while (oparg--) {
                w = items[oparg];
                Py_INCREF(w);
                PUSH(w);
            }
            Py_DECREF(v);
            continue;
        } // followed by an "else if" statement for a list with similar code

上述代码访问元组的本地结构并直接检索值;无需使用诸如 PyObject_GetItem 之类的重型调用,因为这些调用必须考虑到对象可能是自定义的Python类。 BINARY_SUBSCR opcode 只针对Python的原生列表进行了优化;任何不是原生Python列表的内容都需要使用 PyObject_GetItem 调用。

3
然而,我预计BINARY_SUBSCRIPT在查找后将是非常高效的操作,而UNPACK_SEQUENCE则不是(可以看作O(1)与O(n)),并且下标操作需要少一次存储操作。实际上,您对代码的格式化可能会产生误导-两个操作使用相同数量的操作码,并且您实际上没有解释为什么拆包比下标引用更快:特别是,为什么拆包不需要通过PyObject_GetItem进行方法查找? - Konrad Rudolph
2
@KonradRudolph:扩展了。有趣的是,如果你用列表替换元组,情况可能会完全不同。 - Martijn Pieters

18

索引操作通过 __getitem__ 特殊方法实现,因此对于每个项目,必须进行函数查找和执行。这意味着对于一个包含n个项目的列表,您最终需要进行n次查找/调用。

当使用本机列表 / 元组时,解包操作不必处理上述问题; 它只需通过单个调用遍历__iter__ 方法,然后在C中解压缩生成的序列。


请明确一下:您是说解包不经过特殊方法,因此不进行方法查找吗?那么解包只适用于本地Python对象(listtuple)是吗? - Konrad Rudolph
@KonradRudolph 不是这样的 - 注意到 __iter__ 的提及。我的意思是它只需要进行一次调用,因此这个操作是 O(1),而不是像调用序列中每个元素的 __getitem__ 这样的 O(n) 操作。 - Amber
@Amber __getitem__ 必须被调用的次数与解包方法中的项数完全相同:对于 structure 中的每个项都要调用一次。而且 __iter__两种 方式中都被使用。 - Konrad Rudolph
1
@KonradRudolph:解包适用于任意序列,但元组/列表情况已被特殊处理和优化。在这种情况下,底层的C数组直接被使用。 - Martijn Pieters

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接