Why is `1015 in range(1015 1)` so fast in Python 3?

Why is Quadrillion in Range(Quadrillion 1) Fast in Python 3?

Question:

Python 3's range() function is a generator-like object that produces values on demand. Given this, one might expect checking for 1 quadrillion in range(1 quadrillion 1) to be time-consuming since a quadrillion values would need to be generated. However, this operation is surprisingly fast. Why is this?

Answer:

The range() object in Python 3 is a smart sequence that does not immediately produce its elements. It holds only the start, stop, and step values, and calculates the next integer on demand during iteration.

Crucially, range() implements the contains hook, which efficiently determines if a given number falls within the range. This calculation is a (near) constant time operation, so the object does not need to scan every possible value in the range.

Unlike a list of all values in the range, which would incur a linear search, range() calculates membership in O(log N) time, where N is the number of elements in the range. This optimization is made possible by the unbounded nature of Python integers and their efficient handling in optimized C code.

The above is the detailed content of Why is `1015 in range(1015 1)` so fast in Python 3?. For more information, please follow other related articles on the PHP Chinese website!