Найти ближайшие индексы для одного массива против всех значений в другом массиве – Python / NumPy
У меня есть список сложных чисел, для которых я хочу найти ближайшее значение в другом списке сложных чисел.
Мой текущий подход с numpy:
- Numpy: индексный 3D-массив с индексом последней оси, хранящимся в 2D-массиве
- Почему numpy массивы не могут конвертировать из datetime в np.datetime64 неявно?
- Почему np.compress быстрее, чем логическое индексирование?
- Какой самый быстрый способ увеличить контрастность цветного изображения с OpenCV в python (cv2)?
- Фильтрация массива 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); К сожалению, это требует времени для большого количества значений. Есть ли более быстрый или более «питонский» способ сопоставления каждого значения в myArray с ближайшим значением refArray?
FYI: Мне не обязательно нужно numpy в моем скрипте.
Важно: порядок как myArray, так и refArray важен и его не следует изменять. Если сортировка должна быть применена, исходный индекс должен быть каким-то образом сохранен.
One Solution collect form web for “Найти ближайшие индексы для одного массива против всех значений в другом массиве – Python / NumPy”
Вот один векторный подход с np.searchsorted основанный на 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]
Краткое объяснение :
-
Получить отсортированные индексы для левых позиций. Мы делаем это с помощью –
np.searchsorted(arr1, arr2, side='left')или простоnp.searchsorted(arr1, arr2). Теперьsearchsortedожидает, что отсортированный массивsearchsortedпервым входом, поэтому нам нужна какая-то подготовительная работа. -
Сравните значения в этих левых положениях со значениями в их непосредственных правильных положениях
(left + 1)и посмотрите, какая из них ближе всего. Мы делаем это на шаге, который вычисляетmask. -
Исходя из того, наиболее близки ли левые или их ближайшие правые, выберите соответствующие. Это делается с вычитанием индексов с значениями
maskдействующими как смещения, которые преобразуются вints.
Бенчмаркинг
Оригинальный подход –
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
Сроки и проверка –
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+ ускорение для размещенного образца и, надеюсь, больше для больших наборов данных!