How Does Python 3's `range()` Achieve Such Fast Membership Checking for Large Numbers?

The Surprising Performance of range(n) in Python 3

In Python 3, the range generator function is known for its exceptional speed when checking for membership of large numbers within its range. This behavior is seemingly counterintuitive considering the immense number of integers that would seemingly need to be iterated. How does the range object achieve this remarkable efficiency?

The Smart Sequence: Range in Python 3

Contrary to expectations, the range object in Python 3 does not pre-generate its entire range of integers. Instead, it acts as a smart sequence that calculates numbers on demand during iteration. It stores only the starting point, stopping point, and step size, allowing it to calculate individual values or subranges as needed.

The Optimized contains Method

The range object also implements a highly optimized contains method. This method evaluates if a given number is within the range without scanning the entire sequence. Instead, it performs a mathematical calculation involving the starting point, stopping point, and step size. This calculation is executed in optimized C code, resulting in near-constant time complexity.

Example Implementation of a Simplified Range Object

To illustrate the concept, consider a simplified implementation of our own range object:

class my_range:
    # ... other methods as described in the question and answer ...
    def __contains__(self, num):
        if self.step < 0:
            if not (self.stop < num <= self.start):
                return False
        else:
            if not (self.start <= num < self.stop):
                return False
        return (num - self.start) % self.step == 0

This example demonstrates the basic principles behind the efficient contains method of the range object. It calculates range membership without iterating through the entire range.

In summary, the range object in Python 3 is a carefully designed data structure that combines on-demand calculation with an optimized contains method. This design enables it to perform containment checks for large numbers within an extensive range with remarkable efficiency.

The above is the detailed content of How Does Python 3's `range()` Achieve Such Fast Membership Checking for Large Numbers?. For more information, please follow other related articles on the PHP Chinese website!