मैपिंग 2 वैक्टर -

Question

मैटलैब में काम करने में सहायता करने के लिए मेरी अलग-अलग लंबाई के साथ एक्स समन्वय के 2 वैक्टर हैं। उदाहरण के लिए:

xm = [15 20 24 25 26 35 81 84 93]; 
xn = [14 22 26 51 55 59 70 75 89 96]; 

मैं दूसरे शब्दों में xn को xm, या मैप करने के लिए जो xn में निर्देशांक खोजने की जरूरत है xm के सबसे करीब हैं। इसलिए यदि मेरे पास उन निर्देशांक से जुड़े मूल्य हैं, तो मैं इस मानचित्र का उपयोग इंडेक्स के रूप में कर सकता हूं और उन मानों से संबंधित हूं।

दोनों वैक्टर क्रमबद्ध किए गए हैं और प्रत्येक वेक्टर में कोई डुप्लिकेट नहीं है।

मैं के साथ एक सरल समारोह लिखा था के लिए लूप:

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 

ठीक काम करता है, लेकिन लंबे समय वैक्टर के साथ कुछ समय लगता है है (100,000 से अधिक अंक) ।

कोई भी विचार इस कोड को सदिश कैसे करें?

Answer 1

ओह:

Answer 2

ऐसा लगता है कि आपके इनपुट वैक्टर सॉर्ट किए गए हैं। निकटतम मैच खोजने के लिए बाइनरी खोज का प्रयोग करें। यह आपको ओ (एन एलएन एन) रन टाइम देगा।

Answer 3

आपका एक्सएम और एक्सएन सॉर्ट किया गया है। यदि यह आम तौर पर मामला है, तो आप पूरे सरणी पर कदम उठाने से कहीं ज्यादा बेहतर कर सकते हैं।

xn में प्रत्येक मान के लिए, मानों की एक श्रृंखला होगी जिसके लिए xm में कोई मान किसी अन्य की तुलना में उस संख्या के करीब होगा। इन अंतरालों को पहले से गणना करें और फिर आप अनुक्रमिक रूप से दोनों सरणी के माध्यम से कदम उठा सकते हैं।

Answer 4

का लाभ उठाते हुए हल कर जा रहा है, के रूप में डेविड कहते हैं, तेजी से जब से तुम इतने सारे अंक होगा, लेकिन संदर्भ के लिए एक तरह से इस vectorize करने meshgrid उपयोग करने के लिए होगा:

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

ध्यान दें कि यह पैदा करेगा स्मृति में दो 100,000 x 100,000 सरणी, इसलिए यह संभवतः छोटे डेटा सेट के लिए संभव है।

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

Answer 5

इस vectorized समाधान पर विचार करें! एक अन्य विकल्प: चूंकि आप दो क्रमबद्ध सूचियों के बीच घनिष्ठ पत्राचार की तलाश में हैं, इसलिए आप विलय-जैसी एल्गोरिदम का उपयोग करके एक साथ दोनों के माध्यम से जा सकते हैं। यह ओ होना चाहिए (अधिकतम (लंबाई (एक्सएम), लंबाई (एक्सएन))) - आईएसएच।

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 

संपादित करें: देखें @ युक की टिप्पणी, ऊपर कोड पूरी तरह से सही नहीं है!

Answer 6

सबसे तेज़ कार्यान्वयन मुझे पता है कि इस समस्या को हल करता है this one (सी कोड जिसे .mex फ़ाइल के रूप में संकलित किया जा सकता है; मेरे लिए यह स्वीकार्य उत्तर में rescdsk के कोड से लगभग 20 गुना तेज है)। यह आश्चर्य की बात है कि ऐसा एक सामान्य ऑपरेशन MATLAB अंतर्निहित फ़ंक्शन नहीं है।