Pourquoi 1000000000000000 dans la plage (1000000000000001) est-il si rapide en Python3

À quelle vitesse l'expression 1000000000000000 in range(1000000000000001) peut-elle être exécutée en Python ?

Le moyen le plus simple et le plus grossier de déterminer si un élément x renvoie vrai, sa complexité temporelle est O(n), la complexité temporelle théorique de l'utilisation de l'algorithme de hachage est O( 1), et la complexité temporelle de la recherche binaire est O(log n), alors qu'utilisera Python, quel algorithme est utilisé pour y parvenir ?

Faisons d'abord une expérience :

#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

Nous savons tous que la fonction range de python2 renvoie un objet liste, chargeant tous les éléments en mémoire à la fois, donc exécutez la première expression Lors de l'exécution, le Le système se sentira soudainement très bloqué et cela prendra plus de 5 secondes.

xrange est similaire à la fonction range de python3, les deux renvoient un objet itérateur, mais la différence entre leurs résultats d'exécution est choquante. La troisième expression prend près de 0 seconde. Pourquoi y a-t-il une si grande différence entre la fonction xrange en python2 et la fonction range en python3 ? Afin de comprendre le mystère, nous devons comprendre comment se déroule l’opération. Selon les règles de in dans la documentation Python :

Si la classe implémente la méthode contain(), alors tant que y.contains(x) renvoie true alors x in y renvoie également true, et vice versa .

La méthode contain() n'est pas implémentée, mais la méthode iter() est implémentée. Ensuite, pendant le processus d'itération, s'il y a une certaine valeur z==x, elle retournera true, sinon elle le sera. FAUX.

Si aucune des deux méthodes ci-dessus n'est implémentée, regardez la méthode getitem(). S'il existe un index i tel que x==y[i], renvoie true, sinon renvoie false.

Après avoir compris les règles de in, jetons d'abord un coup d'œil aux méthodes fournies par xrange :

dir(xrange)
['__class__','__getitem__', '__hash__', '__init__', 
'__iter__', '__len__', '__new__', ...]

Oui, la fonction xrange implémente uniquement getitem et iter pour déterminer si x est nécessaire dans y La comparaison est effectuée de manière itérative valeur par valeur, ce qui signifie que la complexité temporelle de xrange est O(n).

Jetons un coup d'œil aux méthodes range de python3 :

 dir(range)
['__class__', '__contains__', '__getitem__', '__iter__',  
'count', 'index', 'start', 'step', 'stop', ...]

range fournit beaucoup plus d'attributs que xrange. Il implémente non seulement getitem et iter, mais implémente également contain, il sera donc appelé. contient d'abord la méthode, en plus, il fournit également trois attributs start, stop, step. Alors pourquoi exactement s’exécute-t-il si vite ? Voyons comment la méthode contain est implémentée.

En Python3, contain ne compare pas les valeurs de manière itérative une par une, mais utilise une telle logique :

Vérifiez d'abord si x est entre les plages de début et de fin : start <= x < stop

Si c'est dans cet intervalle, calculez en fonction de l'étape si x tombe sur une certaine valeur dans l'intervalle xrange. Ici, nous utilisons la méthode modulo pour déterminer : (x - start) % step == 0

La vérité est révélée à ce moment, la complexité temporelle de xrange est O(1), c'est-à-dire quelle que soit la taille de la valeur d'arrêt dans xrange( start, stop, step) est la complexité temporelle. Tout est une constante. Par conséquent, la méthode range dans python3 peut non seulement économiser de la mémoire, mais également fonctionner plus efficacement, alors ne vous inquiétez pas de savoir si vous devez apprendre Python2 ou Python3.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!