Suchen Sie den nächsten Wert im numpy-Array

335

Gibt es eine numpy-thonische Möglichkeit, z. B. eine Funktion, um den nächsten Wert in einem Array zu finden?

Beispiel:

np.find_nearest( array, value )
Fookatchu
quelle

Antworten:

514
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
unutbu
quelle
52
@EOL: return np.abs(array-value).min()gibt die falsche Antwort. Dies gibt Ihnen die min der absoluten Wertentfernung, und irgendwie müssen wir den tatsächlichen Array-Wert zurückgeben. Wir könnten hinzufügen valueund
näher
9
@ ~ unutbu Du hast recht, mein schlechtes. Ich kann mir nichts Besseres als Ihre Lösung vorstellen!
Eric O Lebigot
24
scheint verrückt zu sein, es gibt keine eingebaute Nummer, die dies tut.
Dbliss
3
@jsmedmar Die Halbierungsmethode (siehe meine Antwort unten) ist O (log (n)).
Josh Albert
4
FutureWarning: 'argmin' is deprecated. Use 'idxmin' instead. The behavior of 'argmin' will be corrected to return the positional minimum in the future. Use 'series.values.argmin' to get the position of the minimum now.Verwenden idxminstatt argminfunktioniert für mich mit der obigen Lösung. (v3.6.4)
jorijnsmit
78

Wenn Ihr Array sortiert und sehr groß ist, ist dies eine viel schnellere Lösung:

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]

Dies skaliert auf sehr große Arrays. Sie können das oben Gesagte leicht ändern, um es in der Methode zu sortieren, wenn Sie nicht davon ausgehen können, dass das Array bereits sortiert ist. Es ist übertrieben für kleine Arrays, aber sobald sie groß werden, ist dies viel schneller.

Demitri
quelle
Das klingt nach der vernünftigsten Lösung. Ich frage mich, warum es sowieso so langsam ist. Normal np.searchsorteddauert ungefähr 2 µs für meinen Testsatz, die gesamte Funktion ca. 10 µs. Mit wird np.abses noch schlimmer. Keine Ahnung, was Python dort macht.
Michael
2
@Michael Für Einzelwerte sind die Numpy-Mathe-Routinen langsamer als die mathRoutinen, siehe diese Antwort .
Demitri
3
Dies ist die beste Lösung, wenn Sie mehrere Werte gleichzeitig nachschlagen möchten (mit einigen Anpassungen). Das Ganze if/elsemuss ersetzt werden durchidx = idx - (np.abs(value - array[idx-1]) < np.abs(value - array[idx])); return array[idx]
coderforlife
3
Das ist großartig, funktioniert aber nicht, wenn valuees größer als arraydas größte Element ist. Ich habe die ifAussage geändert if idx == len(array) or math.fabs(value - array[idx - 1]) < math.fabs(value - array[idx]), damit sie für mich funktioniert!
Nicoco
3
Dies funktioniert nicht, wenn idx 0 ist. Das if sollte lauten:if idx > 0 and (idx == len(array) or math.fabs(value - array[idx-1]) < math.fabs(value - array[idx])):
JPaget
52

Mit geringfügigen Änderungen funktioniert die obige Antwort mit Arrays beliebiger Dimension (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]

Oder als einzelne Zeile geschrieben:

a.flat[np.abs(a - a0).argmin()]
kwgoodman
quelle
6
Das "flache" Bit ist nicht erforderlich. a[np.abs(a-a0).argmin)]funktioniert gut.
Max Shron
2
Tatsächlich funktioniert das immer noch nur für eine Dimension, da argmin () mehrere Ergebnisse pro Spalte / Dimension liefert. Auch ich hatte einen Tippfehler. Dies funktioniert zumindest für 2 Dimensionen : a[np.sum(np.square(np.abs(a-a0)),1).argmin()].
Max Shron
3
Daher funktioniert es nicht für höhere Dimensionen, und die Antwort sollte gelöscht (oder geändert werden, um dies widerzuspiegeln)
Hugues Fontenelle
11
Bitte geben Sie ein Beispiel an, bei dem die vorgeschlagene Antwort nicht funktioniert. Wenn Sie eine finden, werde ich meine Antwort ändern. Wenn Sie keinen finden können, können Sie dann Ihre Kommentare entfernen?
Kwgoodman
18

Zusammenfassung der Antwort : Wenn eine sortiert ist, arrayist der Halbierungscode (unten angegeben) am schnellsten. ~ 100-1000-mal schneller für große Arrays und ~ 2-100-mal schneller für kleine Arrays. Es erfordert auch keine Numpy. Wenn Sie eine unsortierte haben , sollten Sie, arraywenn sie arraygroß ist, zuerst eine O (n logn) -Sortierung und dann eine Halbierung verwenden. Wenn sie arrayklein ist, scheint Methode 2 die schnellste zu sein.

