Wkład

known_array : tablica numpy; składający się tylko z wartości skalarnych;shape: (m, 1)

test_array : tablica numpy; składający się tylko z wartości skalarnych;shape: (n, 1)

Wydajność

indices : tablica numpy;shape: (n, 1); Dla każdej wartości wtest_array znajduje indeks najbliższej wartości wknown_array

residual : tablica numpy;shape: (n, 1); Dla każdej wartości wtest_array znajduje różnicę od najbliższej wartości wknown_array

Przykład

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])

Przykładowa implementacja (nie w pełni wektoryzowana)

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.])

Jak najlepiej przyspieszyć to zadanie? Cython jest opcją, ale zawsze wolałbym móc usunąćfor pętla i niech kod pozostanie czysty.

NB: Sprawdzono następujące pytania dotyczące przepełnienia stosu

Python / Numpy - szybkie znajdowanie indeksu w tablicy najbliżej jakiejś wartościZnajdź indeks o najbliższej wartości liczbowejZnajdź najbliższą wartość w tablicy numpyZnajdowanie najbliższej wartości i zwracanie indeksu tablicy w Pythonieznajdowanie najbliższych przedmiotów na dwóch listach / tablicach w PythonieAktualizacje

Zrobiłem kilka małych testów porównujących rozwiązanie nie wektoryzowane i wektoryzowane (zaakceptowana odpowiedź).

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

Na temat10-krotnie przyśpieszyć!

Wyjaśnienie

known_array nie jest posortowane.

Przeprowadziłem testy porównawcze zgodnie z odpowiedzią @cyborg poniżej.

Przypadek 1: Jeśliknown_array zostały posortowane

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.

Po pierwsze, dla dużych tablicdiffs Metoda jest wolniejsza, zjada również dużo pamięci RAM, a mój system zawiesił się, gdy uruchomiłem go na rzeczywistych danych.

Przypadek 2 : Gdyknown_array nie jest posortowane; który przedstawia rzeczywisty scenariusz

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)
<ipython-input-26-3170078c217a> in <module>()
      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.

Muszę też powiedzieć, że podejście powinno być również wydajne pod względem pamięci. W przeciwnym razie moje 8 GB pamięci RAM jest niewystarczające. W przypadku podstawowym jest to wystarczające.