¿Por qué la función de búsqueda binaria incorporada de python se ejecuta mucho más rápido?

binary-search

Question

(Ya contestado por el comentario de sharth.)

He escrito un algoritmo de búsqueda binaria en python, que más o menos sigue la misma estructura que la función bisect_left que se encuentra en el módulo bisect. De hecho, tiene un par de condiciones menos, ya que sé que el punto más alto será la longitud de la lista y el más bajo será 0. Sin embargo, por alguna razón, la función incorporada se ejecuta 5 veces más rápido que la mía.

Mi código es el siguiente:

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

El código fuente de la función incorporada es:

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

Como puedes ver, prácticamente idéntico. Sin embargo, el tiempo de espera agotado para mi función (buscando el último término en una lista ordenada de 100,000 palabras) es -3.60012054443e-05, mientras que la función incorporada alcanza -6.91413879395e-06. ¿Qué explica esta diferencia?

En el código fuente hay un comentario al final que dice "Sobrescribir las definiciones anteriores con una implementación rápida de C". ¿Es esto lo que explica la diferencia? Si es así, ¿cómo podría crear un módulo precompilado de este tipo?

Cualquier consejo es muy apreciado.

Answer 1

Para resumir los comentarios anteriores, de modo que la pregunta pueda cerrarse, la razón por la que el módulo incorporado es más rápido es porque los módulos están precompilados en c. Básicamente, existen dos opciones para intentar replicar dicho rendimiento, una es usar un compilador JIT como PyPy donde la compilación se realiza en tiempo de ejecución, la otra es compilar sus propios módulos en C, usar Cython o alguna otra variante para integrar el Código C con python. El enlace de sharth arriba al código c para bisect es particularmente útil y se puede encontrar hg.python.org/cpython/file/0199bff14c5c/Modules/_bisectmodule.c . Gracias de nuevo por toda la ayuda.