Zuerst sollten Sie klarstellen, was Sie unter dem nächsten Wert verstehen . Oft möchte man das Intervall auf einer Abszisse, zB Array = [0,0.7,2.1], Wert = 1,95, Antwort wäre idx = 1. Dies ist der Fall, den Sie vermutlich benötigen (andernfalls kann das Folgende sehr einfach mit einer bedingten Folgeanweisung geändert werden, sobald Sie das Intervall gefunden haben). Ich werde bemerken, dass der optimale Weg, dies durchzuführen, die Halbierung ist (die ich zuerst bereitstellen werde - beachten Sie, dass es überhaupt kein Numpy erfordert und schneller ist als die Verwendung von Numpy-Funktionen, weil sie redundante Operationen ausführen). Dann werde ich einen Zeitvergleich mit den anderen hier von anderen Benutzern präsentierten bereitstellen.

Halbierung:

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

Jetzt definiere ich den Code aus den anderen Antworten, sie geben jeweils einen Index zurück:

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

Jetzt werde ich die Codes zeitlich festlegen: Beachten Sie, dass die Methoden 1,2,4,5 das Intervall nicht korrekt angeben. Die Methoden 1,2,4 runden auf den nächsten Punkt im Array (z. B.> = 1,5 -> 2), und Methode 5 rundet immer auf (z. B. 1,45 -> 2). Nur die Methoden 3 und 6 und natürlich die Halbierung geben das Intervall richtig an.

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

Für ein großes Array ergibt die Halbierung 4us im Vergleich zu den nächstbesten 180us und den längsten 1,21 ms (~ 100 - 1000-mal schneller). Für kleinere Arrays ist es ~ 2-100 mal schneller.

Josh Albert
quelle
2
Sie gehen davon aus, dass das Array sortiert ist. Es gibt viele Gründe, warum jemand das Array nicht sortieren möchte: Zum Beispiel, wenn das Array die Datenpunkte in einem Liniendiagramm darstellt.
user1917407
7
Die Python-Standardbibliothek enthält bereits in der Implementierung des Halbierungsalgorithmus
Felix
Wenn Sie sagten: "Wenn arrayes klein ist, scheint Methode 2 die schnellste zu sein." Wie klein meintest du @JoshAlbert?
Mr.Zeus
2
Dies findet nicht den nächsten Wert, sondern den nächstniedrigeren Wert.
Endolith
@endolith das ist nur bei halbieren der Fall.
Homero Esmeraldo
17

Hier ist eine Erweiterung, um den nächsten Vektor in einem Array von Vektoren zu finden.

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])
Onasafari
quelle
Ich denke, norm(..., axis=-1)sollte schneller sein als das Extrahieren der x,yWerte durch Python-Iteration. Auch x,ySkalare sind hier? Dann norm(x+y)ist ein Fehler, da z. B. die Entfernung (+1, -1)als 0 behandelt wird.
cfh
Das hat bei mir idx = np.array([np.linalg.norm(x+y) for (x,y) in abs(array-value)]).argmin()
funktioniert
9

Wenn Sie numpy nicht verwenden möchten, geschieht dies wie folgt:

def find_nearest(array, value):
    n = [abs(i-value) for i in array]
    idx = n.index(min(n))
    return array[idx]
Nick Crawford
quelle
9

Hier ist eine Version, die ein nicht skalares "Werte" -Array verarbeitet:

import numpy as np

def find_nearest(array, values):
    indices = np.abs(np.subtract.outer(array, values)).argmin(0)
    return array[indices]

Oder eine Version, die einen numerischen Typ zurückgibt (z. B. int, float), wenn die Eingabe skalar ist:

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]
Ryggyr
quelle
Gute Antwort, ich habe noch nie die outerMethode eines Ufunc verwendet. Ich denke, ich werde sie in Zukunft häufiger anwenden. Die erste Funktion sollte array[indices]übrigens zurückkehren.
Widjet
1
Diese Lösung skaliert nicht. np.subtract.outererzeugt die gesamte Außenproduktmatrix, die sehr langsam und speicherintensiv ist, wenn arrayund / oder valuessehr groß ist.
Anthonybell
8

Hier ist eine Version mit scipy für @Ari Onasafari, antworte " um den nächsten Vektor in einem Array von Vektoren zu finden "

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])
Efirvida
quelle
Das Erstellen eines KDTree ist für ein solches Problem ein ziemlicher Aufwand. Ich würde eine solche Lösung nur empfehlen, wenn Sie mehrere Abfragen in einem großen Array durchführen müssen. Dann ist es besser, sie einmal zu erstellen und wiederzuverwenden, als sie für jede Abfrage im laufenden Betrieb zu erstellen.
Ben
8

Hier ist eine schnelle vektorisierte Version von @ Dimitris Lösung, wenn Sie viele valuessuchen müssen ( valueskann ein mehrdimensionales Array sein):

#`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]

Benchmarks

