In Python, `range()`

is most commonly used in `for`

loops to iterate over a known range of numbers. But that’s not all it can do! There are other interesting uses of `range()`

. For example, you can pick out elements of a range or check whether a given number belongs to a range of numbers. The latter operation is known as a **membership test**.

Python’s `range()`

objects support most of the operations that you’ve come to expect from lists. For example, you can calculate the total length, pick out a number at a given index, and iterate over each element in a range. Assume that you have a range of the first ten million integers and a list with the same numbers:

```
>>> numbers_as_range = range(10_000_000)
>>> numbers_as_list = list(numbers_as_range)
```

For many operations, you can treat these objects as interchangeable. Both ranges and lists support indexing items and calculating length:

```
>>> numbers_as_range[123]
123
>>> numbers_as_list[123]
123
>>> len(numbers_as_range)
10000000
>>> len(numbers_as_list)
10000000
```

Additionally, you can iterate over each object or check if a certain element is a member. For example, you can use the `in`

operator to check whether `-1`

is part of any of these containers:

```
>>> -1 in numbers_as_range
False
>>> -1 in numbers_as_list
False
```

Because the range and the list only include non-negative numbers, `-1`

is not a member. However, the time Python takes to figure this out is vastly different for the two data structures:

```
>>> from timeit import timeit
>>> timeit("-1 in numbers_as_range", globals=globals(), number=100)
4.68301093652801e-06
>>> timeit("-1 in numbers_as_list", globals=globals(), number=100)
5.704572553362310
```

Here, you use `timeit`

to measure the running time of the code. The reported numbers indicate how many seconds Python spent executing each command a hundred times.

Note the `e-06`

suffix in the first number. It’s scientific notation that means that the number in front of the suffix represents microseconds. If you compare the numbers, then you’ll see that searching for—and not finding—an element is several orders of magnitude slower in the list than in the range object.

In this tutorial, you’ll investigate how `range()`

works under the hood and learn **why Python’s range() membership tests are so fast**. If you want to brush up on how to work with

`range()`

, then you should have a look at The Python `range()`

Function first. You can click the link below to download some example code that you’ll be exploring in this tutorial:**Free Bonus:** Click here to download the sample code that you’ll use to explore how Python runs such quick membership tests on `range()`

.

## In Short: A Formula Determines Membership in a Python Range

In Python, three numbers define a range: ** start**,

**, and**

`stop`

**. The range will begin at**

`step`

`start`

and then contain every `step`

integer that’s smaller than `stop`

. For example, if `start = 1`

, `stop = 10`

, and `step = 2`

, then the range will be the odd numbers less than ten. Namely, one, three, five, seven, and nine.A list is much more flexible. It can contain any number of elements, and the elements can be of any type. It’s possible to have repeated elements. A list is often not sorted. In fact, it’s possible to have lists that Python can’t order, as the elements can be of mixed types that aren’t comparable.

All this flexibility has a price. To check if a list contains a particular element, Python needs to look through the list—one element at a time—until it finds a match. In principle, the operation looks something like this:

```
>>> def list_contains(element, list_elements):
... for list_element in list_elements:
... if list_element == element:
... return True
... return False
...
```

This function loops over all the list elements until it finds a match. If that match happens to be one of the first elements in the list, then it returns quickly. But if `element`

isn’t in the list, then the function needs to inspect all the elements in the list to reach this conclusion.

If you’re working with ranges, then Python can take a shortcut and use a formula instead. With the following function, you can implement such a calculation:

```
>>> def range_contains(element, start, stop, step=1):
... return start <= element < stop and (element - start) % step == 0
...
```

You’ll look at the details of how `range_contains()`

works soon. For now, you’ll use it to check if a range contains a given element. Consider the odd numbers less than ten that you played with earlier:

```
>>> range_contains(7, start=1, stop=10, step=2)
True
>>> range_contains(4, start=1, stop=10, step=2)
False
```

