在 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__ 并不是逐个值迭代对比,而是采用这样一种逻辑:
此刻真相大白, 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 源码去理解,是个比较好的办法吧?
|