Mapping 2 vectors - help to vectorize

dictionary, matlab, performance, vector, vectorization

Solution

Oh! One other option: since you're looking for close correspondences between two sorted lists, you could go through them both simultaneously, using a merge-like algorithm. This should be 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: See @yuk's comment, the above code is not totally correct!

Problem

Working in Matlab I have 2 vectors of x coordinate with different length. For example: ``` xm = [15 20 24 25 26 35 81 84 93]; xn = [14 22 26 51 55 59 70 75 89 96]; ``` I need to map xm to xn, or in other words to find which coordinates in xn are closest to xm. So if I have values associated with those coordinates, I can use this map as index and correlate those values. Both vectors are sorted and there are no duplicates in each vector. I wrote a simple function with for-loop: ``` 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 ``` For the above example is returns ``` xmap = 1 2 2 3 3 3 8 9 10 ``` It works ok, but takes a while with long vectors (over 100,000 points). Any ideas how to vectorize this code?

Original source