Was ist die Laufzeitkomplexität von Python-Liste Funktionen?

Question

Ich schreibe eine Python-Funktion, die in etwa so aussah

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

, so dass es hieß mit

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

hatte ich angenommen, dass Indexzugriff von Listen war O(1), aber war überrascht, dass für große Listen zu finden war deutlich langsamer als erwartet.

Meine Frage ist also, wie geht es Python-Listen implementiert sind, und was ist die Laufzeitkomplexität der folgenden

• Indexing: list[x]
• Popping vom Ende: list.pop()
• Popping von Anfang an: list.pop(0)
• die Erweiterung der Liste: list.append(x)

Für zusätzliche Kredite, Spleißen oder willkürliche Pops.

Answer 1

gibt es eine sehr detaillierte Tabelle auf Python-Wiki , die Ihre Frage beantwortet.

Doch in Ihrem speziellen Beispiel sollten Sie enumerate verwenden, um einen Index eines iterable innerhalb einer Schleife zu erhalten. etwa so:

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

Answer 2

Die Antwort ist "undefined". Die Python-Sprache definiert nicht die zugrunde liegende Implementierung. Hier sind einige Links zu einer Mailing-Liste Thread Sie interessiert sein könnten.

• Es ist wahr, dass Python-Listen haben als zusammenhängende realisiert Vektoren, die in den C-Implementierungen Python so weit.

• Ich sage nicht, dass das O ( ) Verhalten dieser Dinge sollte ein Geheimnis oder etwas gehalten. Aber du müssen sie im Kontext interpretieren wie Python funktioniert im Allgemeinen.

Auch der mehr Pythonic Weg, um Ihre Schleife zu schreiben, sei dies:

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

Answer 3

Listen sind in der Tat O (1) zum Index - sie als Vektor mit Proportionalzuteilung umgesetzt werden, so führen viel wie man erwarten würde. Der wahrscheinliche Grund, warum Sie diesen Code fanden langsamer als der Anruf erwartet wird, „range(0, len(some_list))“.

range() erstellt eine neue Liste mit der angegebenen Größe, so dass, wenn some_list 1.000.000 Elemente hat, werden Sie eine neue Million Artikellisten erstellen vorne. Diese Verhaltensänderungen in python3 (Bereich ist ein Iterator), der äquivalent zu der python2 xrange , oder noch besser für Ihren Fall, enumerate

Answer 4

noch nicht äußern kann, so

Wenn Sie Index und Wert müssen dann enumerate verwenden:

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

Answer 5

Python-Liste eigentlich nichts anderes als Arrays. So

Indizierung dauert O (1)

für Pop und hängt wieder soll es O (1) gemäß der Dokumentation

Überprüfen Sie folgenden Link aus für Details:

http://dustycodes.wordpress.com / 2012/03/31 / Pythons-Daten-Strukturen-Komplexität-Analyse /