在 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中文網其他相關文章！
