映射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矢量 - 幫助矢量化

回答

相關問題