Kosten für die len () -Funktion

Antworten:

341

Es ist O (1) (konstante Zeit, nicht abhängig von der tatsächlichen Länge des Elements - sehr schnell) für jeden Typ, den Sie erwähnt haben, plus setund andere wie array.array.

Alex Martelli
quelle
17
Danke für die hilfreiche Antwort! Gibt es native Typen, bei denen dies nicht der Fall ist?
Mvanveen
141

Das Aufrufen von len () für diese Datentypen ist O (1) in CPython , der am häufigsten verwendeten Implementierung der Python-Sprache. Hier ist ein Link zu einer Tabelle, die die algorithmische Komplexität vieler verschiedener Funktionen in CPython bereitstellt:

TimeComplexity Python-Wiki-Seite

James Thompson
quelle
84

Alle diese Objekte verfolgen ihre eigene Länge. Die Zeit zum Extrahieren der Länge ist gering (O (1) in Big-O-Notation) und besteht hauptsächlich aus [grobe Beschreibung, geschrieben in Python-Begriffen, nicht in C-Begriffen]: Suchen Sie in einem Wörterbuch nach "len" und senden Sie es an das built_in len Funktion, die die __len__Methode des Objekts nachschlägt und das aufruft ... alles, was es tun muss, istreturn self.length

John Machin
quelle
3
Ich denke, dies ist die am besten geeignete Antwort, da dies einen Einblick in die Implementierungsdetails gibt.
AK
warum erscheint nicht lengthim Wörterbuch von dir(list)?
ViFI
das ist, wonach ich gesucht habe
Visakh Vijayan
@ViFI Weil es nur ein Beispiel ist. Die dargestellte list.lenghtVariable ist in C implementiert, nicht in Python.
Kowalski
73

Die folgenden Messungen liefern den Nachweis, dass len()O (1) für häufig verwendete Datenstrukturen ist.

Ein Hinweis zu timeit: Wenn das -sFlag verwendet wird und zwei Zeichenfolgen an timeitdie erste Zeichenfolge übergeben werden, wird dies nur einmal ausgeführt und ist nicht zeitgesteuert.

Aufführen:

$ python -m timeit -s "l = range(10);" "len(l)"
10000000 loops, best of 3: 0.0677 usec per loop

$ python -m timeit -s "l = range(1000000);" "len(l)"
10000000 loops, best of 3: 0.0688 usec per loop

Tupel:

$ python -m timeit -s "t = (1,)*10;" "len(t)"
10000000 loops, best of 3: 0.0712 usec per loop

$ python -m timeit -s "t = (1,)*1000000;" "len(t)"
10000000 loops, best of 3: 0.0699 usec per loop

String:

$ python -m timeit -s "s = '1'*10;" "len(s)"
10000000 loops, best of 3: 0.0713 usec per loop

$ python -m timeit -s "s = '1'*1000000;" "len(s)"
10000000 loops, best of 3: 0.0686 usec per loop

Wörterbuch (Wörterbuchverständnis verfügbar ab 2.7):

$ python -mtimeit -s"d = {i:j for i,j in enumerate(range(10))};" "len(d)"
10000000 loops, best of 3: 0.0711 usec per loop

$ python -mtimeit -s"d = {i:j for i,j in enumerate(range(1000000))};" "len(d)"
10000000 loops, best of 3: 0.0727 usec per loop

Array:

$ python -mtimeit -s"import array;a=array.array('i',range(10));" "len(a)"
10000000 loops, best of 3: 0.0682 usec per loop

$ python -mtimeit -s"import array;a=array.array('i',range(1000000));" "len(a)"
10000000 loops, best of 3: 0.0753 usec per loop

Set (Set-Verständnis verfügbar ab 2.7):

$ python -mtimeit -s"s = {i for i in range(10)};" "len(s)"
10000000 loops, best of 3: 0.0754 usec per loop

$ python -mtimeit -s"s = {i for i in range(1000000)};" "len(s)"
10000000 loops, best of 3: 0.0713 usec per loop

Deque:

$ python -mtimeit -s"from collections import deque;d=deque(range(10));" "len(d)"
100000000 loops, best of 3: 0.0163 usec per loop

$ python -mtimeit -s"from collections import deque;d=deque(range(1000000));" "len(d)"
100000000 loops, best of 3: 0.0163 usec per loop
mechanisches Fleisch
quelle
1
Dies ist kein so guter Benchmark, obwohl er zeigt, was wir bereits wissen. Dies liegt daran, dass Bereich (10) und Bereich (1000000) nicht O (1) sein sollen.
Unbekannt
3
Dies ist bei weitem die beste Antwort. Sie sollten nur eine Schlussfolgerung hinzufügen, falls jemand die konstante Zeit nicht erkennt.
Santiagobasulto
4
Danke für den Kommentar. Ich fügte einen Hinweis zur O (1) -Komplexität von hinzu len()und korrigierte auch die Messungen, um das -sFlag richtig zu verwenden .
mechanisches
Es ist wichtig zu beachten, dass das Speichern der Länge in einer Variablen eine erhebliche Menge an Rechenzeit einsparen kann: python -m timeit -s "l = range(10000);" "len(l); len(l); len(l)"223 ns pro Schleife python -m timeit -s "l = range(100);" "len(l)"66,2 ns pro Schleife
Radostin Stoyanov
16

len ist ein O (1), da Listen in Ihrem RAM als Tabellen (Reihe zusammenhängender Adressen) gespeichert werden . Um zu wissen, wann der Tisch stoppt, benötigt der Computer zwei Dinge: Länge und Startpunkt. Aus diesem Grund ist len ​​() ein O (1), der Computer speichert den Wert und muss ihn nur nachschlagen.

RAHUL KUMAR
quelle
3

Ich habe an len () in Python gedacht, das von der Größe der Liste abhängt. Daher speichere ich die Länge immer in einer Variablen, wenn ich sie mehrmals verwende. Aber heute habe ich beim Debuggen das Attribut __len__ im Listenobjekt bemerkt, daher muss len () es nur abrufen, was die Komplexität O (1) macht. Also habe ich nur gegoogelt, wenn jemand schon danach gefragt hat und auf diesen Beitrag gestoßen ist.

AYUSH SENAPATI
quelle
Aber es __len__ist eine Funktion, keine Variable, die die Länge einer Liste darstellt.
Kowalski
@Kowalski yes len ist eine Funktion, aber alles was sie tut ist, sie gibt self.length zurück
AYUSH SENAPATI vor
Aber dein Beitrag sagt nichts darüber aus. Woher wissen Sie auch, dass die list.__len__Funktion in konstanter Zeit ausgeführt wird? Es tut es, aber nicht nur, weil es eine Funktion ist. Weil es so umgesetzt wurde.
Kowalski vor