¿Hay alguna manera de evitar la búsqueda lineal en esto?

Question

Tengo un grupo grande de objetos con número inicial y número final. Por ejemplo:

(999, 2333, data) 
(0, 128, data) 
(235, 865, data) 
... 

Suponiendo que los intervalos no se superponen entre sí. Y estoy escribiendo una función que toma un número y ubica el objeto que (bajo, alto) lo contiene. Digamos 333 dado, quiero los 3er objetos en la lista.

¿Hay alguna manera de hacer esto lo más eficientemente posible, a falta de búsqueda lineal? Estaba pensando en la búsqueda binaria, pero teniendo algunas dificultades para hacer frente a la verificación de rango.

Answer 1

En primer lugar, no está del todo claro que la búsqueda binaria esté garantizada aquí . Es posible que la búsqueda lineal sea más rápida cuando el número de intervalos es pequeño.

Si está preocupado por el rendimiento, lo más prudente que hacer es perfilar el código, y tal vez ambos métodos de referencia en sus entradas típicas.

Renuncias un lado, la búsqueda binaria podría ser implementado por la clasificación de los intervalos de una vez, y luego repetidamente utilizando el módulo bisect a hacer la búsqueda:

import bisect 

intervals = [(999, 2333, 'int1'), (0, 128, 'int2'), (235, 865, 'int3')] 
intervals.sort() 

def find_int(intervals, val): 
    pos = bisect.bisect_left([interval[1] for interval in intervals], val) 
    if pos < len(intervals) and val >= intervals[pos][0]: 
     return intervals[pos] 
    else: 
     return None 

print(find_int(intervals, 0)) 
print(find_int(intervals, 1)) 
print(find_int(intervals, 200)) 
print(find_int(intervals, 998)) 
print(find_int(intervals, 999)) 
print(find_int(intervals, 1000)) 
print(find_int(intervals, 2333)) 
print(find_int(intervals, 2334)) 

En lo anterior, supongo que los intervalos no se solapan , y que el intervalo incluye tanto sus puntos de inicio como de finalización.

Por último, para mejorar el rendimiento, se podría considerar la factorización [interval[1] for interval in intervals] de la función y hacerlo sólo una vez al comienzo.

Answer 2

Piense si vale la pena la clasificación de los datos.
Si solo desea buscar varias veces, no es así, y no puede evitar la búsqueda lineal. la complejidad total de sus búsquedas será O(n*k), donde n es el número de elementos y k es el número de búsquedas.

Si desea buscar un montón de veces, entonces primero debe ordenar, y luego buscar mediante la búsqueda binaria. Será O(nlogn) para ordenar y O(klogn) para buscar k veces, por lo que obtiene un total de O((n+k)logn).

Por lo tanto, la clasificación y luego busca al menor debe hacerse sólo si k>=logn

P. S. Puede usar otro enfoque para ordenar y buscar, como se propone en otras respuestas, en todos los sentidos, la conclusión sigue siendo: solo si k>=logn

Answer 3

Usted puede utilizar el módulo bisect: http://docs.python.org/library/bisect.html

Es necesario ordenar los datos una vez, a continuación, utilizar bisect:

import bisect 
data=None 
tuples=[(0, 128, None), (235, 865, None), (999, 2333, None)] 
tuples.sort() 
print tuples 
print bisect.bisect(tuples, (-1,)) # 0 
print bisect.bisect(tuples, (1,)) # 1 
print bisect.bisect(tuples, (333,)) # 2 
print bisect.bisect(tuples, (3333,)) # 3 

Answer 4

Si la velocidad de búsqueda es de suma importancia, a continuación, puede crear una Mira- up table (como ya lo comentó S.Lott).Esto se llevará a O (r) memoria (donde r es el tamaño de la gama), O (r) Tiempo de pre-procesamiento, y O (1) tiempo de búsqueda. Cree una matriz del tamaño del rango y rellene cada elemento con un puntero a los datos o nulo.

lookup = {} 
for low, high, data in source_ranges: 
    for i in range(low,high): # or maybe high+1 if the ranges are inclusive 
     lookup[i] = data 

Ahora la búsqueda es trivial.