Python遞歸二進制搜索功能

問：基本上...創建一種與三種不同語言相同（除了編程語言之外）的二進制搜索算法，對於八個不同大小的數組的相同的8,000,000次不成功搜索（128,512， ...，52428，（524288 * 4）= 2097152）。我編碼這個問題的前兩種語言是C和C++，並得到正常的結果：2097152大小的陣列不超過3sPython遞歸二進制搜索功能

我決定嘗試Python出來，因爲我從來沒有編碼它，並想給它一槍。我最終得到可笑倍的算法來完成：

-For 128 elements I got 800s 
-512 elements = 1005s 
-2048 elements = 1682s 
-8192 elements = 4152s (my computer went to sleep so this may be the sudden increase) 
-32768 elements = 1714s 
-131072 elements = 1890s 
-524288 = 2074s 
-2097152 = still running!!

（除了有8192元的陣列，這基本上遵循O（日誌（BASE2）N）：平均每次遞歸檢查過程114S

。

這是我第一次用Python編碼，所以我想知道：是我的代碼效率低下（事實上算法是非常基本的），還是Python無法處理遞歸調用以及C/C++/Java，尤其是當他們我的Python代碼如下：

import time 
def binarySearch(array, key, min, max): 
    mid = int(min + ((max - min)/2)) 
    if min >= max: 
     return False 
    elif array[mid] == key: 
     return True 
    elif array[mid] > key: 
     return binarySearch(array, key, min, mid - 1) 
    elif array[mid] < key: 
     return binarySearch(array, key, mid + 1, max) 

i = 128 
#for i in range(128, 2097152): 
while i <= 2097152: 
    sTime = time.time() 
    myArray = [None] * (i-1) 
    for k in range(0, i-1): 
     myArray[k] = 13 
    eTime = time.time() 
    k = 0 
    startTime = time.time() 
    for k in range(0, 8000000): 
     binarySearch(myArray, 100, 0, i-1) 
    endTime = time.time() 
    print("[Size = ", i, "] 8,000,000 Unsucessful Searches took ", endTime - startTime, " seconds\n") 
    i = i*4

來源

2015-09-07 timbot

對於c/C++ 3的3s對於2 * 10^6大小的數組的二進制搜索也太多了。理想情況下，應該花費不到半秒。 – vish4071

這是python2.x嗎？「範圍內的k（0，8000000）」將是一個非常昂貴的調用 - 如果使用'xrange'代替，會發生什麼？ – mgilson

哦...你也在做8e6搜索。（我沒有看到那部分）。那好吧。你的算法實現沒有問題。 – vish4071

有解決與Python的性能問題的方法有兩種：

使用C和Python C API或Cython。
使用盡可能多的內置功能，你可以優化你的代碼，然後給代碼PyPy

如果我們採取第二種方式（請注意：//操盤的int，list generator加快列表和PEP8格式）：

import time 


def binary_search(array, key, min_, max_): 
    mid = min_ + ((max_ - min_) // 2) 
    if min_ >= max_: 
     return False 
    elif array[mid] == key: 
     return True 
    elif array[mid] > key: 
     return binary_search(array, key, min_, mid - 1) 
    elif array[mid] < key: 
     return binary_search(array, key, mid + 1, max_) 

i = 128 
magic = 13 
my_array = [magic for _ in range(i-1)] 
while i <= 2097152: 
    k = 0 
    start_time = time.time() 
    for k in range(0, 8000000): 
     binary_search(my_array, 100, 0, i-1) 
    end_time = time.time() 
    print("[Size = ", i, "] 8,000,000 Unsucessful Searches took ", end_time - start_time, " seconds\n") 

    s_time = time.time() 
    my_array += [magic for _ in range(3 * i)] 
    i = i*4 
    e_time = time.time()

畢竟，這是我從PyPy得到：

D:\>pypy test.py 
[Size = 128 ] 8,000,000 Unsucessful Searches took 0.1699998378753662 seconds 
[Size = 512 ] 8,000,000 Unsucessful Searches took 0.9229998588562012 seconds 
[Size = 2048 ] 8,000,000 Unsucessful Searches took 1.0799999237060547 seconds 
[Size = 8192 ] 8,000,000 Unsucessful Searches took 1.2969999313354492 seconds 
[Size = 32768 ] 8,000,000 Unsucessful Searches took 1.5120000839233398 seconds 
[Size = 131072 ] 8,000,000 Unsucessful Searches took 1.7920000553131104 seconds 
[Size = 524288 ] 8,000,000 Unsucessful Searches took 2.062000036239624 seconds 
[Size = 2097152 ] 8,000,000 Unsucessful Searches took 2.236999988555908 seconds

來源

2015-09-07 06:28:36 Vovanrock2002

請記住，C/C++是編譯語言，Python是一種解釋型語言。 Python不僅執行指令，而且還讀取它們並將它們即時轉換爲可執行代碼。減慢的另一個原因是循環結構本身。 1000的性能比並不是很奇怪。

來源

2015-09-07 06:45:59

我只需要解釋我在C，C++和Python之間的時間差異。我應該注意到Python是一個解釋的並執行指令，並且還讀取它們並將它們轉換爲可執行代碼？ – timbot

是的，還有什麼？ –

Python遞歸二進制搜索功能

回答

相關問題