13 ответов:
import numpy as np def find_nearest(array, value): array = np.asarray(array) idx = (np.abs(array - value)).argmin() return array[idx] array = np.random.random(10) print(array) # [ 0.21069679 0.61290182 0.63425412 0.84635244 0.91599191 0.00213826 # 0.17104965 0.56874386 0.57319379 0.28719469] value = 0.5 print(find_nearest(array, value)) # 0.568743859261
Если Ваш массив отсортирован и очень большой, это гораздо более быстрое решение:
def find_nearest(array,value): idx = np.searchsorted(array, value, side="left") if idx > 0 and (idx == len(array) or math.fabs(value - array[idx-1]) < math.fabs(value - array[idx])): return array[idx-1] else: return array[idx]это масштабируется до очень больших массивов. Вы можете легко изменить приведенное выше для сортировки в методе, если вы не можете предположить, что массив уже отсортирован. Это перебор для небольших массивов, но как только они становятся большими, это намного быстрее.
С небольшой модификацией ответ выше работает с массивами произвольной размерности (1d, 2d, 3d, ...):
def find_nearest(a, a0): "Element in nd array `a` closest to the scalar value `a0`" idx = np.abs(a - a0).argmin() return a.flat[idx]или, написанный как одна строка:
a.flat[np.abs(a - a0).argmin()]
вот расширение, чтобы найти ближайший вектор в массиве векторов.
import numpy as np def find_nearest_vector(array, value): idx = np.array([np.linalg.norm(x+y) for (x,y) in array-value]).argmin() return array[idx] A = np.random.random((10,2))*100 """ A = array([[ 34.19762933, 43.14534123], [ 48.79558706, 47.79243283], [ 38.42774411, 84.87155478], [ 63.64371943, 50.7722317 ], [ 73.56362857, 27.87895698], [ 96.67790593, 77.76150486], [ 68.86202147, 21.38735169], [ 5.21796467, 59.17051276], [ 82.92389467, 99.90387851], [ 6.76626539, 30.50661753]])""" pt = [6, 30] print find_nearest_vector(A,pt) # array([ 6.76626539, 30.50661753])
резюме ответа: если у вас есть сортированный
arrayтогда код деления пополам (приведенный ниже) выполняет самый быстрый. ~100-1000 раз быстрее для больших массивов, и ~2-100 раз быстрее для небольших массивов. Он также не требует numpy. Если у вас есть несортированныйarrayтогда, еслиarrayбольшой, следует рассмотреть сначала использование сортировки O (n logn), а затем деление пополам, и еслиarrayмал, то метод 2 кажется самым быстрым.во-первых, вы должны уточнить, что вы подразумеваете под ближайшим значением. Часто требуется интервал в абсциссе, например array=[0,0. 7,2.1], value=1,95, ответ будет idx=1. Это тот случай, который я подозреваю, что вам нужно (в противном случае следующее Может быть очень легко изменено с помощью условного оператора followup, как только вы найдете интервал). Я отмечу, что оптимальный способ выполнить это-с помощью bisection (который я предоставлю сначала-обратите внимание, что он вообще не требует numpy и быстрее, чем использование функций numpy, потому что они выполняют лишние операции). Затем я приведу сравнение времени с другими, представленными здесь другими пользователями.
деление пополам:
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для большого массива bisection дает 4us по сравнению со следующим лучшим 180us и самым длинным 1.21 ms (~100 - 1000 раз быстрее). Для небольших массивов это ~2-100 раз быстрее.
Если вы не хотите использовать numpy, это сделает это:
def find_nearest(array, value): n = [abs(i-value) for i in array] idx = n.index(min(n)) return array[idx]
вот версия с scipy для @Ari Onasafari, ответ"чтобы найти ближайший вектор в массиве векторов"
In [1]: from scipy import spatial In [2]: import numpy as np In [3]: A = np.random.random((10,2))*100 In [4]: A Out[4]: array([[ 68.83402637, 38.07632221], [ 76.84704074, 24.9395109 ], [ 16.26715795, 98.52763827], [ 70.99411985, 67.31740151], [ 71.72452181, 24.13516764], [ 17.22707611, 20.65425362], [ 43.85122458, 21.50624882], [ 76.71987125, 44.95031274], [ 63.77341073, 78.87417774], [ 8.45828909, 30.18426696]]) In [5]: pt = [6, 30] # <-- the point to find In [6]: A[spatial.KDTree(A).query(pt)[1]] # <-- the nearest point Out[6]: array([ 8.45828909, 30.18426696]) #how it works! In [7]: distance,index = spatial.KDTree(A).query(pt) In [8]: distance # <-- The distances to the nearest neighbors Out[8]: 2.4651855048258393 In [9]: index # <-- The locations of the neighbors Out[9]: 9 #then In [10]: A[index] Out[10]: array([ 8.45828909, 30.18426696])
вот версия, которая будет обрабатывать не скалярный массив "values":
import numpy as np def find_nearest(array, values): indices = np.abs(np.subtract.outer(array, values)).argmin(0) return array[indices]или версия, которая возвращает числовой тип (например, int, float), если вход скалярный:
def find_nearest(array, values): values = np.atleast_1d(values) indices = np.abs(np.subtract.outer(array, values)).argmin(0) out = array[indices] return out if len(out) > 1 else out[0]
для больших массивов (отличный) ответ, данный @Demitri, намного быстрее, чем ответ, отмеченный в настоящее время как лучший. Я адаптировал его точный алгоритм следующим образом:
функция ниже работает независимо от того, сортируется ли входной массив.
функция ниже возвращает индекс входного массива, соответствующего ближайшему значению, которое является несколько более общим.
Примечание. что функция ниже также обрабатывает конкретный крайний случай, который приведет к ошибке в исходной функции, написанной @Demitri. В противном случае, мой алгоритм идентичен его.
def find_idx_nearest_val(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
вот быстрая векторизованная версия решения @Dimitri, если у вас есть много
valuesискать (valuesможет быть многомерным массивом):#`values` should be sorted def get_closest(array, values): #make sure array is a numpy array array = np.array(array) # get insert positions idxs = np.searchsorted(array, values, side="left") # find indexes where previous index is closer prev_idx_is_less = ((idxs == len(array))|(np.fabs(values - array[np.maximum(idxs-1, 0)]) < np.fabs(values - array[np.minimum(idxs, len(array)-1)]))) idxs[prev_idx_is_less] -= 1 return array[idxs]критерии
> 100 раз быстрее, чем при использовании
forцикл с решением @ Demitri'>>> %timeit ar=get_closest(np.linspace(1, 1000, 100), np.random.randint(0, 1050, (1000, 1000))) 139 ms ± 4.04 ms per loop (mean ± std. dev. of 7 runs, 10 loops each) >>> %timeit ar=[find_nearest(np.linspace(1, 1000, 100), value) for value in np.random.randint(0, 1050, 1000*1000)] took 21.4 seconds
Я думаю, что наиболее подходящие для Python способ:
num = 65 # Input number array = n.random.random((10))*100 # Given array nearest_idx = n.where(abs(array-num)==abs(array-num).min())[0] # If you want the index of the element of array (array) nearest to the the given number (num) nearest_val = array[abs(array-num)==abs(array-num).min()] # If you directly want the element of array (array) nearest to the given number (num)Это основной код. Вы можете использовать его в качестве функции, если вы хотите
все ответы полезны для сбора информации для написания эффективного кода. Тем не менее, я написал небольшой скрипт Python для оптимизации для различных случаев. Это будет лучший случай, если массив не будет отсортирован. Если искать индекс ближайшей точки заданного значения, то
bisectмодуль является наиболее эффективным. При одном поиске индексы соответствуют массиву,numpy searchsortedнаиболее эффективен.import numpy as np import bisect xarr = np.random.rand(int(1e7)) srt_ind = xarr.argsort() xar = xarr.copy()[srt_ind] xlist = xar.tolist() bisect.bisect_left(xlist, 0.3)в [63]: %времени деления пополам.bisect_left(xlist, 0.3) Время процессора: пользователь 0 НС, система: 0 НС, всего: 0 НС Настенное время: 22,2 МКС
np.searchsorted(xar, 0.3, side="left")In [64]: %time np.searchsorted(xar, 0.3, side= " left") Время процессора: пользователь 0 НС, система: 0 НС, всего: 0 НС Время стены: 98,9 МКС
randpts = np.random.rand(1000) np.searchsorted(xar, randpts, side="left")%time np.searchsorted(xar, randpts, side= " left") Время процессора: пользователь 4 мс, система: 0 НС, всего: 4 мс Стены время: 1,2 МС
если мы следуем мультипликативному правилу, то numpy должен занять ~100 мс, что означает ~83X быстрее.
import numpy as np def find_nearest(array, value): array = np.array(array) z=np.abs(array-value) y= np.where(z == z.min()) m=np.array(y) x=m[0,0] y=m[1,0] near_value=array[x,y] return near_value array =np.array([[60,200,30],[3,30,50],[20,1,-50],[20,-500,11]]) print(array) value = 0 print(find_nearest(array, value))
Comments