映射2矢量 - 帮助矢量化

在Matlab中工作我有2个不同长度的x坐标向量。例如：映射2矢量 - 帮助矢量化

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点）。

任何想法如何矢量化这段代码？

来源

2010-01-26 yuk

我在Matlab的最新版本中使用新的〜语法来跳过一个未使用的变量。如果你有一个更早的版本，只需用〜替换tmp即可。 – yuk 2010-01-26 21:39:05

只是为了澄清，你想为每个xm [i]索引j这样xm [i]最接近xn [j]？ – 2010-01-26 21:47:45

是的。很好的总结，谢谢。 – yuk 2010-01-27 01:20:20

哦！另一种选择是：由于您正在寻找两个排序列表之间的密切对应关系，因此您可以使用类似合并的算法同时通过它们。这应该是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

编辑：见@议员的评论，上面的代码是不完全正确的！

来源

2010-01-27 03:20:39 rescdsk

太棒了！这个代码给我超过50倍的速度提高了10000个长度的矢量，1500（！）倍的100,000个长度的矢量。如果xn的最后几个元素映射到xm（end），它可以返回错误。如果M yuk 2010-01-28 18:22:41

看起来我无法在注释中格式化代码。 :( – yuk 2010-01-28 18:23:41

酷！耶！我很高兴它的工作对你！是的，就是关于计算机科学的有趣的事情之一，当你突然做什么更快的亿万倍... – rescdsk 2010-01-28 18:34:09

它看起来像您的输入向量排序。使用二进制搜索来找到最接近的匹配。这会给你一个O（n ln n）的运行时间。

来源

2010-01-26 21:39:20

请你提供一些Matlab代码吗？ – yuk 2010-01-26 21:40:43

是的，矢量排序。 – yuk 2010-01-26 21:42:13

啊，二进制搜索！没想到这一点。 +1 – John 2010-01-26 21:48:52

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

对于xn中的每个值，都会有一个xm值比其他值更接近该值的值的范围。事先计算这些时间间隔，然后可以按顺序逐步通过两个阵列。

来源

2010-01-26 21:48:03 John

趁着进行排序，正如大卫说，会更快，因为你有这么多点，但参考矢量化一个方法是使用meshgrid：

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

注意，这将创造内存中有两个100,000 x 100,000阵列，所以它可能只适用于较小的数据集。

来源

2010-01-26 21:52:32 rescdsk

嗯，它需要大量的内存，然后比我的小矢量函数慢得多。 – yuk 2010-01-28 18:35:26

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

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

来源

2010-01-26 22:48:02 Amro

漂亮的矢量化。谢谢。但是，它比我的函数慢两倍左右，而且需要更多的内存，但是比以前的代码更好。 – yuk 2010-01-28 18:37:22

我意识到解决这个问题的最快速度是this one（C代码可以编译为.mex文件;对我来说，它比接受答案中的rescdsk代码快20倍）。令人惊讶的是，这种常见操作不是MATLAB内置函数。

来源

2014-07-04 19:58:20

感谢。有没有尝试过，但它看起来像一个很好的解决方案 – yuk 2014-07-05 14:48:37

映射2矢量 - 帮助矢量化

回答

相关问题