推断一个元素 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 了。
以上就是为什么 1000000000000000 in range(1000000000000001) 在 Python3 里速率那末快的细致内容，更多请关注ki4网别的相干文章！
