Python執行x in range(y)的速度能有多快

這篇文章主要介紹了Python執行x in range(y)的速度能有多快的相關知識，內容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇Python執行x in range(y)的速度能有多快文章都會有所收獲，下面我們一起來看看吧。

題圖：unsplash.com

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

也可以把它當作一到面試題來問：Python2 中的 xrange 與 python3 中的 range 有什么區別？它不僅可以考察候選者對 Python3 的熟悉程度，而且可以看出候選者對一個知識點的理解深度。

關于“Python執行x in range(y)的速度能有多快”這篇文章的內容就介紹到這里，感謝各位的閱讀！相信大家對“Python執行x in range(y)的速度能有多快”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注億速云行業資訊頻道。