1000000000000000 in range(1000000000000001) 的执行速度为什么这么快

[lzjun]

在 Python 中，表达式 1000000000000000 in range(1000000000000001) 的执行速度能有多快？

判断一个元素 x 是否存在于集合 y 中最简单粗暴地方法就是迭代，每次取出一个值与之比较，如果集合中存在一个值 z 等于 x 就返回 true ，它的时间复杂度是 O(n)，使用哈希算法的理论时间复杂度是 O(1)，二分查找的时间复杂度是 O(log n)，那么 Python 究竟会采用的哪种算法来实现呢？

先来做个实验：

#python2

timeit.timeit('1000000000 in range(0,1000000000,10)', number=1)
5.50357640805305

timeit.timeit('1000000000 in xrange(0,1000000000,10)', number=1)
2.3025200839183526

# python3

import timeit
timeit.timeit('1000000000 in range(0,1000000000,10)', number=1)
4.490355838248402e-06

我们都知道 python2 中的 range 函数返回的是一个列表对象，一次性把所有的元素加载到内存，所以执行第一个表达式的时候，系统会突然感觉非常卡顿，它需要的时间是 5 秒多。

xrange 和 python3 中的 range 函数类似，都是返回一个迭代器对象，但是它俩的执行结果相差悬殊，让人大跌眼镜。第三个表达式所花的时间接近 0 秒，为何 python2 的 xrange 与 python3 中 range 函数区别这么大？为了弄明白其中的玄机，我们要理解 in 操作是如何执行的。根据 Python 文档 in 的规则：

如果该类实现了__contains__()方法，那么只要 y.contains(x) 返回 true 那么 x in y 也返回 true ，反之亦然。 没有实现__contains__()方法，但实现了__iter__()方法，那么在迭代过程中如果有某个值 z==x ，就返回 true ，否则就是 false 。 如果以上两个方法都没有实现，就看__getitem__()方法， 如果存在一个索引 i 使得 x==y[i] ，就返回 true ，否则返回 false 。 明白了 in 的规则之后，我们先看看 xrange 提供了哪些方法：

dir(xrange)

['__class__','__getitem__', '__hash__', '__init__', 
'__iter__', '__len__', '__new__', ...]

是的， xrange 函数只实现了 getitem 和 __iter__，判断 x 是 是否在 y 中需要逐个值迭代进行比较，也就是说 xrange 的时间复杂度是 O(n)。

再来看看 python3 的 range 有哪些方法：

 dir(range)
['__class__', '__contains__', '__getitem__', '__iter__',  
'count', 'index', 'start', 'step', 'stop', ...]

range 提供的属性比 xrange 要多很多，不仅实现了 getitem 和 iter ，还实现了 contains ，所以它会优先调用__contains__方法，此外，它还提供了三个属性 start 、 stop 、 step 。那么究竟为什么它的执行速度会如此之快呢？来看看 contains 方法是如何实现的吧。

在 Python3 中，__contains__ 并不是逐个值迭代对比，而是采用这样一种逻辑：

• 首先检查 x 是否 在 start 和 stop 范围之间： start <= x < stop
• 如果在这个区间范围，那么再根据 step 计算 x 是否刚好落在 xrange 区间中的某个值上，这里用取模的方式来判断：(x - start) % step == 0

此刻真相大白， xrange 的时间复杂度是 O(1)，也就是说不管 xrange(start, stop, step) 中的 stop 值多大，时间复杂度都是一个常量。所以 python3 中的 range 方法不仅可以节省内存，而且执行效率更高，所以不要再纠结学 Python2 还是 Python3 了。

也可以把它当作一到面试题来问： Python2 中的 xrange 与 python3 中的 range 有什么区别？它不仅可以考察候选者对 Python3 的熟悉程度，而且可以看出候选者对一个知识点的理解深度。

公众号『一个程序员的微站』分享 Python 干货和有温度的内容

[luxinxin]

探讨很有意思，但“ python3 中的 range 方法不仅可以节省内存，而且执行效率更高”这个结论似乎不是很直接啊，只有在 in 这个例子里有用吧？

[Yinz]

一下子好像想不出判断一个常数是否在一个 range 里的用处啊。。。不知哪位能赐教一下？

[skywatcher]

蛮有意思的

[latyas]

http://gist.github.com/ly0/f7c4a8a1e40555ac7684e5b68b8cc59d

路过，附上 Python3.6 里 range 的 contains 方法的实现片段, btw python2.7 里没有实现 contains

[ericls]

把这种问题当成面试题是有多疯。。。

[HGladIator]

立马就关注了，喜欢这样深入的姿势

[lzjun]

@luxinxin 节省内存是 range 返回的是一个迭代器的特性带来的优势

[lzjun]

@latyas python2 中没有__contain__方法的这个问题其实很早就在 python 社区提出来了，不过最终他还是没有并入到 python2 中，而是直接集成到 python3 中去了

http://bugs.python.org/issue1766304

[glogo]

编译成字节码看，然后对照 Python 源码去理解，是个比较好的办法吧？

[latyas]

@lzjun 没有办法，官方也不可能在一个即将要死的版本上添加新 feature ，无论从意义上还是从版本的兼容上。

[latyas]

@ericls 这种题当面试题的公司基本可以转身就走了，真想折磨人 python 能问的问题可多了（越甜的糖越有毒）， cpython 的实现不好的地方也有太多，比如最近 3.6 的 dict 重新实现，如果这个 range 的问题能算面试题的话，是不是所有的 PEP 都可以随机抽出来做面试题呢？仅个人意见，不代表真实情况。

[lzjun]

@latyas 纯粹作为开放式的话题吧，不能说这个答不出来就直接否定你，只是说答好了可以加分，答不好也没太大关系

[latyas]

@lzjun 这种有标准正确答案的问题不算是开放性的问题吧，对面试的效应姑且不谈，只是个人认为问这种问题面试官有 zb 的嫌疑，当然，这不是什么高端 b （为了避免误会，这么说没有刻意针对你和你的主题的意思啊。。