列表查找比元组更快？

在过去，当我需要在紧密循环中使用类似数组的索引查找时，我通常使用元组，因为它们通常看起来非常高效（接近仅使用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秒。另外，我在没有lambdas的情况下运行它，你知道，以防万一（注意数字= 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)]

已邀请:

2 个回复

甲车劲

元组主要更快地构建列表，而不是访问它们。元组的访问速度应该稍微快一些：它们需要少一个间接。但是，我认为主要的好处是它们在构建列表时不需要第二次分配。查找的原因列表稍快一些，因为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循环主体中的每个特殊情况都会增加代码大小，从而降低缓存一致性，这意味着每种其他类型的查找都需要额外的分支。

泻伴墓荒

与此相反，我有完全不同的建议。如果数据是 - 根据问题的性质 - 固定长度，使用元组。例子：（r，g，b） - 由问题的定义确定的三个要素。（纬度，经度） - 由问题定义修复的两个元素如果数据是 - 根据问题的性质 - 变量，请使用列表。速度不是问题。意义应该是唯一的考虑因素。

要回复问题请先登录或注册

列表查找比元组更快？

2 个回复

发起人

performance

list

tuples

python_internals

问题状态

列表查找比元组更快？

与内容相关的链接

2 个回复

发起人

performance

list

tuples

python_internals

问题状态