Dlaczego moje wyszukiwanie bisekcji jest wolniejsze niż wyszukiwanie liniowe w pythonie?

Question

Zostałem poproszony podczas wywiadu o wdrożenie wyszukiwania bisekcji w celu poprawy czasu wyszukiwania i wpadłem na to. Wróciłem do domu i przetestowałem go, ale wygląda na to, że wyszukiwanie liniowe działa lepiej niż moje poszukiwania bisekcji. Czy zrobiłem coś złego tutaj?

import time 

sorted_list = range(0, 10000000) 
needle = 9999999 

def split_list(sorted_list): 
    half = len(sorted_list)/2 
    return sorted_list[:half], sorted_list[half:] 

def bisection(haystack, needle, length_of_list): 
    if len(haystack) <= length_of_list/5: 
     return haystack 

    first, last = split_list(haystack) 
    if needle < first[-1]: 
     return bisection(first, needle, length_of_list) 
    else: 
     return bisection(last, needle, length_of_list) 

def linear_search(smaller_ist): 
    for ele in smaller_list: 
     if ele == needle: 
      return 0 

start_time = time.time() 
smaller_list = bisection(sorted_list, needle, len(sorted_list)) 
print linear_search(smaller_list) 
print("--- %s seconds ---" % (time.time() - start_time)) 

start_time = time.time() 
print linear_search(sorted_list) 
print("--- %s seconds ---" % (time.time() - start_time)) 

Answer 1

List slicing wynosi O (k), gdzie k jest długością wycinka otrzymujesz. Wielokrotnie wycinałeś listę w split_list(), w linii return sorted_list[:half], sorted_list[half:]. Wywołanie najwyższego poziomu do bisection, które wywołuje split_list() na całej liście, zajmie O (n) tylko po to, aby uruchomić split_list (od rozmiaru lewej połowy + rozmiaru prawej połowy = n), która sama już jest dopasowana czas złożoności wyszukiwania liniowego.

Jednym ze sposobów, aby ominąć to, zamiast listy krojenie, przechodzą wokół się lowerBound i upperBound w rekurencyjnych wywołań swojej funkcji (gdzie wywołanie najwyższego poziomu używa lowerBound i upperBound zestaw do 0 i len(sorted_list) odpowiednio). I length_of_list będzie upperBound - lowerBound.