Python列表索引效率

Question

Python列表索引效率

15

关于 Python 中内置的列表对象，有一个简单的问题。假设您有一个列表包含数字 0-99。您正在编写一个程序，需要获取列表中最后一项并将其用于某些其他目的。使用 list[-1] 比使用 list[99] 更有效吗？换句话说，在任一情况下，Python 是否会迭代整个列表？

谢谢您的帮助。

- Madison May

5

Python的list是进行随机访问的最有效方法。我怀疑你无法测量这两种方法之间的差异。 - Mark Ransom

7

随机访问，时间复杂度为 O(1)，不需要迭代。 - David Heffernan

7个回答

8

为什么不试一试呢？

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)

当然，通过运行几次，你会发现其他答案中指出的原因，实际上并没有（显著的）区别。

- mgilson

6

你可以使用timeit：

>>> 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);，所以基本上处理负索引时有轻微的常数开销。

如果你好奇的话， ./Include/listobject.h: #define PyList_GET_ITEM(op, i) (((PyListObject *)(op))->ob_item[i])，所以这基本上是一个查找 ;)

尽管差异很小，如果你的目标是声明你想要最后一个值，那么values[-1]更符合Python风格/更清晰地表达了这个意图，values[99]只是表示获取第99个值，如果程序员不知道它有100个值，那么他就不知道它是最后一个值。

- Samy Vilar

1

只要不是空列表即可。公平地说：lst[99] 也会抛出那个错误 :D - poke

1

@poke 哈哈，是的，但我希望原帖作者已经意识到了 :) 我只是在明确表达，虽然可能有点过了... - Samy Vilar

感谢详细的回复，samy.vilar :) 这是对幕后发生的事情的一些不错的见解。我得记住 dis 模块以备将来使用。 - Madison May

4

在这两种情况下它都不进行迭代。list[-1] 本质上等同于 list[len(list) - 1]。列表由数组支持，因此查找是常数时间的。

- Laurence Gonsalves

3

在Python中，列表索引始终为O(1)。

有关时间复杂度的更多详细信息，请参阅此链接

- Somesh

1

一个简单的timeit测试结果显示，负索引略微慢一些，但时间几乎相等。

lis=list(xrange(10000000))
def f1():
    a,b,c,d,e=lis[-1],lis[-2],lis[-3],lis[-4],lis[-5]    

def f2():
    a,b,c,d,e=lis[0],lis[1],lis[2],lis[3],lis[4]

if __name__=="__main__":
    from timeit import Timer
    t = Timer("f1()", "from __main__ import f1")
    print t.timeit()
    t = Timer("f2()", "from __main__ import f2")
    print t.timeit()

输出：

0.878027235305
0.845932094722

- Ashwini Chaudhary

0

我的机器上，mylist[-1]比mylist[99]慢大约30%至45%。

>>> def test():
...     t99=timeit.timeit('mylist[99]',setup='mylist=list(range(100))',number=10000000)
...     t_1=timeit.timeit('mylist[-1]',setup='mylist=list(range(100))',number=10000000)
...     return (t_1, t99, (t_1-t99)*100/t99)
... 
>>> test()
(0.21327159996144474, 0.13456149981357157, 58.49377441312871)
>>> test()
(0.17166510014794767, 0.13119220011867583, 30.850081020563916)
>>> test()
(0.19142579985782504, 0.13216119981370866, 44.842661936827426)
>>> test()
(0.1880386001430452, 0.1329137000720948, 41.47420472159728)
>>> test()
(0.18617470003664494, 0.1398134999908507, 33.159315837761085)
>>> test()
(0.17610100004822016, 0.1407316999975592, 25.13243288560744)
>>> test()
(0.19496860005892813, 0.14028189983218908, 38.983432853531)
>>> test()
(0.19262430001981556, 0.13199010002426803, 45.938445371584066)
>>>

- Pengbert Wu

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kindall · Accepted Answer

Python不会通过迭代列表来查找特定的索引。列表是在连续的内存中的数组（指向元素的指针），因此定位所需的元素始终只需要进行简单的乘法和加法运算。如果有什么区别的话，list[-1] 会稍微慢一些，因为Python需要将负索引与长度相加以获取 真正的 索引。（然而，我怀疑这个差异并不明显，因为所有这些都是在 C 中完成的。）