列表查找比元组更快?

问题描述 投票:0回答:3

过去,当我需要在紧密循环中进行类似数组的索引查找时,我通常使用元组,因为它们通常看起来性能非常好(接近于仅使用 n 个变量)。然而,我今天决定质疑这个假设,并得出了一些令人惊讶的结果:

In [102]: l = range(1000)
In [103]: t = tuple(range(1000))
In [107]: timeit(lambda : l[500], number = 10000000)
Out[107]: 2.465047836303711
In [108]: timeit(lambda : t[500], number = 10000000)
Out[108]: 2.8896381855010986

元组查找似乎比列表查找花费的时间长 17%!重复实验得到了相似的结果。拆开来看,我发现它们都是:

In [101]: dis.dis(lambda : l[5])
  1           0 LOAD_GLOBAL              0 (l)
              3 LOAD_CONST               1 (5)
              6 BINARY_SUBSCR       
              7 RETURN_VALUE    

作为参考,典型的 10,000,000 个全局变量查找/返回需要 2.2 秒。另外,我在没有 lambda 的情况下运行了它,你知道,以防万一(请注意,数字 = 100,000,000 而不是 10,000,000)。

In [126]: timeit('t[500]', 't=range(1000)', number=100000000)
Out[126]: 6.972800970077515
In [127]: timeit('t[500]', 't=tuple(range(1000))', number=100000000)
Out[127]: 9.411366939544678

这里,元组查找花费的时间延长了 35%。这里发生了什么?对于非常紧密的循环,这实际上看起来是一个很大的差异。可能是什么原因造成的?

请注意,对于分解为变量(例如 x,y=t),元组稍微快一些(在我的几次测试中,节省了大约 6% 的时间),并且对于从固定数量的参数进行构造,元组速度更快(大约少了 83%)时间)。不要将这些结果视为一般规则;我只是进行了一些小型测试,这对于大多数项目来说毫无意义。

In [169]: print(sys.version)
2.7.1 (r271:86882M, Nov 30 2010, 09:39:13) 
[GCC 4.0.1 (Apple Inc. build 5494)]
python performance list tuples python-internals
3个回答
24
投票

元组主要用于构造列表,而不是访问它们。

元组的访问速度应该稍微快一些:它们需要少一个间接。然而,我相信主要的好处是它们在构建列表时不需要第二次分配。

列表查找速度稍快的原因是 Python 引擎对其进行了特殊优化:

case BINARY_SUBSCR:
    w = POP();
    v = TOP();
    if (PyList_CheckExact(v) && PyInt_CheckExact(w)) {
        /* INLINE: list[int] */
        Py_ssize_t i = PyInt_AsSsize_t(w);
        if (i < 0)
            i += PyList_GET_SIZE(v);
        if (i >= 0 && i < PyList_GET_SIZE(v)) {
            x = PyList_GET_ITEM(v, i);
            Py_INCREF(x);
        }

注释掉此优化后,元组比列表稍微快一点(大约快 4%)。

请注意,在这里为元组添加单独的特殊情况优化并不是一个好主意。 VM 循环主体中的每个特殊情况都会增加代码大小,从而降低缓存一致性,这意味着每个“其他”类型的查找都需要一个额外的分支。


12
投票

如果数据(根据问题的性质)长度是固定的,请使用元组。

示例:

( r, g, b ) - 三个元素,由问题的定义确定。
  • ( 纬度, 经度 ) - 两个元素,由问题定义固定
  • 如果数据(根据问题的性质)是变量,请使用列表。

速度

不是

问题。

含义

应该是唯一的考虑因素。


0
投票
© www.soinside.com 2019 - 2024. All rights reserved.