
| rank | vote | view | answer | url |
|:-:|:-:|:-:|:-:|:-:|
|47|2165|206370|10| [url](http://stackoverflow.com/questions/30081275/why-is-1000000000000000-in-range1000000000000001-so-fast-in-python-3) |
***

## 为什么 "1000000000000000 in range(1000000000000001)" 在 Python3 里速度那么快?

在我理解 `range()` 函数作为 [an object type in Python 3](https://docs.python.org/3/library/stdtypes.html#typesseq-range) 生成的内容和生成器差不多快.

我测试如下语句

```python
1000000000000000 in range(1000000000000001)
```

不管我加了多少个 0 这个计算的结果时间都差不多

我还试了下这个, 结果差不多, 非常快:

```python
000000000000000000000 in range(0,1000000000000000000001,10) # count by tens
```

但是我自己写了个代码速度就非常慢:

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

所以我想问为啥 `range()` 如此之快?

***

Python3 的 `range()` 对象并不会立即产生数值;它会在需要时来产生.它包含你的起始, 终止和步长, 它会随着每次迭代来产生下一个数值.

这个对象通过 [`object.__contains__ hook`](https://docs.python.org/3/reference/datamodel.html#object.__contains__) 来实现的.计算的时间复杂度为 `O(1)`.在迭代的过程中其实是不需要一下计算出所有的数值的.

根据 [`range()`](https://docs.python.org/3/library/stdtypes.html#range) 文档

> `range` 优于于 `list` 和 `tuple` 的地方在于不管它的范围是多少它只占用少量的内存(因为它只保存 `start`, `stop`, `step`, 按需得到数值)

所以你可以这么写你的 `range()`:

```python
class my_range(object):
    def __init__(self, start, stop=None, step=1):
        if stop is None:
            start, stop = 0, start
        self.start, self.stop, self.step = start, stop, step
        if step < 0:
            lo, hi = stop, start
        else:
            lo, hi = start, stop
        self.length = ((hi - lo - 1) // abs(step)) + 1

    def __iter__(self):
        current = self.start
        if self.step < 0:
            while current > self.stop:
                yield current
                current += self.step
        else:
            while current < self.stop:
                yield current
                current += self.step

    def __len__(self):
        return self.length

    def __getitem__(self, i):
        if i < 0:
            i += self.length
        if 0 <= i < self.length:
            return self.start + i * self.step
        raise IndexError('Index out of range: {}'.format(i))

    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
```

这个代码和真正的 `range()` 缺少了像 `.index()`, `.count()` 方法,但是应当可以给你些启发.

