Tìm chỉ mục gần nhất cho một mảng so với tất cả các giá trị trong mảng khác - Python/NumPy

Question

Tôi có danh sách các số phức mà tôi muốn tìm giá trị gần nhất trong danh sách số phức khác.

cách tiếp cận hiện tại của tôi với 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); 

Thật không may, điều này có độ tuổi cho một số lượng lớn các giá trị. Có cách nào nhanh hơn hoặc nhiều hơn "pythonian" khớp với mỗi giá trị trong myArray với giá trị gần nhất trong refArray không?

FYI: Tôi không nhất thiết cần phải có mật mã trong tập lệnh của mình.

Quan trọng: thứ tự của cả myArray cũng như refArray là quan trọng và không nên thay đổi. Nếu việc sắp xếp được áp dụng, chỉ mục ban đầu sẽ được giữ lại theo một cách nào đó.

Answer 1

Dưới đây là một cách tiếp cận vectorized với np.searchsorted dựa trên 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] 

Giới thiệu tóm tắt lời giải thích:

• Lấy chỉ số được sắp xếp cho các vị trí còn lại. Chúng tôi thực hiện việc này với - np.searchsorted(arr1, arr2, side='left') hoặc chỉ np.searchsorted(arr1, arr2). Bây giờ, searchsorted dự kiến ​​sắp xếp mảng là đầu vào đầu tiên, vì vậy chúng tôi cần một số công việc chuẩn bị ở đó.

• So sánh các giá trị tại các vị trí bên trái đó với các giá trị ở vị trí bên phải ngay lập tức (left + 1) và xem giá trị nào gần nhất. Chúng tôi thực hiện việc này ở bước tính toán mask.

• Căn cứ vào việc những cái bên trái hoặc cái bên phải của chúng ở bên trái gần nhất, hãy chọn những cái tương ứng. Điều này được thực hiện với phép trừ các chỉ mục với các giá trị mask hoạt động như các giá trị bù trừ được chuyển đổi thành ints.

Benchmarking

gốc cách tiếp cận -

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 

Thời gian và xác minh -

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+ tăng tốc cho các mẫu đăng và hopef ully nhiều hơn cho các tập dữ liệu lớn hơn!