Kosten der Funktion len()

Question

Wie hoch sind die Kosten für len() Funktion für Python built-ins? (Liste/Tupel/String/Wörterbuch)

Answer 1

Es ist O(1) (konstante Zeit, nicht abhängig von der tatsächlichen Länge des Elements - sehr schnell) für alle von Ihnen genannten Typen, plus set und andere wie zum Beispiel array.array .

Answer 2

Aufruf von len() für diese Datentypen ist O(1) en CPython , die offizielle und am weitesten verbreitete Implementierung der Sprache Python. Hier ist ein Link zu einer Tabelle, die die algorithmische Komplexität vieler verschiedener Funktionen in CPython angibt:

ZeitKomplexität Python Wiki Seite

Answer 3

Alle diese Objekte behalten ihre eigene Länge im Auge. Die Zeit, um die Länge zu extrahieren, ist klein (O(1) in Big-O-Notation) und besteht hauptsächlich aus [grobe Beschreibung, geschrieben in Python-Begriffen, nicht in C-Begriffen]: Schauen Sie "len" in einem Wörterbuch nach und senden Sie es an die eingebaute len-Funktion, die die Objektlänge __len__ Methode und rufen diese auf ... alles, was es tun muss, ist return self.length

Answer 4

Die folgenden Messungen belegen, dass len() ist O(1) für häufig genutzte Datenstrukturen.

Eine Anmerkung zu timeit : Wenn die -s Flagge verwendet und zwei Zeichenketten werden an timeit die erste Zeichenkette wird nur einmal ausgeführt und ist nicht zeitlich begrenzt.

Liste:

$ 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

Zeichenfolge:

$ 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örterbuch-Verständnis in 2.7+ verfügbar):

$ 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 in 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

Answer 5

len ist ein O(1), weil in Ihrem RAM Listen als Tabellen gespeichert sind (Reihe von zusammenhängenden Adressen). Um zu wissen, wann die Tabelle endet, benötigt der Computer zwei Dinge: Länge und Startpunkt. Deshalb ist len() ein O(1), der Computer speichert den Wert und muss ihn nur noch nachschlagen.