Your function calls confirm that the range of odd numbers contains `7`

but not `4`

. Now look closer at the implementation of `range_contains()`

. It checks two conditions:

`start <= element < stop`

`(element - start) % step == 0`

The first check ensures that `element`

is in the required half-open interval. It needs to be greater than or equal to `start`

and smaller than `stop`

because `range()`

isn’t inclusive of the `stop`

value. The second condition uses the modulo operator (`%`

) to confirm that `element`

is a multiple of `step`

away from `start`

.

**Note:** The given formula doesn’t support negative steps, but you can use negative steps to decrement with `range()`

:

```
>>> range_contains(7, start=9, stop=0, step=-2)
False
>>> 7 in range(9, 0, -2)
True
```

If `step`

is negative, then `start`

becomes the largest number in the range. That means the first condition should be `start >= element > stop`

in this case. The second condition holds for negative `step`

values because the modulo operator will still work as intended.

By using `range_contains()`

, you can determine whether an element is part of a range. The complexity of the calculations doesn’t depend on the size of the range, so these membership tests are reasonably fast, independent of the size of the range.

If you want to look for an element in a corresponding list, then you may end up having to look at all the items in the list. As the list grows, this will take more and more time. This is why testing for membership in a range is faster, in general, than in a list.

You’ve seen how—in principle—`range()`

implements membership tests. In the next section, you’ll learn more about the general implementation of `range()`

.

## How Does Python Implement `range()`

?

Since `range()`

is a core part of Python, it’s implemented in C, which certainly helps with its speed. At first glance, `range()`

may look like a function. But if you dig deeper, then you’ll discover that `range`

is a class, and `range()`

is its constructor.

In this section, you’ll code a custom `Range`

class that works mostly the same as the built-in `range`

but is slower because it’s not implemented in C. Through this exercise, you’ll learn more about `range()`

as well as Python’s data model. The data model defines special methods, also called dunder methods, that you can implement in a class to support common Python operations and operators like `len()`

, the addition operator (`+`

), and iteration.

For convenience, you’ll use data classes to define two classes, `Range`

and `_RangeIterator`

. The first one will approximate the built-in `range`

, while the second will facilitate iteration with `Range`

. Add the following code to a file named `range_tools.py`

:

```
# range_tools.py
from dataclasses import dataclass
@dataclass
class Range:
start: int
stop: int
step: int = 1
```

This gives you a skeleton that you’ll expand throughout this section. You can already instantiate a `Range`

object:

```
>>> from range_tools import Range
>>> Range(start=0, stop=10_000_000)
Range(start=0, stop=10000000, step=1)
>>> Range(start=1, stop=10, step=2)
Range(start=1, stop=10, step=2)
```

The `step`

parameter is optional, with a default value of `1`

. Unlike for the built-in `range`

, `start`

isn’t optional here, but you can use named keyword arguments.

The most common use of ranges is in iteration, so you’ll implement that next. The iterator protocol dictates that you need to implement two special methods: `.__iter__()`

and `.__next__()`

. To conveniently support iterating over a range several times, you’ll use a non-public class, `_RangeIterator`

. Each `_RangeIterator`

instance remembers the state of one iteration. Add this class to the same file:

```
# range_tools.py
from dataclasses import dataclass, field
# ...
@dataclass
class _RangeIterator:
start: int
stop: int
step: int
_state: int | None = field(default=None, init=False)
def __next__(self):
if self._state is None:
self._state = self.start
else:
self._state += self.step
if self._state >= self.stop:
raise StopIteration
return self._state
```

You name `_RangeIterator`

with a leading underscore to indicate that it’s a helper class and not something that you should call directly. In addition to including `.start`

, `.stop`

, and `.step`

, you add an internal attribute named `._state`

that will keep track of the iteration. You initialize the value of `._state`

to `None`

to indicate that the iteration hasn’t started.

