列表查找比元组更快? [英] List lookup faster than tuple?

问题描述

过去，当我需要在紧密循环中进行类似数组的索引查找时，我通常使用元组，因为它们通常表现出色(接近仅使用n个变量).但是，我今天决定质疑这一假设，并得出了一些令人惊讶的结果:

In the past, when I've needed array-like indexical  lookups in a tight loop, I usually use tuples, since they seem to be generally extremely performant (close to using just n-number of variables). However, I decided to question that assumption today and came up with some surprising results:

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％的时间！重复实验给出了相似的结果.拆开它们，我发现它们都是:

Tuple lookups appear to take 17% longer than list lookups! Repeated experimentation gave similar results. Disassembling each, I found them to both be:

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 s.另外，我运行时没有lambda，您知道，以防万一(请注意，该数字= 100,000,000而不是10,000,000).

For reference, a typical 10,000,000 global variable lookup/returns take 2.2s. Also, I ran it without the lambdas, y'know, just in case (note that number=100,000,000 rather than 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％的时间.这里发生了什么?对于非常紧密的循环，这实际上似乎是一个很大的差异.是什么原因造成的?

Here, the tuple lookup take 35% longer. What's going on here? For very tight loops, this actually seems like a significant discrepancy. What could be causing this?

请注意，对于分解为变量(例如x，y = t)，元组要快一些(在我的少数测试中，时间要少6％左右)，而对于使用固定数量的参数进行构造，元组要快得多(〜83 ％ 更短的时间).不要将这些结果作为一般规则；我只是进行了一些小型测试，这些测试对于大多数项目来说都是毫无意义的.

Note that for decomposition into variable (e.g. x,y=t), tuples are slightly faster (~6% in my few tests less time) and for construction from a fixed number of arguments, tuples are crazy faster(~83% less time). Don't take these results as general rules; I just performed a few minitests that are going to be meaningless for most projects.

In [169]: print(sys.version)
2.7.1 (r271:86882M, Nov 30 2010, 09:39:13) 
[GCC 4.0.1 (Apple Inc. build 5494)]

推荐答案

对于构造列表(而不是对其进行访问)而言，主要是更快的问题.

Tuples are primarily faster for constructing lists, not for accessing them.

组的访问应该稍微快一些:它们需要更少的间接访问.但是，我相信主要的好处是，在构造列表时，它们不需要第二次分配.

Tuples should be slightly faster to access: they require one less indirection. However, I believe the main benefit is that they don't require a second allocation when constructing the list.

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

The reason lists are slightly faster for lookups is because the Python engine has a special optimization for it:

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％).

With this optimization commented out, tuples are very slightly faster than lists (by about 4%).

请注意，在此处为元组添加单独的特殊情况优化并不是一个好主意. VM循环主体中的每种特殊情况都会增加代码大小，从而降低缓存一致性，这意味着每种 other 类型的查询都需要一个额外的分支.

Note that adding a separate special-case optimization for tuples here isn't necessary a good idea. Every special case like this in the main body of the VM loop increases the code size, which decreases cache consistency, and it means every other type of lookup requires an extra branch.

这篇关于列表查找比元组更快?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！