14

組み込みのPythonリストオブジェクトに関する簡単な質問。0から99までの数字のリストがあるとします。リストの最後の項目を取得し、それを他の目的に使用するプログラムを作成しています。list [99]を使用するよりもlist[-1]を使用する方が効率的ですか？言い換えれば、どちらの場合でも、Pythonはリスト全体を反復処理しますか？

ご協力いただきありがとうございます。

4

6 に答える 6

21

Pythonは、特定のインデックスを見つけるためにリストを反復処理しません。リストは連続したメモリ内の（要素へのポインタの）配列であるため、目的の要素を見つけることは常に単純な乗算と加算です。どちらかといえば、 Pythonは実際のlist[-1]インデックスを取得するために長さに負のインデックスを追加する必要があるため、少し遅くなります。（ただし、すべてがCで行われるため、著しく遅くなるとは思えません。）

于 2012-07-09T17:37:10.527 に答える
7

テストして見てみませんか？

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)

もちろん、これを数回実行するとわかるように、他の回答で指摘されている理由から、実際には（目立った）違いはありません。

于 2012-07-09T17:43:22.123 に答える
4

あなたは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では、ただしほとんどのpython2.*でも同じである必要があります。

./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番目の値を取得することを意味します。彼はその最後の値を知りません。

于 2012-07-09T17:50:16.223 に答える
3

どちらの場合も繰り返されません。list[-1]本質的にはと同じですlist[len(list) - 1]。リストは配列に基づいているため、ルックアップは一定時間です。

于 2012-07-09T17:36:51.283 に答える
2

Pythonでのリストのインデックス作成は、常にO（1）です。

時間計算量の詳細については、このリンクをたどってください

于 2012-10-04T11:19:38.253 に答える
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
于 2012-07-09T18:03:38.813 に答える