**Note:** The syntax `int | None`

indicates that `.state`

can be either an integer or `None`

. You can only use the vertical bar (`|`

) in Python 3.10 and later. Otherwise, you can use `typing.Optional`

and write `Optional[int]`

.

The `.__next__()`

special method is responsible for calculating the next element. If `.state`

is `None`

, then the iteration hasn’t started, so you set the next element to `.start`

. Otherwise, you increase the current element by `.step`

. If the element is greater than or equal to `.stop`

then you end the iteration by raising `StopIteration`

. Finally, you return the value of the next element.

To complete the implementation of your custom `Range`

as an iterator, you add `.__iter__()`

to it:

```
# range_tools.py
# ...
@dataclass
class Range:
start: int
stop: int
step: int = 1
def __iter__(self):
return _RangeIterator(self.start, self.stop, self.step)
# ...
```

The `.__iter__()`

special method is in charge of initializing the iterator. In this case, you only need to instantiate a `_RangeIterator`

with proper parameters. You can now iterate over your custom `Range`

objects. Restart your REPL session to pick up your latest updates. Then try to convert `Range`

to a list:

```
>>> from range_tools import Range
>>> list(Range(start=1, stop=10, step=2))
[1, 3, 5, 7, 9]
```

Your custom `Range`

correctly lists the odd numbers below ten. Any object that supports iteration automatically supports membership tests as well:

```
>>> 7 in Range(start=1, stop=10, step=2)
True
>>> 4 in Range(start=1, stop=10, step=2)
False
```

Python implements these membership tests under the hood by iterating over the object until it finds an element or exhausts the iterator. This will be slow for large ranges:

```
>>> from timeit import timeit
>>> numbers = Range(0, 10_000_000)
>>> timeit("-1 in numbers", globals=globals(), number=100)
78.16305017451504
```

Feel free to use a smaller range in your own experiments so that you don’t have to wait too long for the operations to finish. If you get impatient, then you can interrupt the calculation by pressing `Ctrl`+`C` on your keyboard.

Again you look for `-1`

, which isn’t part of the range comprising the first ten million integers. In this example, it takes more than a minute to run the membership test one hundred times. Note that this is even slower than searching through the list as you did earlier, mainly because that list was implemented in C.

You can optimize the membership test by telling Python to use the same formula that you studied in the previous section. You do so by implementing the `.__contains__()`

special method:

```
# range_tools.py
# ...
@dataclass
class Range:
start: int
stop: int
step: int = 1
def __iter__(self):
return _RangeIterator(self.start, self.stop, self.step)
def __contains__(self, element):
return (
self.start <= element < self.stop
and (element - self.start) % self.step == 0
)
# ...
```

The implementation of `.__contains__()`

is the same as the implementation of `range_contains()`

from the previous section. You can restart your Python interpreter to check the improved performance:

```
>>> from range_tools import Range
>>> from timeit import timeit
>>> numbers = Range(0, 10_000_000)
>>> timeit("-1 in numbers", globals=globals(), number=100)
8.584989233942503e-06
```

The checks that took more than a minute earlier now run in a few microseconds! When you want custom containers where you can exploit some structure to find members of the container, you should implement `.__contains__()`

.

The built-in `range()`

supports more operations than iteration and membership testing. You can access individual elements, find the index of an element, calculate the length of a range, and so on. You can extend your own `Range`

to support the same operations. Even though you won’t do so in this tutorial, you can click below to see the implementation of a more full-featured `Range`

class:

**Free Bonus:** Click here to download the sample code that you’ll use to explore how Python runs such quick membership tests on `range()`

.

## Is a Range Better Than a List?

You’ve seen that it’s generally faster to check if a particular element is a member of a range than it is to check for membership in a corresponding list. You’ve also learned that ranges support many of the same methods as lists. So, does that mean that a range is better than a list?

As with most such questions, the answer is loud and clear: *it depends*! If the numbers you need to represent are so well structured that you can use `range()`

