9

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?

4

6 回答 6

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

编辑：见@yuk 的评论，上面的代码并不完全正确！

于 2010-01-27T03:20:39.077 回答
4

考虑这个矢量化解决方案：

[~, xmap] = min( abs(bsxfun(@minus, xm, xn')) )
于 2010-01-26T22:48:02.607 回答
3

我知道解决这个问题的最快实现是这个（可以编译为 .mex 文件的 C 代码；对我来说，它比接受答案中 rescdsk 的代码快 20 倍）。令人惊讶的是，如此常见的操作不是 MATLAB 内置函数。

于 2014-07-04T19:58:20.780 回答
1

看起来您的输入向量已排序。使用二分搜索查找最接近的匹配项。这将为您提供 O(n ln n) 的运行时间。

于 2010-01-26T21:39:20.937 回答
0

您的 xm 和 xn 已排序。如果通常是这种情况，那么您可以做得比跨过整个阵列要好得多。

对于 xn 中的每个值，将有一个值范围，其中 xm 中的值将比任何其他值更接近该数字。事先计算这些间隔，然后您可以按顺序逐步遍历这两个数组。

于 2010-01-26T21:48:03.290 回答
0

正如大卫所说，利用排序会更快，因为你有这么多点，但作为参考，一种矢量化的方法是使用网格网格：

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

请注意，这将在内存中创建两个 100,000 x 100,000 数组，因此它可能仅适用于较小的数据集。

于 2010-01-26T21:52:32.780 回答