為什麼 1000000000000000 in range(1000000000000001) 在 Python3 裡速度那麼快

在 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 了。

以上是為什麼 1000000000000000 in range(1000000000000001) 在 Python3 裡速度那麼快的詳細內容。更多資訊請關注PHP中文網其他相關文章！