Эффективный способ поиска индекса интервала

Question

Я пишу сплайновый класс в Python. Для вычисления интерполированного значения сплайна требуется индекс ближайших точек данных x. В настоящее время упрощенная версия выглядит следующим образом:

def evaluate(x): 
    for ii in range(N): # N = len(x_data) 
     if x_data[ii] <= x <= x_data[ii+1]: 
      return calc(x,ii) 

Так перебирает список x_data точек, пока он не найдет более низкий индекс ii интервала, в которых x ложь и использует в функции calc, которая выполняет сплайн-интерполяции , В то время как функциональный, похоже, что это было бы неэффективно для больших массивов x_data, если x близко к концу набора данных. Есть ли более эффективный или элегантный способ выполнения той же функциональности, которая не требует, чтобы каждый интервал был проверен итеративно?

Примечание: x_data можно считать сортированным таким образом x_data[ii] < x_data[ii+1], но не обязательно равномерно распределенным.

Answer 1

это именно то, что разрез`ать для https://docs.python.org/2/library/bisect.html

from bisect import bisect 
index = bisect(x_data,x) 
#I dont think you actually need the value of the 2 closest but if you do here it is 
point_less = x_data[index-1] # note this will break if its index 0 so you probably want a special case for that 
point_more = x_data[index] 

closest_value = min([point_less,point_more],key=lambda y:abs(x-y)) 

в качестве альтернативы следует использовать бинарный поиск (на самом деле им очень уверен, что тот, что Bisect использует под капотом) .... это должно быть худший случай O(log n) (если ваш входной массив уже отсортирован)