Картирование 2 вектора - help toizeize

Question

Работа в Matlab У меня есть 2 вектора координат x с разной длиной. Например:

xm = [15 20 24 25 26 35 81 84 93]; 
xn = [14 22 26 51 55 59 70 75 89 96]; 

Мне нужно отобразить хт хп, или, другими словами, чтобы выяснить, какие координаты в хп ближе к хт. Поэтому, если у меня есть значения, связанные с этими координатами, я могу использовать эту карту в качестве индекса и соотнести эти значения.

Оба вектора сортируются, и в каждом векторе нет дубликатов.

Я написал простую функцию с для цикла:

function xmap = vectors_map(xm,xn) 
xmap = zeros(size(xm)); 
for k=1:numel(xm) 
    [~, ind] = min(abs(xm(k)-xn)); 
    xmap(k) = ind(1); 
end 

Для приведенного выше примера это возвращает

xmap = 
    1  2  2  3  3  3  8  9 10 

Он работает нормально, но занимает некоторое время, с длинными векторами (более 100 000 точек) ,

Какие-нибудь идеи, как векторизовать этот код?

Answer 1

Oh! Еще один вариант: поскольку вы ищете близкие соответствия между двумя отсортированными списками, вы можете проходить их оба одновременно, используя алгоритм слияния. Это должно быть O (max (длина (xm), длина (xn))) - ish.

match_for_xn = zeros(length(xn), 1); 
last_M = 1; 
for N = 1:length(xn) 
    % search through M until we find a match. 
    for M = last_M:length(xm) 
    dist_to_curr = abs(xm(M) - xn(N)); 
    dist_to_next = abs(xm(M+1) - xn(N)); 

    if dist_to_next > dist_to_curr 
     match_for_xn(N) = M; 
     last_M = M; 
     break 
    else 
     continue 
    end 

    end % M 
end % N 

EDIT: комментарий видеть @ Юк, тем выше код не совсем правильно!

Answer 2

Похоже, что ваши входные векторы отсортированы. Используйте бинарный поиск, чтобы найти ближайшее совпадение. Это даст вам время O (n ln n).

Answer 3

Ваши xm и xn сортированы. Если это вообще так, то вы можете сделать гораздо лучше, чем перешагнуть через весь массив.

Для каждого значения в xn будет диапазон значений, значение которого в xm будет ближе к этому числу, чем любое другое. Вычислите эти интервалы заранее, и затем вы можете последовательно проходить через оба массива.

Answer 4

Воспользовавшись сортируется, как говорит Давид, будет быстрее, так как у вас так много очков, но для справки один способ векторизации это было бы использовать meshgrid:

[X Y] = meshgrid(xn, xm); 
diffs = X - y; 
mins = min(diffs, [], 2); 

Обратите внимание, что это создаст два массива 100 000 x 100 000 в памяти, поэтому, вероятно, это возможно только для небольших наборов данных.

Answer 5

Рассмотрим векторизованную решение:

[~, xmap] = min(abs(bsxfun(@minus, xm, xn'))) 

Answer 6

Самая быстрая реализация, о которой я знаю, решает эту проблему: this one (код C, который может быть скомпилирован как файл .mex, для меня это примерно в 20 раз быстрее, чем код rescdsk в принятом ответе). Удивительно, что такая общая операция не является встроенной функцией MATLAB.