Отображение 2 векторов - помогите векторизовать

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

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

Оба вектора отсортированы, и в каждом из них нет дубликатов.

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

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

О! Еще один вариант: поскольку вы ищете близкие соответствия между двумя отсортированными списками, вы можете просматривать их одновременно, используя алгоритм, подобный слиянию. Это должно быть 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: Смотрите комментарий @ yuk, приведенный выше код не совсем корректен!

Answer 2

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

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

Answer 3

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

Answer 4

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

Answer 5

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

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

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

Answer 6

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

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