Python列表索引效率

Question

关于内置python列表对象的快速问题.假设您有一个数字0到99的列表.您正在编写一个程序,它接受列表中的最后一项并将其用于其他目的.使用list [-1]比使用list [99]更有效吗？换句话说,在任何一种情况下,python都会遍历整个列表吗？

谢谢你的帮助.

Answer 1

Python不会遍历列表来查找特定索引.列表是连续内存中的数组(指向元素的指针),因此定位所需元素始终是一个简单的乘法和加法.如果有的话,list[-1]会稍微慢一点,因为Python需要将负索引添加到长度以获得真正的索引.(我怀疑它明显变慢了,因为无论如何都是在C中完成的.)

Answer 2

为什么不试试看？

import timeit
t=timeit.timeit('mylist[99]',setup='mylist=list(range(100))',number=10000000)
print (t)
t=timeit.timeit('mylist[-1]',setup='mylist=list(range(100))',number=10000000)
print (t)

当然,正如你可以通过运行几次看到的那样,由于其他答案中指出的原因,实际上没有(明显的)差异.

Answer 3

你可以计时：

>>> import timeit
>>> timeit.Timer('values[99]', 'values = range(100)').timeit(number = 10**7)
0.44513392448425293
>>> timeit.Timer('values[99]', 'values = range(100)').timeit(number = 10**7)
0.45273900032043457
>>> timeit.Timer('values[-1]', 'values = range(100)').timeit(number = 10**7)
0.44431495666503906
>>> timeit.Timer('values[-1]', 'values = range(100)').timeit(number = 10**7)
0.44684290885925293
>>> timeit.Timer('values[-1]', 'values = range(100)').timeit(number = 10**7)
0.44867610931396484
>>> timeit.Timer('values[-1]', 'values = range(100)').timeit(number = 10**8)
4.4455509185791016
>>> timeit.Timer('values[99]', 'values = range(100)').timeit(number = 10**8)
4.4184651374816895
>>> timeit.Timer('values[99]', 'values = range(100)').timeit(number = 10**8)
4.4276700019836426
>>> timeit.Timer('values[-1]', 'values = range(100)').timeit(number = 10**8)
4.4026989936828613
>>> timeit.Timer('values[-1]', 'values = range(100)').timeit(number = 10**8)
4.4386618137359619
>>> timeit.Timer('values[99]', 'values = range(100)').timeit(number = 10**8)
4.3991479873657227
>>> 

确实没有区别，但如果您确实想要最后一个项目values[-1]似乎是最简单/最安全的方法，因为无论列表的长度如何，只要它不是空列表，它总是会获取最后一个项目，

这会引发异常：

>>> [][-1]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: list index out of range
>>> 

换句话说，无论哪种情况，python 都会迭代整个列表吗？

在这两种情况下，python 都不会遍历列表。

我实际上很好奇 python 是否做了什么不同的事情，所以我反汇编了代码：

>>> import dis
>>> def test_0():
...     values = range(100)
...     return values[99]
...
>>> def test_1():
...     values = range(100)
...     return values[-1]
...
>>> dis.dis(test_0)
2           
    0 LOAD_GLOBAL              0 (range)
    3 LOAD_CONST               1 (100)
    6 CALL_FUNCTION            1
    9 STORE_FAST               0 (values)

3          
    12 LOAD_FAST                0 (values)
    15 LOAD_CONST               2 (99)
    18 BINARY_SUBSCR
    19 RETURN_VALUE
>>> dis.dis(test_1)
2           
    0 LOAD_GLOBAL              0 (range)
    3 LOAD_CONST               1 (100)
    6 CALL_FUNCTION            1
    9 STORE_FAST               0 (values)

3          
    12 LOAD_FAST                0 (values)
    15 LOAD_CONST               2 (-1)
    18 BINARY_SUBSCR
    19 RETURN_VALUE
>>>

嗯，看起来在指令级别，它几乎是相同的，你需要进入 CPython 实现，才能确切地了解处理负索引时发生了什么，但我认为大多数其他答案已经暗示了这一点。

$ python --version
Python 2.6.1 

出于好奇，我更深入地挖掘并发现了这一点：

在 python 2.7.1 上，但在大多数 python 2.* 上应该是相同的

./Python/ceval.c:

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);
        }
        else
            goto slow_get;
    }
    else
      slow_get:
        x = PyObject_GetItem(v, w);
    Py_DECREF(v);
    Py_DECREF(w);
    SET_TOP(x);
    if (x != NULL) continue;
    break;

请注意，if (i < 0) i += PyList_GET_SIZE(v);基本上是的，constant 在处理负指数时会产生轻微的开销。

如果您好奇， ./Include/listobject.h: #define PyList_GET_ITEM(op, i) (((PyListObject *)(op))->ob_item[i])那么它基本上是一个查找；）

虽然差异很小，如果你的目标是声明你想要最后一个值，那么这values[-1]更Pythonic /更清晰地表达了这个意图，values[99]简单地意味着如果程序员不知道它有100个值，则获取第99个值他不知道它的最后一个值。