推荐学习书目
› Learn Python the Hard Way
Python Sites
› PyPI - Python Package Index
› http://diveintopython.org/toc/index.html
› Pocoo
值得关注的项目
› PyPy
› Celery
› Jinja2
› Read the Docs
› gevent
› pyenv
› virtualenv
› Stackless Python
› Beautiful Soup
› 结巴中文分词
› Green Unicorn
› Sentry
› Shovel
› Pyflakes
› pytest
Python 编程
› pep8 Checker
Styles
› PEP 8
› Google Python Style Guide
› Code Style from The Hitchhiker's Guide
1000000000000000 in range(1000000000000001) 的执行速度为什么这么快
lzjun · lzjun567 · 2017-01-13 23:35:47 +08:00 · 2594 次点击这是一个创建于 2906 天前的主题，其中的信息可能已经有所发展或是发生改变。
在 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 干货和有温度的内容
 |
1
luxinxin 2017-01-14 00:33:15 +08:00 via Android
探讨很有意思，但“ python3 中的 range 方法不仅可以节省内存，而且执行效率更高”这个结论似乎不是很直接啊，只有在 in 这个例子里有用吧？
|
 |
2
Yinz 2017-01-14 00:41:51 +08:00
一下子好像想不出判断一个常数是否在一个 range 里的用处啊。。。不知哪位能赐教一下？
|
 |
3
skywatcher 2017-01-14 00:46:48 +08:00
蛮有意思的
|
 |
4
latyas 2017-01-14 01:22:06 +08:00
http://gist.github.com/ly0/f7c4a8a1e40555ac7684e5b68b8cc59d
路过，附上 Python3.6 里 range 的 contains 方法的实现片段, btw python2.7 里没有实现 contains |
 |
5
ericls 2017-01-14 07:25:56 +08:00  1
把这种问题当成面试题是有多疯。。。
|
 |
6
HGladIator 2017-01-14 10:00:35 +08:00 via iPhone
立马就关注了，喜欢这样深入的姿势
|
 |
8
lzjun OP @latyas python2 中没有__contain__方法的这个问题其实很早就在 python 社区提出来了，不过最终他还是没有并入到 python2 中，而是直接集成到 python3 中去了
http://bugs.python.org/issue1766304 |
 |
9
glogo 2017-01-14 14:08:59 +08:00
编译成字节码看，然后对照 Python 源码去理解，是个比较好的办法吧？
|
Select Language