2

Читаю "Грокаем алгоритмы" и сразу возник вопрос про бинарный поиск. Написал код для проверки за сколько времени найдет элемент в списке встроенный метод list.index и за сколько находит бинарный поиск. И вот собственно мой вопрос: почему встроенный метод работает в 2.5 раза быстрее чем бинарный поиск? Что то не так с моим кодом? Или встроенный метод имеет более быстрый алгоритм (а если так, то на каком алгоритме он реализован?)? В общем помогите разобраться.

#!usr/bin/env python3
# -*- coding: utf-8 -*-

import time

#декоратор бенчмарк
def bench(func):
    def wrapper():
        start = time.time()
        func()
        end = time.time()
        print('{}'.format(end - start))
    return wrapper

#генерируем список
def gen_list():
    big_list = []
    x = 1
    while len(big_list) != 10000000:
        big_list.append(x)
        x += 1
    return big_list

#время нахождение методом индекс
@bench
def search_index():
    big_list = gen_list()
    dx = big_list.index(5000001)
    return dx

#время нахождения бинарным поиском
@bench
def binary_search():
    low = 0
    high = len(gen_list()) - 1
    l = list(gen_list())

    while low <= high:
        mid = (low + high)
        guess = l[mid]
        if guess == 5000001:
            return mid
        elif guess > 5000001:
            high = mid - 1
        else:
            low = mid + 1
    return None


def main():
    print('')
    print('простой поиск по индексу:')
    search_index()
    print('*' * 20)
    print('бинарный поиск:')
    binary_search()

main()
3
  • 3
    mid = (low + high) — а где деление на 2?
    – Alexey Ten
    28 мая 2020 в 16:03
  • 1
    Ещё вы 2 раза создаёте список 28 мая 2020 в 16:06
  • Самое очевидное — потому что list.index написан не на питоне. Ну а остальное уже Harry рассказал
    – andreymal
    28 мая 2020 в 16:24

1 ответ 1

10

Ну, как минимум, зачем вы дважды генерируете список?

high = len(gen_list()) - 1
l = list(gen_list())

У меня было 2.1 против 4.8 секунды. После замены на

big_list = gen_list()
high = len(big_list) - 1
l = list(big_list)

Стало 2.1 на 2.9. Хорошо бы вынести генерацию из бенчмарка вообще - но это вы уж сами...

Ну, а потом, надо учесть, что встроенный поиск сделан не на Python, что уже несколько поднимает скорость, да он и не выполняет никакой арифметики, только сравнение - а ваш поиск написан на самом Python, не оптимален, etc etc...

А после того, как исправил замеченное @AlexeyTen (сам я, увы, не обратил внимания...) -

mid = (low + high)//2

то соотношение стало 2.1 к 2.0 в пользу бинарного поиска.

8
  • Спасибо за ответ. А теперь меня интересует, почему бинарный поиск оказывается быстрее "встроенного" поиска в списках?) Типо вот вам поиск из коробки, но если хотите быстрее, допишите сами 5 строчек самого простого алгоритма?! 28 мая 2020 в 18:51
  • 2
    Поиск из коробки работает с неупорядоченными списками. А бинарный - только с упорядоченными. Я не спец в Python, но, думаю, в нем тоже есть какой-то встроенный бинарный поиск - для применения, когда известна упорядоченность массива.
    – Harry
    28 мая 2020 в 19:04
  • Вынес генерацию из бенчмарка и бинарный поиск опять стал дольше. :/ 28 мая 2020 в 19:24
  • 1
    @DreamSeller например это l = list(big_list).
    – extrn
    28 мая 2020 в 19:35
  • 1
    @DreamSeller list это конструктор списка, он конструирует список из переданной ему последовательности. В вашем случае он создал список из списка, т.е. сделал неглубокую копию.
    – extrn
    28 мая 2020 в 19:49

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.