вход

known_array : массив NumPy; состоящий только из скалярных значений;shape: (m, 1)

test_array : массив NumPy; состоящий только из скалярных значений;shape: (n, 1)

Выход

indices : массив NumPy;shape: (n, 1); Для каждого значения вtest_array находит индекс ближайшего значения вknown_array

residual : массив NumPy;shape: (n, 1); Для каждого значения вtest_array находит разницу от ближайшего значения вknown_array

пример

In [17]: known_array = np.array([random.randint(-30,30) for i in range(5)])

In [18]: known_array
Out[18]: array([-24, -18, -13, -30,  29])

In [19]: test_array = np.array([random.randint(-10,10) for i in range(10)])

In [20]: test_array
Out[20]: array([-6,  4, -6,  4,  8, -4,  8, -6,  2,  8])

Пример реализации (не полностью векторизованный)

def find_nearest(known_array, value):
    idx = (np.abs(known_array - value)).argmin()
    diff = known_array[idx] - value
    return [idx, -diff]

In [22]: indices = np.zeros(len(test_array))

In [23]: residual = np.zeros(len(test_array))

In [24]: for i in range(len(test_array)):
   ....:     [indices[i], residual[i]] =  find_nearest(known_array, test_array[i])
   ....:     

In [25]: indices
Out[25]: array([ 2.,  2.,  2.,  2.,  2.,  2.,  2.,  2.,  2.,  2.])

In [26]: residual
Out[26]: array([  7.,  17.,   7.,  17.,  21.,   9.,  21.,   7.,  15.,  21.])

Каков наилучший способ ускорить эту задачу? Cython - вариант, но я всегда предпочел бы удалитьfor цикл и пусть код остается чистым NumPy.

NB: Следующие вопросы переполнения стека были рассмотрены

Python / Numpy - быстро найти индекс в массиве, ближайшем к некоторому значениюНайти индекс численно ближайшего значенияНайти ближайшее значение в массиве NumPyНахождение ближайшего значения и возврат индекса массива в Pythonпоиск ближайших элементов в двух списках / массивах в PythonОбновления

Я сделал несколько небольших тестов для сравнения не векторизованного и векторизованного решения (принятый ответ).

In [48]: [indices1, residual1] = find_nearest_vectorized(known_array, test_array)

In [53]: [indices2, residual2] = find_nearest_non_vectorized(known_array, test_array)

In [54]: indices1==indices2
Out[54]: array([ True,  True,  True,  True,  True,  True,  True,  True,  True,  True],   dtype=bool)

In [55]: residual1==residual2
Out[55]: array([ True,  True,  True,  True,  True,  True,  True,  True,  True,  True], dtype=bool)

In [56]: %timeit [indices2, residual2] = find_nearest_non_vectorized(known_array, test_array)
10000 loops, best of 3: 173 µs per loop

In [57]: %timeit [indices1, residual1] = find_nearest_vectorized(known_array, test_array)
100000 loops, best of 3: 16.8 µs per loop

Об10-кратный ускорив!

осветление

known_array не отсортировано.

Я провел тесты, как указано в ответе @cyborg ниже.

Случай 1: Еслиknown_array были отсортированы

known_array = np.arange(0,1000)
test_array = np.random.randint(0, 100, 10000)
print('Speedups:')
base_time = time_f('base')
for func_name in ['diffs', 'searchsorted1', 'searchsorted2']:
    print func_name + ' is x%.1f faster than base.' % (base_time / time_f(func_name))
    assert np.allclose(base(known_array, test_array), eval(func_name+'(known_array, test_array)'))

Speedups:
diffs is x0.4 faster than base.
searchsorted1 is x81.3 faster than base.
searchsorted2 is x107.6 faster than base.

Во-первых, для больших массивовdiffs Метод на самом деле медленнее, он также потребляет много оперативной памяти, и моя система зависала, когда я запускал его на реальных данных.

Дело 2 : Когдаknown_array не сортируется; который представляет собой реальный сценарий

known_array = np.random.randint(0,100,100)
test_array = np.random.randint(0, 100, 100)

Speedups:
diffs is x8.9 faster than base.
AssertionError                            Traceback (most recent call last)
 in ()
      5 for func_name in ['diffs', 'searchsorted1', 'searchsorted2']:
      6     print func_name + ' is x%.1f faster than base.' % (base_time /  time_f(func_name))
----> 7     assert np.allclose(base(known_array, test_array),  eval(func_name+'(known_array, test_array)'))

AssertionError: 


searchsorted1 is x14.8 faster than base.

Я также должен прокомментировать, что этот подход также должен эффективно использовать память. В противном случае моих 8 ГБ оперативной памяти недостаточно. В базовом случае этого вполне достаточно.