मैटलैब दोहराया आव्यूह गुणन - पाश बनाम निर्मित प्रदर्शन

Question

एक मैट्रिक्स A देखते हुए, मैं अन्य n वैक्टर Bi (अर्थात i=1...n) के साथ गुणा करने की आवश्यकता। A का आकार 5000x5000 जैसा हो सकता है और इस प्रकार Bi5000x1 जैसा हो सकता है।

अगर मैं निम्नलिखित तरीके से उत्पाद का मूल्यांकन: (परिमाण)

for i=1:n 
    product=A*Bi; 
    % do something with product 
end 

परिणाम तरीका है जैसे उत्पादों कंप्यूटिंग की तुलना में धीमी:

%assume that S is a matrix that contains the vectors Bi as columns, i.e. S(:,i)=Bi, then: 
results=A*S; %stores all the products in matrix form 
% do something with results 

समस्या

कि संख्या है n वेक्टर Bi स्मृति में संग्रहीत करने के लिए बहुत बड़ा हो सकता है, उदाहरण के लिए n=300000, इसलिए मुझे एक लूप दृष्टिकोण का उपयोग करने की आवश्यकता है जहां हर बार जब मैं उत्पाद का मूल्यांकन करता हूं, इसका उपयोग करता हूं और फिर वेक्टर Bi को त्याग देता हूं।

प्रत्यक्ष गुणा की तुलना में ऐसा दृष्टिकोण इतना धीमा क्यों है, और इस पर काबू पाने के तरीके हैं?

Answer 1

तुम इतनी उदाहरण

के लिए

for i = 0:(n/k)-1 
    product = A*S(:,(i*k+1):(i+1)*k) 
end 

बैचों से अधिक पाश की कोशिश और k समायोजित आप के लिए गति और स्मृति के बंद सबसे अच्छा व्यापार को खोजने के लिए कर सकते हैं।

MATLAB के लूप धीमे हैं क्योंकि यह एक व्याख्या की गई भाषा है। तो इसे फ्लाई पर बहुत सी चीजें काम करना है। जेआईटी कंपाइलर की वजह से इन दिनों लूपों में काफी सुधार हुआ है, लेकिन वे अभी भी अंतर्निहित कार्यों की तुलना में धीमे हैं जो सी में लिखे और संकलित किए गए हैं। इसके अलावा, वे वास्तव में बढ़ते सुपर फास्ट मैट्रिक्स गुणा एल्गोरिदम का उपयोग करते हैं, जैसा कि तुलना में लूपिंग द्वारा प्राप्त आपके निष्पक्ष निष्पक्ष एल्गोरिदम के साथ, जो आप जिस गति-गति का अनुभव कर रहे हैं उसमें भी सहायता करते हैं।

Answer 2

सादगी के लिए मेरा उत्तर एन-बाय-एन स्क्वायर मैट्रिक्स ए मान लेगा, लेकिन यह गैर वर्गों के लिए भी सच है।

आपका लूप दृष्टिकोण मैट्रिक्स वेक्टर गुणा का उपयोग करता है। बेवकूफ समाधान भी सबसे अच्छा ज्ञात है, जिसके परिणामस्वरूप ओ (एन^2) का रनटाइम होता है जिसे बार बार दोहराया जाता है। आप ओ (एन^3) के कुल रनटाइम के साथ समाप्त होते हैं।

मैट्रिक्स गुणा के लिए, एक बेहतर दृष्टिकोण है। सबसे अच्छी तरह से ज्ञात एल्गोरिदम केवल ओ (एन^2.4) रनटाइम से कम की आवश्यकता है, जो इसे बड़ी संख्या के लिए बहुत तेज बनाता है।

मैट्रिक्स गुणा का उपयोग करते हुए एक बार कई वैक्टरों को गुणा करते समय आप बेहतर रनटाइम प्राप्त करेंगे। यह शुद्ध मैट्रिक्स गुणा के प्रदर्शन को प्राप्त नहीं करेगा, लेकिन बी के बड़े स्लाइस के साथ काम करना शायद सबसे तेज़ स्मृति कुशल समाधान है।

अलग चर्चा की दृष्टिकोण के लिए कुछ कोड:

n=5000; 
k=100; 
A=rand(n,n); 
S=rand(n,n); 
workers=matlabpool('size'); 
%for a parfor solution, the batch size must be smaller because multiple batches are stred in memory at once 
kparallel=k/workers; 
disp('simple loop:'); 
tic; 
for i = 1:n 
    product = A*S(:,n); 
end 
toc 
disp('batched loop:'); 
tic; 
for i = 1:(n/k) 
    product = A*S(:,(i-1)*k+1:(i)*k); 
end 
toc 
disp('batched parfor loop:'); 
tic; 
parfor i = 1:(n/kparallel) 
    product = A*S(:,(i-1)*kparallel+1:(i)*kparallel); 
end 
toc 
disp('matrix multiplication:'); 
tic; 
A*S; 
toc 

Answer 3

@Dan's answer के अलावा आप समानांतर जा रहा कोशिश कर सकते हैं में, बशर्ते आप पर्याप्त कोर और बड़ा पर्याप्त संचालन सुनिश्चित करने के लिए यह लाभदायक (स्मृति के बारे में अधिक जानकारी के लिए this answer देखना है parfor की खपत):

parfor ii = 0:(n/k)-1 
    product = A*S(:,(ii*k+1):(ii+1)*k) 
end 

मैं docs on mtimes (* ऑपरेटर में नहीं देख सकते हैं) है कि क्या यह परोक्ष थ्रेड है, लेकिन यह है मुझे लगता है कि एक शॉट के लायक है।

Answer 4

मैट्रिक्स के साथ प्रत्येक सरणी के गुणों को करने के लिए बस मैट्रिक्स को एक मैट्रिक्स के साथ गुणा करें जो स्तंभों के रूप में आपके इच्छित सरणी होंगे।

तो आप जाँच करना चाहते हैं तो इस

अगर

size(a)=3,3 

तो

a*b==horzcat(a*b(:,1),a*b(:,2),a*b(:,3)) 

आप पाश

से बहुत समय बचाने के सच

इस तरह है