Найти элементы массива один, ближайший к элементам массива два

Этот ответ объясняет, как найти ближайший (отсортированный) элемент массива кодна точкаспособом, эффективным для больших массивов (слегка модифицированным):

def arg_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 idx-1
    else:
        return idx

Если вместо этого мы хотим найти элементы массива, ближайшие кзадавать точек (то есть второй массив); Существуют ли эффективные (по скорости, для больших массивов) способы расширения этого, кроме использования цикла for?

Некоторые тестовые случаи:

>>> xx = [0.2, 0.8, 1.3, 1.5, 2.0, 3.1, 3.8, 3.9, 4.5, 5.1, 5.5]
>>> yy = [1, 2, 3, 4, 5]
>>> of_x_nearest_y(xx, yy)
[0.5, 2.0, 3.1, 3.9, 5.1]

>>> xx = [0.2, 0.8, 1.3, 1.5, 2.0, 3.1, 3.8, 3.9, 4.5, 5.1, 5.5]
>>> yy = [-2, -1, 4.6, 5.8]
>>> of_x_nearest_y(xx, yy)
[0.2, 0.2, 4.5, 5.5]

Изменить: при условии, что оба массива отсортированы, вы можете сделатьнемного лучше чемполностью наивный цикл for путем исключения значений ниже тех, которые уже сопоставлены, т.е.

def args_nearest(options, targets):
    locs = np.zeros(targets.size, dtype=int)
    prev = 0
    for ii, tt in enumerate(targets):
        locs[ii] = prev + arg_nearest(options[prev:], tt)
        prev = locs[ii]
    return locs
 DilithiumMatrix15 июн. 2016 г., 19:17
@ user2357112 ммм, хорошая точка!
 user235711215 июн. 2016 г., 19:16
searchsorted принимает массив значений для поиска, поэтому его не так уж сложно изменитьarg_nearest для вашей работы.

Ответы на вопрос(1)

Решение Вопроса

чтобы расширить его для массива элементов вvalue, вот так -

idx = np.searchsorted(xx, yy, side="left").clip(max=xx.size-1)
mask = (idx > 0) &  \
       ( (idx == len(xx)) | (np.fabs(yy - xx[idx-1]) < np.fabs(yy - xx[idx])) )
out = xx[idx-mask]

объяснение

Номенклатура:array это массив, в котором мы хотим разместить элементы изvalue поддерживать отсортированный характерarray.

Изменения, необходимые для расширения решения для одного элемента на множество элементов для поиска:

1] Обрезать массив индексовidx получен изnp.searchsorted на макс. изarray.size-1потому что для элементов вvalue которые больше, чем максимумarrayнам нужно сделатьidx индексируетсяarray.

2] Ввестиnumpy заменитьmath делать эти операции в векторизованном виде.

3] Заменить условное утверждение на хитростьidx - mask, В этом случае внутренне Python будет конвертироватьmask дляint массив, чтобы соответствовать типу данныхidx, Таким образом, всеTrue элементы становятся1 и, таким образом, дляTrue элементы, которые мы бы эффективно иметьidx-1, какойTrue случай условного оператора IF в исходном коде.

 DilithiumMatrix15 июн. 2016 г., 19:52
Красивая! Я только что придумал (эффективно) одно и то же решение, за исключением использования 8 строк с многочисленными фильтрами и парой~ инверсии ... ты выиграл!
 Divakar15 июн. 2016 г., 20:10
@DilithiumMatrix Действительно интересная проблема, которая должна быть полезна при решении многих других ближайших задач! До этого я бы пошел с решением для грубого вещания:xx[np.abs(xx[:,None] - yy).argmin(0)], Но этоsearchsorted основанное решение должно очень хорошо масштабироваться для больших массивов. Спасибо, что представили нам эту эффективную идею!
 DilithiumMatrix15 июн. 2016 г., 20:21
Хаха, всегда рада, что моя борьба была полезной!

Ваш ответ на вопрос