How Does Python's `range()` Object Achieve Near-Instantaneous Membership Checks for Extremely Large Ranges?

The Surprising Speed of Python's Range Object

In Python 3, the range() function generates an object that represents a range of numbers. This object differs from the traditional generator in that it does not create the entire range in memory. Instead, it produces numbers on demand, making it significantly faster for large ranges.

The Problem:

Intuitively, determining whether a number falls within a range requires iterating through all the values in that range. However, the Python 3 range() object defies this expectation by performing such checks almost instantaneously, even for vast ranges.

The Solution:

The range() object does not physically store the entire range. Rather, it holds the starting, ending, and step values. When testing for membership, it calculates the result based on those values alone. This calculation is executed in C code, which contributes to its high efficiency.

A Comparison:

The following Python code compares the performance of the range() object with a custom implementation that generates numbers on the fly:

def my_crappy_range(N):
    i = 0
    while i < N:
        yield i
        i += 1

1_000_000_000_000_000 in range(1_000_000_000_000_001)
1_000_000_000_000_000_000_000 in range(1_000_000_000_000_000_000_001)

for number in my_crappy_range(100):
    print(number)

The range() object performs the checks almost instantly, whereas the custom implementation takes significantly longer.

Additional Optimizations:

The range() object also implements an contains hook that optimizes containment testing. This optimization allows the object to determine if a number is within its range in near constant time, regardless of the range's size.

Conclusion:

The Python 3 range() object's exceptional speed results from its efficient data structure and optimized operations. It stores minimal information and calculates the requested values on the fly, enabling almost instantaneous containment testing even for enormous ranges.

The above is the detailed content of How Does Python's `range()` Object Achieve Near-Instantaneous Membership Checks for Extremely Large Ranges?. For more information, please follow other related articles on the PHP Chinese website!