Trouver la valeur la plus proche dans le tableau de numpy
13 réponses
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
si votre tableau est trié et est très grand, c'est une solution beaucoup plus rapide:
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]
cette échelle à de très grands tableaux. Vous pouvez facilement modifier ce qui précède pour trier dans la méthode si vous ne pouvez pas supposer que le tableau est déjà trié. C'est exagéré pour les petits tableaux, mais une fois qu'ils deviennent grands, c'est beaucoup plus rapide.
avec une légère modification, la réponse ci-dessus fonctionne avec des tableaux de dimensions arbitraires (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]
Ou, écrite sur une seule ligne:
a.flat[np.abs(a - a0).argmin()]
voici une extension pour trouver le vecteur le plus proche dans un tableau de vecteurs.
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])
résumé de la réponse : si on a un array trié, alors le code de bisection (indiqué ci-dessous) est le plus rapide. ~100-1000 fois plus rapide pour les grands tableaux, et ~2-100 fois plus rapide pour les petits tableaux. Il n'a pas besoin non plus numpy.
Si vous avez un array non trié, alors si array est grand, on devrait d'abord envisager d'utiliser un tri O(N logn), puis une coupe en deux, et si array est petit, alors la méthode 2 semble la plus rapide.
vous devez d'abord préciser ce que vous entendez par la valeur la plus proche . Souvent on veut l'intervalle dans un abscisse, par exemple tableau=[0,0.7,2.1], Valeur = 1.95, la réponse serait idx=1. C'est le cas que je soupçonne que vous avez besoin (autrement ce qui suit peut être modifié très facilement avec une déclaration conditionnelle de suivi une fois que vous trouvez l'intervalle). Je vais noter que la meilleure façon d'effectuer ceci est avec bisection (que je fournirai d'abord-Notez qu'il ne nécessite pas de numpy du tout et est plus rapide que l'utilisation des fonctions numpy parce qu'ils effectuent des opérations redondantes). Ensuite, je vais fournir une comparaison de temps par rapport aux autres présentés ici par d'autres utilisateurs.
Bissection:
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
maintenant je vais définir le code à partir des autres réponses, ils renvoient chacun un index:
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
maintenant je vais chronométrer les codes: Note méthodes 1,2,4,5 ne donnent pas correctement l'intervalle. Méthodes 1,2,4 ronde au point le plus proche dans le tableau (par exemple >=1,5 -> 2), et la méthode 5 arrondit toujours vers le haut (par exemple 1,45 -> 2). Seules les méthodes 3, et 6, et bien sûr la section donnent l'intervalle correctement.
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
pour un grand réseau bisection donne 4us comparé au meilleur 180us suivant et le plus long 1,21 ms (~100 - 1000 fois plus rapide). Pour les plus petits tableaux, il est ~2-100 fois plus rapide.
Si vous ne voulez pas utiliser numpy cela fera:
def find_nearest(array, value):
n = [abs(i-value) for i in array]
idx = n.index(min(n))
return array[idx]
Voici une version avec scipy pour @Arionasafari, réponse " pour trouver le vecteur le plus proche dans un tableau de vecteurs
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])
Voici une version qui traitera un tableau de "valeurs" non-scalaire:
import numpy as np
def find_nearest(array, values):
indices = np.abs(np.subtract.outer(array, values)).argmin(0)
return array[indices]
ou une version qui renvoie un type numérique (par exemple int, float) si l'entrée est scalaire:
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]
pour les grands tableaux, la (excellente) réponse donnée par @Demitri est beaucoup plus rapide que la réponse actuellement marquée comme meilleure. J'ai adapté Son algorithme exact de deux façons:
-
la fonction ci-dessous fonctionne que le tableau d'entrée soit ou non trié.
-
la fonction ci-dessous renvoie le index du tableau d'entrées correspondant à la valeur la plus proche, qui est quelque peu plus général.
notez que la fonction ci-dessous gère également un cas de bord spécifique qui conduirait à un bug dans la fonction originale écrite par @Demitri. Sinon, mon algorithme est identique au sien.
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
Voici une version vectorisée rapide de la solution de @Dimitri si vous avez beaucoup de values à rechercher ( values peut être un tableau multidimensionnel):
#`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]
Repères
> 100 fois plus rapide qu'une boucle for avec la solution de @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
je pense que la façon la plus pythonique serait:
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)
c'est le code de base. Vous pouvez l'utiliser comme une fonction si vous voulez ""
toutes les réponses sont bénéfiques pour recueillir l'information pour écrire du code efficace. Cependant, j'ai écrit un petit script Python pour l'optimiser dans divers cas. Ce sera le meilleur cas si le tableau fourni est trié. Si l'on recherche l'index du point le plus proche d'une valeur spécifiée, alors le module bisect est le plus efficace dans le temps. Lorsqu'on recherche les indices correspondant à un tableau, le numpy searchsorted est le plus efficace.
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)
dans [63]: %temps coupent.bisect_left(xlist, 0.3) Temps CPU: utilisateur 0 ns, sys: 0 ns, total: 0 ns Temps de paroi: 22.2 µs
np.searchsorted(xar, 0.3, side="left")
Dans [64]: %de temps de np.searchsorted(xar, 0.3, côté="gauche") Temps CPU: utilisateur 0 ns, sys: 0 ns, total: 0 ns Temps de paroi: 98.9 µs
randpts = np.random.rand(1000)
np.searchsorted(xar, randpts, side="left")
%temps de np.searchsorted(xar, randpts, côté="gauche") Temps CPU: utilisateur 4 ms, sys: 0 ns, total: 4 ms Durée du mur: 1,2 ms
si nous suivons la règle multiplicative, alors numpy devrait prendre ~100 ms ce qui implique ~83X plus rapide.
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))