Время, прошедшее между линейным поиском и двоичным поиском с использованием Python

Question

Мне нужна помощь с моим кодом Python.

Я сделал две функции ниже, одну для последовательного (линейного) поиска и другую для двоичного поиска.

Я хочу сделать эти 3 вещи для каждого значения размера в данном списке:

1) создать список случайных целочисленных значений (от 1 до 1000,0000) для заданного размера списка

2) запустить последовательный поиск -1 в списке и записать время, прошедшее последовательным поиском

3) запустить двоичный поиск -1 в отсортированном списке (после сортировки списка) и записать время, прошедшее двоичным поиском

То, что я сделал, это:

def sequentialSearch(alist, item):
    pos = 0
    found = False

    while pos < len(alist) and not found:
        if alist[pos] == item:
            found = True
        else:
            pos = pos + 1

    return found

def binSearch(list, target):
    list.sort()
    return binSearchHelper(list, target, 0, len(list) - 1)

def binSearchHelper(list, target, left, right):
    if left > right:
        return False

    middle = (left + right)//2
    if list[middle] == target:
        return True
    elif list[middle] > target:
        return binSearchHelper(list, target, left, middle - 1)
    else:
        return binSearchHelper(list, target, middle + 1, right)

import random
import time
list_sizes = [10,100,1000,10000,100000,1000000]
for size in list_sizes:
    list = []
    for x in range(size):
        list.append(random.randint(1,10000000))

    sequential_search_start_time = time.time()
    sequentialSearch(list,-1)
    sequential_search_end_time = time.time()
    print("Time taken by linear search is = ",(sequential_search_end_time-sequential_search_start_time))

    binary_search_start_time = time.time()
    binSearch(list,-1)
    binary_search_end_time = time.time()
    print("Time taken by binary search is = ",(binary_search_end_time-binary_search_start_time))

    print("\n")

Вывод, который я получаю:

Как мы знаем, бинарный поиск намного быстрее, чем линейный поиск. Итак, я просто хочу знать, почему он показывает, что время, потребляемое бинарным поиском, больше, чем время, затрачиваемое на линейный поиск?

Answer 1

1) Вам необходимо учесть время сортировки. Бинарный поиск работает только в отсортированных списках, поэтому сортировка занимает много времени, а сложность - до O(nlogn). И в вашем случае вы сортируете его после запуска таймера, так что он будет выше.

2) Вы ищете элемент, которого нет в списке, т.е. -1, что не является средним показателем для бинарного поиска. В худшем случае при бинарном поиске приходится совершать столько прыжков, чтобы никогда не найти элемент.

3) Пожалуйста, не используйте list в качестве переменной, это ключевое слово python, и вы явно его переопределяете. Используйте что-нибудь еще.

Теперь, если вы сортируете список без учета времени. Результаты резко меняются. Вот мой.

Time taken by linear search is =  9.059906005859375e-06
Time taken by binary search is =  8.58306884765625e-06


Time taken by linear search is =  1.2159347534179688e-05
Time taken by binary search is =  4.5299530029296875e-06


Time taken by linear search is =  0.00011110305786132812
Time taken by binary search is =  5.9604644775390625e-06


Time taken by linear search is =  0.0011129379272460938
Time taken by binary search is =  8.344650268554688e-06


Time taken by linear search is =  0.011270761489868164
Time taken by binary search is =  1.5497207641601562e-05


Time taken by linear search is =  0.11133551597595215
Time taken by binary search is =  1.7642974853515625e-05

Что я сделал, так это просто отсортировал список, прежде чем он был рассчитан. Путь, путь лучше, чем если бы вам пришлось сортировать и искать все сразу.