将2个向量映射-帮助进行向量化

Question

将2个向量映射-帮助进行向量化

performancematlabdictionaryvectorvectorization

9

在Matlab中工作时，我有两个不同长度的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

代码可以正常运行，但是当处理长向量（超过10万个点）时需要一些时间。

有什么想法可以对这段代码进行向量化处理吗？

- yuk

我正在使用最新版本的Matlab中的新~~语法来跳过未使用的变量。如果您使用早期版本，请将~~替换为tmp。 - yuk

1

只是为了澄清，您想要找到每个 xm[i] 最接近 xn[j] 的索引 j 吗？ - Thom Smith

老兄，我的名字也叫汤姆·史密斯！ - rescdsk

6个回答

4

考虑这个向量化的解决方案：

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

- Amro

很好的向量化。谢谢。然而，它比我的函数慢了大约两倍，并且需要更多的内存，但比以前的代码要好。 - yuk

3

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

- Matt Mizumi

谢谢。我还没有尝试过，但它看起来是一个很好的解决方案。 - yuk

1

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

- 3Dave

啊，二分查找！没想到那个。+1 - John

0

利用排序的优势，正如David所说，因为你有那么多点，这样做会更快，但是为了参考，将其向量化的一种方法是使用meshgrid：

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

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

- rescdsk

是的，它占用了很多内存，并且比我用小向量的函数慢得多。 - yuk

0

你的 xm 和 xn 已经排序。如果通常情况下是这样的话，那么你可以比遍历整个数组做得更好。

对于 xn 中的每个值，都会有一系列的值，其中 xm 中的一个值将比其他任何值更接近该数。预先计算这些区间，然后你就可以按顺序遍历两个数组。

- John

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rescdsk · Accepted Answer

哦！另一种选择：由于您正在寻找两个排序列表之间的相似性，因此可以同时遍历它们，使用类似合并的算法。这应该是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的评论，上述代码并不完全正确！