Wie schnell kann der Ausdruck 1000000000000000 in range(1000000000000001) in Python ausgeführt werden?
Der einfachste und gröbste Weg, um zu bestimmen, ob ein Element x „true“ zurückgibt, ist seine zeitliche Komplexität O(n), die theoretische zeitliche Komplexität der Verwendung des Hash-Algorithmus ist O( 1) und die Zeitkomplexität der binären Suche beträgt O(log n), welchen Algorithmus verwendet Python dann, um dies zu erreichen?
Lassen Sie uns zuerst ein Experiment durchführen:
#python2 timeit.timeit('1000000000 in range(0,1000000000,10)', number=1) 5.50357640805305 timeit.timeit('1000000000 in xrange(0,1000000000,10)', number=1) 2.3025200839183526 # python3 import timeit timeit.timeit('1000000000 in range(0,1000000000,10)', number=1) 4.490355838248402e-06
Wir alle wissen, dass die Range-Funktion in Python2 ein Listenobjekt zurückgibt, das alle Elemente auf einmal in den Speicher lädt, also führen Sie den ersten Ausdruck aus Das System fühlt sich plötzlich sehr festgefahren an und es dauert mehr als 5 Sekunden.
xrange ähnelt der Range-Funktion in Python3, beide geben ein Iteratorobjekt zurück, aber ihre Ausführungsergebnisse sind so unterschiedlich, dass es überraschend ist. Der dritte Ausdruck dauert fast 0 Sekunden. Warum gibt es einen so großen Unterschied zwischen xrange in Python2 und der Range-Funktion in Python3? Um das Geheimnis zu verstehen, müssen wir verstehen, wie die Operation durchgeführt wird. Gemäß den Regeln von in in der Python-Dokumentation:
Wenn die Klasse die Methode contains() implementiert, gibt x in y auch true zurück, solange y.contains(x) true zurückgibt, und umgekehrt .
Die Methode „contains()“ ist nicht implementiert, aber die Methode „iter()“ ist implementiert. Wenn während des Iterationsprozesses ein bestimmter Wert z==x vorhanden ist, wird „true“ zurückgegeben, andernfalls ist dies der Fall FALSCH.
Wenn keine der beiden oben genannten Methoden implementiert ist, schauen Sie sich die Methode getitem() an. Wenn es einen Index i mit x==y[i] gibt, geben Sie true zurück, andernfalls geben Sie false zurück.
Nachdem wir die Regeln von in verstanden haben, werfen wir zunächst einen Blick auf die von xrange bereitgestellten Methoden:
dir(xrange) ['__class__','__getitem__', '__hash__', '__init__', '__iter__', '__len__', '__new__', ...]
Ja, die xrange-Funktion implementiert nur getitem und iter, um zu bestimmen, ob x in y benötigt wird Der Vergleich wird iterativ Wert für Wert durchgeführt, was bedeutet, dass die zeitliche Komplexität von xrange O(n) beträgt.
Werfen wir einen Blick auf die Range-Methoden von Python3:
dir(range) ['__class__', '__contains__', '__getitem__', '__iter__', 'count', 'index', 'start', 'step', 'stop', ...]
range bietet viel mehr Attribute als xrange. Es implementiert nicht nur getitem und iter, sondern auch contains, also wird es aufgerufen Enthält zunächst die Methode und stellt außerdem drei Attribute bereit: Start, Stopp und Schritt. Warum genau wird es so schnell ausgeführt? Werfen wir einen Blick darauf, wie die Methode „contains“ implementiert wird.
Contains vergleicht in Python3 die Werte nicht iterativ einzeln, sondern verwendet eine solche Logik:
Überprüfen Sie zunächst, ob x zwischen dem Start- und Stoppbereich liegt : start <= x < stop
Wenn es innerhalb dieses Intervalls liegt, berechnen Sie gemäß Schritt, ob x zufällig auf einen bestimmten Wert im xrange-Intervall fällt. Hier verwenden wir die Modulo-Methode, um Folgendes zu bestimmen: (x - Start) % Schritt == 0
Die Wahrheit wird in diesem Moment enthüllt, die zeitliche Komplexität von xrange ist O(1), das heißt, egal wie groß der Stoppwert in xrange( Start, Stopp, Schritt) ist die Zeitkomplexität. Es ist alles eine Konstante. Daher kann die Range-Methode in Python3 nicht nur Speicher sparen, sondern auch effizienter arbeiten. Machen Sie sich also keine Gedanken darüber, ob Sie Python2 oder Python3 lernen möchten.
Das obige ist der detaillierte Inhalt vonWarum ist 1000000000000000 im Bereich (1000000000000001) in Python3 so schnell?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
