為什麼 x in range(1000000000000001) 的執行速度這麼快

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

判斷一個元素 x 是否存在於集合 y 中最簡單粗暴地方法就是迭代，每次取出一個值與之比較，如果集合中存在一個值 z 等於 x 就返回 true ，它的時間複雜度是 O(n)，使用哈希演算法的理論時間複雜度是 O(1)，二分查找的時間複雜度是 O(log n)，那麼 Python 究竟會採用的哪種演算法來實現呢？

先來做個實驗：

#python2timeit.timeit(1000000000 in range(0,1000000000,10), number=1)5.50357640805305timeit.timeit(1000000000 in xrange(0,1000000000,10), number=1)2.3025200839183526# python3import timeittimeit.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 。

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 乾貨和有溫度的內容

推薦閱讀：