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

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

題圖：unsplash.com

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

判斷一個(gè)元素 x 是否存在于集合 y 中最簡(jiǎn)單粗暴地方法就是迭代，每次取出一個(gè)值與之比較，如果集合中存在一個(gè)值 z 等于 x就返回 true ，它的時(shí)間復(fù)雜度是 O(n)，使用哈希算法的理論時(shí)間復(fù)雜度是 O(1)，二分查找的時(shí)間復(fù)雜度是 O(log n)，那么 Python 究竟會(huì)采用的哪種算法來實(shí)現(xiàn)呢？

先來做個(gè)實(shí)驗(yàn)：

#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 函數(shù)返回的是一個(gè)列表對(duì)象，一次性把所有的元素加載到內(nèi)存，所以執(zhí)行第一個(gè)表達(dá)式的時(shí)候，系統(tǒng)會(huì)突然感覺非?？D，它需要的時(shí)間是5秒多。

xrange 和 python3 中的 range 函數(shù)類似，都是返回一個(gè)迭代器對(duì)象，但是它倆的執(zhí)行結(jié)果相差懸殊，讓人大跌眼鏡。第三個(gè)表達(dá)式所花的時(shí)間接近0秒，為何 python2 的 xrange 與 python3 中 range 函數(shù)區(qū)別這么大？為了弄明白其中的玄機(jī)，我們要理解in操作是如何執(zhí)行的。根據(jù) Python 文檔 in 的規(guī)則：

• 如果該類實(shí)現(xiàn)了__contains__()方法，那么只要 y.__contains__(x) 返回 true 那么 x in y 也返回 true，反之亦然。

• 沒有實(shí)現(xiàn)__contains__()方法，但實(shí)現(xiàn)了__iter__()方法，那么在迭代過程中如果有某個(gè)值 z==x，就返回 true，否則就是 false。

• 如果以上兩個(gè)方法都沒有實(shí)現(xiàn)，就看__getitem__()方法， 如果存在一個(gè)索引i使得  x==y[i] ，就返回 true，否則返回 false。

明白了 in 的規(guī)則之后，我們先看看 xrange 提供了哪些方法：

dir(xrange)

['__class__','__getitem__', '__hash__', '__init__', 
'__iter__', '__len__', '__new__', ...]

是的，xrange 函數(shù)只實(shí)現(xiàn)了 __getitem__ 和 __iter__，判斷 x 是 是否在 y 中需要逐個(gè)值迭代進(jìn)行比較，也就是說 xrange 的時(shí)間復(fù)雜度是O(n)。

再來看看 python3 的 range 有哪些方法：

 dir(range)
['__class__', '__contains__', '__getitem__', '__iter__',  
'count', 'index', 'start', 'step', 'stop', ...]

range 提供的屬性比 xrange 要多很多，不僅實(shí)現(xiàn)了 __getitem__ 和 __iter__ ，還實(shí)現(xiàn)了 __contains__ ，所以它會(huì)優(yōu)先調(diào)用__contains__方法，此外，它還提供了三個(gè)屬性 start、stop、step。那么究竟為什么它的執(zhí)行速度會(huì)如此之快呢？來看看contains方法是如何實(shí)現(xiàn)的吧。

在 Python3 中，__contains__ 并不是逐個(gè)值迭代對(duì)比，而是采用這樣一種邏輯：

• 首先檢查 x 是否 在 start 和 stop 范圍之間：start <= x < stop

• 如果在這個(gè)區(qū)間范圍，那么再根據(jù) step 計(jì)算 x 是否剛好落在 xrange 區(qū)間中的某個(gè)值上，這里用取模的方式來判斷：(x - start) % step == 0

此刻真相大白，xrange 的時(shí)間復(fù)雜度是O(1)，也就是說不管 xrange(start, stop, step) 中的 stop 值多大，時(shí)間復(fù)雜度都是一個(gè)常量。所以 python3 中的 range 方法不僅可以節(jié)省內(nèi)存，而且執(zhí)行效率更高，所以不要再糾結(jié)學(xué) Python2 還是 Python3 了。

也可以把它當(dāng)作一到面試題來問：Python2 中的 xrange 與 python3 中的 range 有什么區(qū)別？它不僅可以考察候選者對(duì) Python3 的熟悉程度，而且可以看出候選者對(duì)一個(gè)知識(shí)點(diǎn)的理解深度。

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