Отображение 2 векторов - помогает векторизовать
При работе в 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. Таким образом, если у меня есть значения, связанные с теми координатами, я могу использовать эту карту в качестве индекса и коррелировать те значения.
Оба вектора отсортированы и в каждом векторе нет никаких дубликатов.
Я записал простую функцию с для цикла:
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 точек).
Какие-либо идеи, как векторизовать этот код?
5 ответов
О! Еще один вариант: так как вы ищете тесные соответствия между двумя отсортированными списками, вы можете просматривать их оба одновременно, используя алгоритм слияния. Это должно быть O(max(length(xm), length(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, приведенный выше код не совсем корректен!
Похоже, что ваши входные векторы сортируются. Используйте бинарный поиск, чтобы найти ближайший матч. Это даст вам время выполнения o (n ln n).
Рассмотрим это векторное решение:
[~, xmap] = min( abs(bsxfun(@minus, xm, xn')) )
Использование преимуществ сортировки, как говорит Дэвид, будет быстрее, так как у вас так много точек, но для справки одним из способов векторизации будет использование meshgrid:
[X Y] = meshgrid(xn, xm);
diffs = X - y;
mins = min(diffs, [], 2);
Обратите внимание, что это создаст два массива 100,000 x 100,000 в памяти, так что это, вероятно, возможно, возможно только для меньших наборов данных.
Ваш XM и XN отсортированы. Если это обычно так, то вы можете сделать намного лучше, чем наступить на весь массив.
Для каждого значения в Xn будет диапазон значений, для которых значение в XM будет ближе к этому номеру, чем любой другой. Вычислить эти интервалы заранее, и вы можете затем выйти через оба массива последовательно.