Почему python, встроенный в функцию бинарного поиска, работает намного быстрее?

(Уже ответил комментарий sharth.)

Я написал алгоритм бинарного поиска в python, который более или менее следует той же структуре, что и функция bisect_left, найденная в модуле bisect. На самом деле он имеет несколько меньших условностей, так как я знаю, что верхняя точка будет длиной списка, а нижним будет 0. Но по какой-то причине встроенная функция работает в 5 раз быстрее, чем моя.

Мой код выглядит следующим образом:

def bisection_search(word, t):

    high = len(t)
    low = 0

    while low < high:
        half = (high+low)/2
        if t[half] < word:
            low = half + 1
        else:
            high = half
    return low

Исходный код встроенной функции:

def bisect_left(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    return lo

Как вы можете видеть, практически идентичны. Тем не менее тайм-аут, поставленный для моей функции (поиск последнего слагаемого в упорядоченном списке из 100 000 слов), составляет -3.60012054443e-05, где, как встроенный, достигает -6.91413879395e-06. Чем объясняется эта разница?

В исходном коде в конце есть комментарий, в котором говорится: "Переписать выше определения с быстрой реализацией C" - вот что объясняет разницу? Если да, то как я могу создать такой предварительно скомпилированный модуль?

Приветствуются любые советы.

Ответы

Ответ 1

Чтобы суммировать замечания выше, поэтому вопрос может быть закрыт, причина, по которой встроенный модуль быстрее, состоит в том, что модули предварительно скомпилированы в c. В принципе, есть две возможности попытаться воспроизвести такую ​​производительность: использовать JIT-компилятор, такой как PyPy, где компиляция выполняется во время выполнения, другая - скомпилировать ваши собственные модули на C, используя Cython или какой-либо другой вариант для интеграции C с помощью python. Ссылка с sharth выше на c-код для bisect особенно полезна и может быть найдена здесь. Еще раз спасибо за помощь.