Den nächstgelegenen Wert in einem Numpy-Array finden

Question

Gibt es einen numpy-thonischen Weg, z.B. eine Funktion, um die nächstgelegener Wert in einem Array?

Ejemplo:

np.find_nearest( array, value )

Answer 1

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

Answer 2

IF 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 ermöglicht die Skalierung auf sehr große Arrays. Sie können die obige Methode leicht ändern, um in der Methode zu sortieren, wenn Sie nicht davon ausgehen können, dass das Array bereits sortiert ist. Es ist ein Overkill für kleine Arrays, aber sobald sie groß werden, ist dies viel schneller.

Answer 3

Mit leichten Änderungen funktioniert die obige Antwort auch 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 eine einzige Zeile geschrieben:

a.flat[np.abs(a - a0).argmin()]

Answer 4

Zusammenfassung der Antwort : Wenn man eine sortierte array dann ist der (unten angegebene) Bisektionscode der schnellste. ~100-1000 mal schneller für große Arrays und ~2-100 mal schneller für kleine Arrays. Er benötigt auch kein Numpy. Wenn Sie ein unsortiertes array wenn dann array groß ist, sollte man zunächst eine O(n logn)-Sortierung und dann eine Bisektion in Betracht ziehen, und wenn array klein ist, scheint Methode 2 die schnellste zu sein.

Zunächst sollten Sie klären, was Sie unter dem nächstliegenden Wert verstehen . Oft will man das Intervall in einer Abszisse, z.B. array=[0,0.7,2.1], value=1.95, die Antwort wäre idx=1. Ich vermute, dass Sie genau diesen Fall benötigen (andernfalls kann das Folgende sehr leicht mit einer nachfolgenden bedingten Anweisung geändert werden, sobald Sie das Intervall gefunden haben). Ich möchte anmerken, dass der optimale Weg, dies zu tun, die Halbierung ist (die ich zuerst bereitstellen werde - beachten Sie, dass sie überhaupt kein Numpy erfordert und schneller ist als die Verwendung von Numpy-Funktionen, da diese redundante Operationen durchführen). Dann werde ich einen Zeitvergleich mit den anderen hier von anderen Benutzern vorgestellten Methoden anstellen.

Zweiteilung:

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 werde ich den Code aus den anderen Antworten definieren, 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 timen: Hinweis Die Methoden 1,2,4,5 geben das Intervall nicht korrekt an. Die Methoden 1,2,4 runden auf den nächstgelegenen 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 Zweiteilung geben das Intervall korrekt 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

Bei einem großen Array ergibt die Halbierung 4 Sekunden im Vergleich zu den nächstbesten 180 Sekunden und den längsten 1,21 ms (~100 bis 1000 Mal schneller). Bei kleineren Arrays ist es ~2-100 mal schneller.

Answer 5

Hier ist eine schnelle vektorisierte Version der Lösung von @Dimitri, wenn Sie viele haben values zu suchen ( values kann 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 mit einem for Schleife mit @Demitri's 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