как сопоставить два клочковатых массива неравной длины?

Question

У меня есть два одномерных массива.Длина неравна.Я хочу сделать пары (array1_elemnt, array2_element) элементов, которые находятся близко друг к другу.Давайте рассмотрим следующий пример

    a = [1,2,3,8,20,23]
    b = [1,2,3,5,7,21,35]

Ожидаемый результат:

    [(1,1), 
    (2,2), 
    (3,3), 
    (8,7),
    (20,21),
    (23,25)]

Важно отметить, что 5 оставлено в покое.Это легко сделать с помощью циклов, но у меня есть очень большие массивы.Я рассмотрел использование ближайшего соседа.Но хотелось убить воробья с помощью пушки.

Может кто-нибудь предложить какое-нибудь элегантное решение.

Большое спасибо.

Answer 1

Как насчет использования алгоритма Needleman-Wunsch ? :)

Матрица подсчета очков была бы тривиальной, так как «расстояние» между двумя числами - только их разница.

Но это, вероятно, будет похоже на убийство воробья с помощью танка ...

Answer 2

Вы можете использовать встроенную функцию карты для векторизации функции, которая делает это.Например:

ar1 = np.array([1,2,3,8,20,23])
ar2 = np.array([1,2,3,5,7,21,35])
def closest(ar1, ar2, iter):
    x = np.abs(ar1[iter] - ar2)
    index = np.where(x==x.min())
    value = ar2[index]
    return value

def find(x):
    return closest(ar1, ar2, x)
c = np.array(map(find, range(ar1.shape[0])))

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

 def closest(ar1, ar2, iter):
    x = np.abs(ar1[iter] - ar2)
    index = np.where(x==x.min())
    value = ar2[index]
    ar2[ar2==value] = -10000000
    return value

Answer 3

Вы можете сделать следующее:

a = np.array([1,2,3,8,20,23])
b = np.array([1,2,3,5,7,21,25])

def find_closest(a, sorted_b):
    j = np.searchsorted(.5*(sorted_b[1:] + sorted_b[:-1]), a, side='right')
    return b[j]

b.sort()  # or, b = np.sort(b), if you don't want to modify b in-place
print np.c_[a, find_closest(a, b)]

# ->
# array([[ 1,  1],
#        [ 2,  2],
#        [ 3,  3],
#        [ 8,  7],
#        [20, 21],
#        [23, 25]])

Это должно быть довольно быстро.Как это работает, searchsorted найдет для каждого числа a индекс в b после средней точки между двумя числами, то есть ближайшего числа.

Answer 4

Я думаю, что это можно сделать так:

1. создает два новых структурированных массива, так что существует второй индекс, который равен 0 или 1, указывающий, к какому массиву принадлежит значение, т. Е. Ключ
2. объединить оба массива
3. сортировка объединенного массива по первому полю (значениям)
4. использовать 2 стека: пройти массив, поместив элементы с ключом 1 в левый стек, а когда вы пересечете элемент с ключом 0, положить их в правый стек. Когда вы достигнете второго элемента с помощью клавиши 0, для первого с помощью клавиши 0 проверьте верхнюю и нижнюю часть левого и правого стеков и возьмите ближайшее значение (возможно, с максимальным расстоянием), переключите стеки и продолжайте.

сортировка должна быть самым медленным шагом, а максимальное общее пространство для стеков равно n или m.

Answer 5

Лучший метод, который я могу придумать, это использовать цикл.Если цикл в Python медленный, вы можете использовать Cython для ускорения вашего кода.