> 100-mal schneller als die Verwendung einer forSchleife mit @ Demitris Lösung`

>>> %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
Anthonybell
quelle
idx = np.searchsorted(array, values)idx[array[idx] - values>np.diff(array).mean()*0.5]-=1return array[idx]
Wenn
7

Bei großen Arrays ist die (ausgezeichnete) Antwort von @Demitri weitaus schneller als die derzeit als beste gekennzeichnete Antwort. Ich habe seinen genauen Algorithmus auf zwei Arten angepasst:

  1. Die folgende Funktion funktioniert unabhängig davon, ob das Eingabearray sortiert ist oder nicht.

  2. Die folgende Funktion gibt den Index des Eingabearrays zurück, der dem nächsten Wert entspricht, der etwas allgemeiner ist.

Beachten Sie, dass die folgende Funktion auch einen bestimmten Randfall behandelt, der zu einem Fehler in der ursprünglichen Funktion von @Demitri führen würde. Ansonsten ist mein Algorithmus identisch mit seinem.

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
aph
quelle
1
Es ist erwähnenswert, dass dies ein großartiges Beispiel dafür ist, wie die Optimierung von Code dazu führt, dass das Lesen hässlicher und schwieriger wird. Die Antwort von @unutbu sollte (viel) bevorzugt werden, wenn Geschwindigkeit kein großes Problem darstellt, da sie weitaus transparenter ist.
Aph
Ich sehe die Antwort von @Michael nicht. Ist das ein Fehler oder bin ich blind?
Fookatchu
Nein, du bist nicht blind, ich bin nur Analphabet ;-) Es war @Demitri, auf dessen Antwort ich geriffelt habe. Mein Fehler. Ich habe gerade meinen Beitrag repariert. Vielen Dank!
Aph
Ich bekomme unterschiedliche Antworten mit Demitris und Ihren. Irgendwelche Ideen? x = np.array([2038, 1758, 1721, 1637, 2097, 2047, 2205, 1787, 2287, 1940, 2311, 2054, 2406, 1471, 1460]). Mit find_nearest(x, 1739.5)(dem ersten Quantil am nächsten) erhalte ich 1637(vernünftig) und 1(Fehler?).
PatrickT
3

Dies ist eine vektorisierte Version der Antwort von unutbu :

def find_nearest(array, values):
    array = np.asarray(array)

    # the last dim must be 1 to broadcast in (array - values) below.
    values = np.expand_dims(values, axis=-1) 

    indices = np.abs(array - values).argmin(axis=-1)

    return array[indices]


image = plt.imread('example_3_band_image.jpg')

print(image.shape) # should be (nrows, ncols, 3)

quantiles = np.linspace(0, 255, num=2 ** 2, dtype=np.uint8)

quantiled_image = find_nearest(quantiles, image)

print(quantiled_image.shape) # should be (nrows, ncols, 3)
Zhanwen Chen
quelle
2

Ich denke, der pythonischste Weg wäre:

 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)

Dies ist der Grundcode. Sie können es als Funktion verwenden, wenn Sie möchten

Ishan Tomar
quelle
2

Alle Antworten sind nützlich, um die Informationen zum Schreiben von effizientem Code zu sammeln. Ich habe jedoch ein kleines Python-Skript geschrieben, um es für verschiedene Fälle zu optimieren. Dies ist der beste Fall, wenn das bereitgestellte Array sortiert ist. Wenn man den Index des nächsten Punktes eines bestimmten Wertes durchsucht, bisectist das Modul am zeiteffizientesten. Wenn man die Indizes durchsucht, die einem Array entsprechen, numpy searchsortedist das am effizientesten.

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)

In [63]:% Zeit bisect.bisect_left (xlist, 0.3) CPU-Zeiten: Benutzer 0 ns, System: 0 ns, Gesamt: 0 ns Wandzeit: 22,2 µs

np.searchsorted(xar, 0.3, side="left")

In [64]:% time np.searchsorted (xar, 0,3, side = "left") CPU-Zeiten: Benutzer 0 ns, sys: 0 ns, gesamt: 0 ns Wandzeit: 98,9 µs

randpts = np.random.rand(1000)
np.searchsorted(xar, randpts, side="left")

% time np.searchsorted (xar, randpts, side = "left") CPU-Zeiten: Benutzer 4 ms, sys: 0 ns, gesamt: 4 ms Wandzeit: 1,2 ms

Wenn wir der multiplikativen Regel folgen, sollte numpy ~ 100 ms dauern, was ~ 83X schneller bedeutet.

Soumen
quelle
1

Für das 2d-Array, um die i, j-Position des nächsten Elements zu bestimmen:

import numpy as np
def find_nearest(a, a0):
    idx = (np.abs(a - a0)).argmin()
    w = a.shape[1]
    i = idx // w
    j = idx - i * w
    return a[i,j], i, j
Eduardo S. Pereira
quelle
0
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))
kareem mohamed
quelle
1
Hallo, willkommen bei Stack Overflow. Lesen Sie, wie Sie eine gute Antwort schreiben . Geben Sie eine kurze Beschreibung dessen, was Sie im Zusammenhang mit der Frage getan haben!
Tristo
0

Vielleicht hilfreich für ndarrays:

def find_nearest(X, value):
    return X[np.unravel_index(np.argmin(np.abs(X - value)), X.shape)]
Gusev Slava
quelle