python-internals - how to add python code in android - Why is “1000000000000000 in range(1000000000000001)” so fast in Python 3?
how to open py files in mobile / python / performance / python-3.x / range
It is my understanding that the
range() function, which is actually an object type in Python 3, generates its contents on the fly, similar to a generator.
This being the case, I would have expected the following line to take an inordinate amount of time, because in order to determine whether 1 quadrillion is in the range, a quadrillion values would have to be generated:
1000000000000000 in range(1000000000000001)
I have also tried things like this, but the calculation is still almost instant:
1000000000000000000000 in range(0,1000000000000000000001,10) # count by tens
If I try to implement my own range function, the result is not so nice!!
def my_crappy_range(N): i = 0 while i < N: yield i i += 1 return
What is the
range() object doing under the hood that makes it so fast?
Martijn Pieters' answer was chosen for its completeness, but also see abarnert's first answer for a good discussion of what it means for
range to be a full-fledged sequence in Python 3, and some information/warning regarding potential inconsistency for
__contains__ function optimization across Python implementations. abarnert's other answer goes into some more detail and provides links for those interested in the history behind the optimization in Python 3 (and lack of optimization of
xrange in Python 2). Answers by poke and by wim provide the relevant C source code and explanations for those who are interested.
The object returned by
range() is actually a
range object. This object implements the iterator interface so you can iterate over its values sequentially, just like a generator, list, or tuple.
But it also implements the
__contains__ interface which is actually what gets called when an object appears on the right hand side of the
in operator. The
__contains__() method returns a
bool of whether or not the item on the left-hand-side of the
in is in the object. Since
range objects know their bounds and stride, this is very easy to implement in O(1).