एक तेज, vectorized फैशन में पिछले अशून्य सूचकांक का एक वेक्टर में एक द्विआधारी मैट्रिक्स टर्निंग

Question

मान लीजिए, MATLAB में, मैं एक मैट्रिक्स, ए, जिसका तत्व हैं या तो 0 या 1.

मैं कैसे मिलता है कि एक तेज, वेक्टरकृत तरीके से प्रत्येक कॉलम के अंतिम गैर-शून्य तत्व की अनुक्रमणिका का एक वेक्टर?

मैं

[B, I] = max(cumsum(A));

कर सकता है और I उपयोग करते हैं, लेकिन वहाँ एक तेज़ तरीका है? (मुझे लगता है कि cumsum थोड़ा सा समय भी 0 और 1 के योग होगा)।

संपादित करें: मुझे लगता है कि मैं और भी अधिक की तुलना में मैं तेजी से जरूरत vectorized - श्री Fooz 'पाश महान है लेकिन MATLAB में प्रत्येक पाश समय भले ही वह तेजी से है दूर करने में मुझे एक बहुत खर्च हो रहा है।

Answer 1

जैसा कि Mr Fooz द्वारा दिखाया गया है, क्योंकि लूप अब MATLAB के नए संस्करणों के साथ बहुत तेज़ हो सकते हैं। हालांकि, अगर आप वास्तव में कॉम्पैक्ट vectorized कोड करना चाहते हैं, मैं इस कोशिश कर सुझाव है:

[B,I] = max(flipud(A)); 
I = size(A,1)-I+1; 

यह आपके CUMSUM आधारित जवाब की तुलना में तेजी है, लेकिन अभी भी रूप में तेजी से नहीं काफी श्री Fooz के लूपिंग विकल्प के रूप में।

दो अतिरिक्त बातों पर विचार करने के लिए:

• क्या परिणाम आप एक कॉलम में कोई लोगों को नहीं है कि सभी के लिए प्राप्त करना चाहते हैं? उपर्युक्त विकल्प के साथ मैंने आपको दिया, मुझे विश्वास है कि आपको आकार (ए, 1) (यानी में पंक्तियों की संख्या) इस तरह के मामले में एक सूचकांक प्राप्त होगा। आपके विकल्प के लिए, मेरा मानना ​​है कि आपको इस तरह के मामले में 1 मिलेगा, जबकि श्री फूज़ से नेस्टेड-फॉर-लूप विकल्प आपको 0

• इन विभिन्न विकल्पों की सापेक्ष गति के आधार पर अलग-अलग होंगे का आकार और गैर-शून्यों की संख्या जो आप उम्मीद करते हैं।

Answer 2

फास्ट वही है जो आपको चिंता करना चाहिए, जरूरी नहीं कि पूर्ण वेक्टरनाइज़ेशन। Matlab के हाल के संस्करण बहुत कुशलतापूर्वक लूप को संभालने के बारे में समझदार हैं। यदि कुछ व्यक्त करने का एक कॉम्पैक्ट वेक्टरीकृत तरीका है, तो यह आमतौर पर तेज़ होता है, लेकिन लूप को हमेशा (हमेशा) डरना नहीं चाहिए जैसा कि वे होते थे।

clc 

A = rand(5000)>0.5; 
A(1,find(sum(A,1)==0)) = 1; % make sure there is at least one match 

% Slow because it is doing too much work 
tic;[B,I1]=max(cumsum(A));toc 

% Fast because FIND is fast and it runs the inner loop 
tic; 
I3=zeros(1,5000); 
for i=1:5000 
    I3(i) = find(A(:,i),1,'last'); 
end 
toc; 
assert(all(I1==I3)); 

% Even faster because the JIT in Matlab is smart enough now 
tic; 
I2=zeros(1,5000); 
for i=1:5000 
    I2(i) = 0; 
    for j=5000:-1:1 
    if A(j,i) 
     I2(i) = j; 
     break; 
    end 
    end 
end 
toc; 
assert(all(I1==I2)); 

R2008a, विंडोज़, x64 पर, cumsum संस्करण 0.9 सेकंड लेता है। लूप और खोज संस्करण 0.02 सेकंड लेता है। डबल लूप संस्करण में केवल 0.001 सेकेंड लगते हैं।

संपादित करें: कौन सा सबसे तेज़ डेटा पर निर्भर करता है। जब आप 0.5 से 0.999 बदलते हैं तो डबल-लूप 0.05 सेकेंड लेता है (क्योंकि ब्रेक को हिट करने में अधिक समय लगता है; औसत पर)। cumsum और लूप & पाते हैं कार्यान्वयन में अधिक लगातार गति है।

संपादित करें 2: gnovice का फ्लिपड समाधान चालाक है। दुर्भाग्यवश, मेरी टेस्ट मशीन पर 0.1 सेकंड लगते हैं, इसलिए यह cumsum से बहुत तेज है, लेकिन looped संस्करणों की तुलना में धीमी है।