python - Pythonリスト関数の実行時の複雑さはどれくらいですか?

Question

私はこのようなPython関数を書いていました

def foo(some_list):
   for i in range(0, len(some_list)):
       bar(some_list[i], i)

で呼び出されるように

x = [0, 1, 2, 3, ... ]
foo(x)

リストのインデックスアクセスはであると想定していましたがO(1)、大きなリストの場合、これが予想よりも大幅に遅いことに驚きました。

私の質問は、Python リストがどのように実装されているか、および以下の実行時の複雑さはどのくらいかということです。

索引付け:list[x]
最後から飛び出る：list.pop()
最初からポップ：list.pop(0)
リストの拡張:list.append(x)

追加のクレジット、スプライシング、または任意のポップ用。

score 37 · Accepted Answer

あなたの質問に答えるpython wiki に非常に詳細な表があります。

ただし、特定の例enumerateでは、ループ内でイテラブルのインデックスを取得するために使用する必要があります。そのようです：

for i, item in enumerate(some_seq):
    bar(item, i)

score 8 · Accepted Answer

答えは「未定」です。Python 言語は、基礎となる実装を定義していません。興味のあるメーリングリストスレッドへのリンクを次に示します。

また、ループをより Pythonic に記述する方法は次のようになります。

def foo(some_list):
   for item in some_list:
       bar(item)

score 6 · Accepted Answer

リストは確かにインデックス付けするO（1）です-それらは比例的な過剰割り当てを持つベクトルとして実装されているので、期待どおりに実行します。このコードが予想よりも遅いと思った理由としては、「range(0, len(some_list))」の呼び出しが考えられます。

range()指定されたサイズの新しいリストを作成するため、some_listに1,000,000個のアイテムがある場合は、事前に新しい100万個のアイテムリストを作成します。この動作はpython3（範囲はイテレータ）で変更されます。これは、python2に相当するものがxrangeであるか、場合によってはさらに適切に列挙します。

score 3 · Accepted Answer

インデックスと値が必要な場合は、列挙を使用します。

for idx, item in enumerate(range(10, 100, 10)):
    print idx, item

score 1 · Accepted Answer

Python リストは、実際には配列にすぎません。したがって、

インデックス作成には O(1) かかります

pop と append の場合は、ドキュメントに従って O(1) にする必要があります

詳細については、次のリンクを参照してください。

http://dustycodes.wordpress.com/2012/03/31/pythons-data-structures-complexity-analysis/

python - Pythonリスト関数の実行時の複雑さはどれくらいですか?

5 に答える 5

Related

Reference