Erstens Sie nicht die Geschwindigkeit von len()
gemessen haben, haben Sie die Geschwindigkeit der Erstellung einer Liste gemessen/set zusammen mit die Geschwindigkeit der len()
.
Verwenden Sie das --setup
Argument von timeit
:
$ python -m timeit --setup "a=[1,2,3,4,5,6,7,8,9,10]" "len(a)"
10000000 loops, best of 3: 0.0369 usec per loop
$ python -m timeit --setup "a={1,2,3,4,5,6,7,8,9,10}" "len(a)"
10000000 loops, best of 3: 0.0372 usec per loop
Die Anweisungen, die Sie zu --setup
passieren, werden ausgeführt, bevor die Geschwindigkeit des len()
messen.
Zweitens, sollten Sie beachten, dass len(a)
ist eine ziemlich schnelle Aussage. Der Vorgang der Geschwindigkeitsmessung kann "Rauschen" unterliegen. Bedenken Sie, dass the code executed (and measured) by timeit dem folgenden entspricht:
for i in itertools.repeat(None, number):
len(a)
Da sowohl len(a)
und itertools.repeat(...).__next__()
sind schnelle Operationen und ihre Geschwindigkeiten können ähnlich sein, die Geschwindigkeit der itertools.repeat(...).__next__()
die Zeiten beeinflussen können.
Aus diesem Grunde sollten Sie besser Maß len(a); len(a); ...; len(a)
(100-mal wiederholt oder so), so dass der Körper der for-Schleife eine wesentlich höhere Menge an Zeit in Anspruch nimmt als der Iterator:
$ python -m timeit --setup "a=[1,2,3,4,5,6,7,8,9,10]" "$(for i in {0..1000}; do echo "len(a)"; done)"
10000 loops, best of 3: 29.2 usec per loop
$ python -m timeit --setup "a={1,2,3,4,5,6,7,8,9,10}" "$(for i in {0..1000}; do echo "len(a)"; done)"
10000 loops, best of 3: 29.3 usec per loop
(Die Ergebnisse noch sagt, dass len()
die gleichen Leistungen auf Listen und Sätzen, aber jetzt sind Sie sicher, dass das Ergebnis korrekt ist.)
Drittens es stimmt, dass „Komplexität“ und „Geschwindigkeit“ beziehen, aber ich glaube, Sie machen etwas Verwirrung. Die Tatsache, dass die Komplexität von Listen und Mengen len()
O (1) bedeutet, bedeutet nicht, dass sie auf Listen und Mengen mit derselben Geschwindigkeit laufen muss.
Es bedeutet, dass im Durchschnitt, egal wie lange die Liste a
ist, len(a)
führt die gleiche asymptotische Anzahl von Schritten. Und egal wie lange der Satz b
ist, len(b)
führt die gleiche asymptotische Anzahl von Schritten aus. Aber der Algorithmus für die Berechnung der Größe von Listen und Mengen kann unterschiedlich sein, was zu unterschiedlichen Leistungen führt (Zeit zeigt, dass dies nicht der Fall ist, dies kann jedoch eine Möglichkeit sein).
Schließlich
Wenn die Erzeugung eines Satzes Objekt mehr Zeit zum Erstellen einer Liste verglichen nimmt, was wäre der eigentliche Grund sein?
Ein Satz, wie Sie wissen, erlaubt keine wiederholten Elemente. Sets in CPython sind als Hashtabellen implementiert (um sicherzustellen, dass der Durchschnittswert O (1) Insertion und Lookup): Das Erstellen und Pflegen einer Hashtabelle ist wesentlich komplexer als das Hinzufügen von Elementen zu einer Liste.
Insbesondere beim Erstellen einer Menge müssen Sie Hashes berechnen, die Hash-Tabelle erstellen, sie nachschlagen, um das Einfügen duplizierter Ereignisse zu vermeiden, und so weiter. Im Gegensatz dazu sind Listen in CPython als ein einfaches Array von Zeigern implementiert, die wie erforderlich malloc()
ed und realloc()
ed sind.
Ihr letzter Satz ist wahrscheinlich richtig - beim Hinzufügen von Elementen zu einem Set ist Hashing beteiligt. –
Sie können versuchen, den Block ohne 'len()' zu überprüfen :) – Caramiriel
@Caramiriel oder zu zwei Strings und pass-'s Option :) – Maroun