Finden Sie nächste Indizes für ein Array gegen alle Werte in einem anderen Array - Python/NumPy

Question

Ich habe eine Liste von komplexen Zahlen, für die ich den nächsten Wert in einer anderen Liste von komplexen Zahlen finden möchte.

Mein aktueller Ansatz mit numpy:

import numpy as np 

refArray = np.random.random(16); 
myArray = np.random.random(1000); 


def find_nearest(array, value): 
    idx = (np.abs(array-value)).argmin() 
    return idx; 

for value in np.nditer(myArray): 
    index = find_nearest(refArray, value); 
    print(index); 

Leider dauert das Alter für eine große Menge von Werten. Gibt es eine schnellere oder mehr "pythonianische" Möglichkeit, jeden Wert in myArray mit dem nächsten Wert in refArray abzugleichen?

FYI: Ich brauche nicht unbedingt in meinem Skript numpy.

Wichtig: Die Reihenfolge sowohl von myArray als auch von refArray ist wichtig und sollte nicht geändert werden. Wenn Sortierung angewendet werden soll, sollte der ursprüngliche Index in irgendeiner Weise beibehalten werden.

Answer 1

Hier ist ein vektorisiert Ansatz mit np.searchsorted basierend auf this post -

def closest_argmin(A, B): 
    L = B.size 
    sidx_B = B.argsort() 
    sorted_B = B[sidx_B] 
    sorted_idx = np.searchsorted(sorted_B, A) 
    sorted_idx[sorted_idx==L] = L-1 
    mask = (sorted_idx > 0) & \ 
    ((np.abs(A - sorted_B[sorted_idx-1]) < np.abs(A - sorted_B[sorted_idx]))) 
    return sidx_B[sorted_idx-mask] 

Kurzerklärung:

• Holen Sie die sortierten Indizes für die linken Positionen. Wir machen das mit - np.searchsorted(arr1, arr2, side='left') oder nur np.searchsorted(arr1, arr2). Jetzt erwartet searchsorted sortierte Array als erste Eingabe, so dass wir dort einige Vorarbeiten benötigen.

• Vergleichen Sie die Werte an diesen linken Positionen mit den Werten an ihren unmittelbaren rechten Positionen (left + 1) und sehen Sie, welche am nächsten ist. Wir machen dies bei dem Schritt, der mask berechnet.

• Je nachdem, ob die linken oder ihre unmittelbaren rechten am nächsten sind, wählen Sie die entsprechenden aus. Dies erfolgt durch Subtraktion von Indizes mit den Werten mask, die als die in ints umgewandelten Offsets wirken.

Benchmarking

Original-Ansatz -

def org_app(myArray, refArray): 
    out1 = np.empty(myArray.size, dtype=int) 
    for i, value in enumerate(myArray): 
     # find_nearest from posted question 
     index = find_nearest(refArray, value) 
     out1[i] = index 
    return out1 

Timings und Verifizierung -

In [188]: refArray = np.random.random(16) 
    ...: myArray = np.random.random(1000) 
    ...: 

In [189]: %timeit org_app(myArray, refArray) 
100 loops, best of 3: 1.95 ms per loop 

In [190]: %timeit closest_argmin(myArray, refArray) 
10000 loops, best of 3: 36.6 µs per loop 

In [191]: np.allclose(closest_argmin(myArray, refArray), org_app(myArray, refArray)) 
Out[191]: True 

50x+ Speedup für die gesetzte Probe und hopef viel mehr für größere Datensätze!