Есть ли способ избежать линейного поиска?

Question

У меня есть большой пул объектов с начальным номером и конечным числом. Например:

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

Предполагая, что интервалы не пересекаются друг с другом. И я пишу функцию, которая принимает число и находит объект, который (низкий, высокий) содержит его. Скажем, 333, мне нужны 3-й объект в списке.

Есть ли способ, который я могу сделать это максимально эффективно, нежели линейный поиск? Я думал о бинарном поиске, но имел некоторые трудности с проверкой диапазона.

Answer 1

Прежде всего, не совсем ясно, что двоичный поиск здесь оправдан , Вполне возможно, что линейный поиск выполняется быстрее, когда количество интервалов невелико.

Если вас беспокоит производительность, разумная задача - профилировать код и, возможно, сравнить оба метода на ваших типичных входах.

Отказ в сторону, бинарный поиск может быть реализован путем сортировки интервалов один раз, а затем многократно используя bisect модуль для выполнения поиска:

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)) 

В выше, я полагаю, что интервалы не перекрываются , и что этот интервал включает как начальную, так и конечную точки.

Наконец, чтобы повысить производительность, можно было бы рассмотреть факторинг [interval[1] for interval in intervals] вне функции и сделать это только один раз в начале.

Answer 2

Подумайте, стоит ли сортировать данные.
Если вы хотите только несколько раз искать, то это не так - и вы не можете избежать линейного поиска. общая сложность ваших поисков будет O(n*k), где n - количество элементов, а k - количество поисков.

Если вы хотите много раз искать, то сначала вам нужно отсортировать, а затем выполнить поиск с помощью двоичного поиска. Это будет O(nlogn) для сортировки и O(klogn) для поиска k раз, поэтому вы получите общее количество O((n+k)logn).

Таким образом, сортировка, тогда поиск должно быть сделано только в том случае k>=logn

P.S. Вы можете использовать другой подход для сортировки и поиска, как это предлагается в других ответах, по-прежнему остаётся: делать это только в том случае, если k>=logn

Answer 3

Вы можете использовать модуль Bisect: http://docs.python.org/library/bisect.html

Вы должны сортировать данные один раз, а затем использовать 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

Если скорость поиска имеет первостепенное значение, то вы можете создать look- (как уже прокомментировал С.Лотт).Это займет O (R) память (где г является размер диапазона), О (г) Время предварительной обработки, а также O (1) поиск по времени. Создайте массив размера диапазона и заполните каждый элемент указателем на данные или null.

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 

Теперь поиск является тривиальным.