Рекурсивная функция двоичного поиска Python

Question

Q: в основном ... создать алгоритм двоичного поиска, который является одним и тем же (кроме языка программирования) на трех разных языках для тех же 8 000 000 безуспешных поисков для восьми массивов разного размера (128, 512, ..., 52428, (524288 * 4) = 2097152). Первые два языка, в которых я закодировал эту проблему, были C и C++ и получили нормальные результаты: не более 3s для массива размера 2097152

Я решил попробовать 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) п): в среднем каждый рекурсивный проверка занимает 114s

.

Это моя первая кодировка в Python, поэтому мне было интересно: мой код THAT неэффективен (хотя алгоритм чрезвычайно простой), или Python не способен обрабатывать рекурсивные вызовы, а также говорить C/C++/Java, особенно когда они мой питон код ниже:

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 

Answer 1

Есть два пути решения проблемы с производительностью 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 

Answer 2

Имейте в виду, что C/C++ - это скомпилированные языки, а Python - интерпретируемый. Python не просто выполняет инструкции, но также читает их и переводит их в исполняемый код на лету. Другой причиной замедления является сама конструкция цикла. Коэффициент производительности 1000 не очень странный.