, then you should normally do so. A range will likely be faster than a list. It’ll also be more memory efficient because a range is uniquely defined by three numbers, while a list needs pointers to all of its elements.

If your data are harder to represent as a range, then a list is typically the better choice. The flexibility of lists is hard to beat!

## Is a Range Better Than a Set or Dictionary?

There are container data structures in Python that are better suited for membership testing than lists. For example, sets and dictionaries are optimized for looking up values. They’re on par with and even faster than ranges for looking up values:

```
>>> from timeit import timeit
>>> numbers_as_range = range(10_000_000)
>>> numbers_as_set = set(numbers_as_range)
>>> numbers_as_dict = dict.fromkeys(numbers_as_range)
>>> timeit("-1 in numbers_as_range", globals=globals(), number=100)
4.408007953310404e-06
>>> timeit("-1 in numbers_as_set", globals=globals(), number=100)
2.8829672373830812e-06
>>> timeit("-1 in numbers_as_dict", globals=globals(), number=100)
3.396009560672908e-06
```

Searching through ranges, sets, or dictionaries takes about the same time. Both sets and dictionaries are much more flexible than ranges in terms of which elements they can contain. Indeed, they bring many of the same advantages as lists. For example, a set can contain all the prime numbers less than thirty, which a range couldn’t possibly represent:

```
>>> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}
```

A **set** can contain any Python object, including integers. Sets differ from lists in a few key aspects. Sets are unordered and can’t contain duplicate values. This means that there are many use cases where lists are more suitable than sets.

For example, if you’re recording a student’s scores on several exams, then you want to use a list. If you used a set, then you wouldn’t be able to see how the student’s performance has progressed over time. And if the student scored the same on two exams, then you’d lose one of those scores.

The timing results above indicate that a set is as fast—maybe even faster—than a range when checking whether an element is a member. There’s one caveat to this: it usually takes much longer to construct a set.

As you’ve seen, creating a range only requires recording three numbers, so it’s a performant operation:

```
>>> timeit("range(10_000_000)", number=100)
3.327196463941211e-05
```

Creating the corresponding set requires iterating over all the elements in the range. Therefore, it’ll be much slower for large sets:

```
>>> timeit("set(numbers_as_range)", globals=globals(), number=100)
37.61038364198480
```

Creating the set of ten million integers takes a significant amount of time. This means that you shouldn’t convert a range—or a list—to a set if you only need to do one membership lookup. However, if you’re doing repeated lookups, then the time to convert to a set will play a smaller role, and you can start to consider working with a set.

**Dictionaries** have some properties in common with sets. In particular, the keys of a dictionary behave mostly like a set, and as you confirmed earlier, finding elements among dictionary keys is fast. Still, the creation of the dictionary will often be the bottleneck:

```
>>> timeit("dict.fromkeys(numbers_as_range)", globals=globals(), number=100)
53.68100337609845
```

Initializing the dictionary with ten million keys is even slower than creating the set. You should only use a dictionary when you have some meaningful values to map each key to. Otherwise, a set will always be a better choice.

## Conclusion

You’ve looked closely at `range()`

, in particular why Python is so fast at finding out whether a particular element is part of a range. Along the way, you noticed that ranges share several characteristics with lists, and you’ve implemented your own `Range`

class to explore these further. You also compared ranges’ performance of membership testing to that of lists, sets, and dictionaries.

Python’s data model is based on classes that implement special methods, often called dunder methods, like `.__contains__()`

, `.__iter__()`

, and `.__len__()`

. You implemented some of these yourself. However, you can look at more of them by downloading the code for your `Range`

class below:

**Free Bonus:** Click here to download the sample code that you’ll use to explore how Python runs such quick membership tests on `range()`

.

If you create your own classes, especially container data structures, then you should consider implementing explicit membership tests. Feel free to share your approach with the community in the comments below.