Сводка ответа : Если у вас есть отсортированный array, то код деления пополам (приведенный ниже) выполняется быстрее всего. ~ 100-1000 раз быстрее для больших массивов и ~ 2-100 раз быстрее для маленьких массивов. Это также не требует NumPy.
Если у вас есть несортированная array, то, если array велико, следует сначала рассмотреть использование сортировки O (n logn), а затем разделить пополам, а если array мало, то метод 2 кажется самым быстрым.
Сначала вы должны уточнить, что вы подразумеваете под ближайшим значением . Часто требуется интервал в абсциссе, например, массив = [0,0.7,2.1], значение = 1,95, ответом будет idx = 1. Я подозреваю, что это именно тот случай (в противном случае следующее очень легко можно изменить с помощью условного оператора последующего действия, как только вы найдете интервал). Я отмечу, что оптимальный способ сделать это - разделить пополам (что я предоставлю первым - заметьте, что он вообще не требует numpy и работает быстрее, чем использование numpy функций, поскольку они выполняют избыточные операции). Затем я приведу сравнение времени с другими, представленными здесь другими пользователями.
Bisection:
def bisection(array,value):
'''Given an ``array`` , and given a ``value`` , returns an index j such that ``value`` is between array[j]
and array[j+1]. ``array`` must be monotonic increasing. j=-1 or j=len(array) is returned
to indicate that ``value`` is out of range below and above respectively.'''
n = len(array)
if (value < array[0]):
return -1
elif (value > array[n-1]):
return n
jl = 0# Initialize lower
ju = n-1# and upper limits.
while (ju-jl > 1):# If we are not yet done,
jm=(ju+jl) >> 1# compute a midpoint with a bitshift
if (value >= array[jm]):
jl=jm# and replace either the lower limit
else:
ju=jm# or the upper limit, as appropriate.
# Repeat until the test condition is satisfied.
if (value == array[0]):# edge cases at bottom
return 0
elif (value == array[n-1]):# and top
return n-1
else:
return jl
Теперь я определю код из других ответов, каждый из которых возвращает индекс:
import math
import numpy as np
def find_nearest1(array,value):
idx,val = min(enumerate(array), key=lambda x: abs(x[1]-value))
return idx
def find_nearest2(array, values):
indices = np.abs(np.subtract.outer(array, values)).argmin(0)
return indices
def find_nearest3(array, values):
values = np.atleast_1d(values)
indices = np.abs(np.int64(np.subtract.outer(array, values))).argmin(0)
out = array[indices]
return indices
def find_nearest4(array,value):
idx = (np.abs(array-value)).argmin()
return idx
def find_nearest5(array, value):
idx_sorted = np.argsort(array)
sorted_array = np.array(array[idx_sorted])
idx = np.searchsorted(sorted_array, value, side="left")
if idx >= len(array):
idx_nearest = idx_sorted[len(array)-1]
elif idx == 0:
idx_nearest = idx_sorted[0]
else:
if abs(value - sorted_array[idx-1]) < abs(value - sorted_array[idx]):
idx_nearest = idx_sorted[idx-1]
else:
idx_nearest = idx_sorted[idx]
return idx_nearest
def find_nearest6(array,value):
xi = np.argmin(np.abs(np.ceil(array[None].T - value)),axis=0)
return xi
Теперь я буду время коды:
Примечание методы 1,2,4,5 не дают правильный интервал. Методы 1,2,4 округляют до ближайшей точки в массиве (например,> = 1,5 -> 2), а метод 5 всегда округляет (например, 1,45 -> 2). Только методы 3, 6 и, конечно, деление пополам дают правильный интервал.
array = np.arange(100000)
val = array[50000]+0.55
print( bisection(array,val))
%timeit bisection(array,val)
print( find_nearest1(array,val))
%timeit find_nearest1(array,val)
print( find_nearest2(array,val))
%timeit find_nearest2(array,val)
print( find_nearest3(array,val))
%timeit find_nearest3(array,val)
print( find_nearest4(array,val))
%timeit find_nearest4(array,val)
print( find_nearest5(array,val))
%timeit find_nearest5(array,val)
print( find_nearest6(array,val))
%timeit find_nearest6(array,val)
(50000, 50000)
100000 loops, best of 3: 4.4 µs per loop
50001
1 loop, best of 3: 180 ms per loop
50001
1000 loops, best of 3: 267 µs per loop
[50000]
1000 loops, best of 3: 390 µs per loop
50001
1000 loops, best of 3: 259 µs per loop
50001
1000 loops, best of 3: 1.21 ms per loop
[50000]
1000 loops, best of 3: 746 µs per loop
Для большого массива бисекция дает 4us по сравнению со следующими лучшими 180us и самой длинной 1,21 мс (~ 100 - 1000 раз быстрее). Для небольших массивов это в 2-100 раз быстрее.