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递归二进制搜索功能

回答

相关问题