matlab

Question

में कुशलतापूर्वक हथौड़ा वजन की गणना करना एक MATLAB uint32 को थोड़ा स्ट्रिंग के रूप में व्याख्या करने के लिए दिया गया है, यह समझने का एक कुशल और संक्षिप्त तरीका क्या है कि स्ट्रिंग में कितने nonzero बिट्स हैं?

मेरे पास एक कामकाजी, निष्पक्ष दृष्टिकोण है जो बिट्स पर लूप करता है, लेकिन यह मेरी आवश्यकताओं के लिए बहुत धीमा है। (Std :: बिटसेट गिनती() का उपयोग कर एक सी ++ कार्यान्वयन लगभग तुरंत चलता है)।

मुझे विभिन्न बिट गिनती तकनीकों को सूचीबद्ध करने वाला एक बहुत अच्छा पृष्ठ मिला है, लेकिन मुझे आशा है कि एक आसान MATLAB-esque तरीका है।

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

अद्यतन # 1

बस ब्रायन Kernighan एल्गोरिथ्म कार्यान्वित इस प्रकार है:

w = 0; 
while (bits > 0) 
    bits = bitand(bits, bits-1); 
    w = w + 1; 
end 

प्रदर्शन गणना करने के लिए सिर्फ 4096^2 वजन, अभी भी भद्दा है 10 सेकंड से अधिक गणना। Std :: bitset से गिनती() का उपयोग कर मेरा सी ++ कोड उपसेकंद समय में करता है।

# 2

यहाँ अद्यतन तकनीक मैं अब तक की कोशिश की है के लिए रन समय की एक टेबल है। मैं इसे अपडेट कर दूंगा क्योंकि मुझे अतिरिक्त विचार/सुझाव मिलते हैं।

 
Vectorized Scheiner algorithm    => 2.243511 sec 
Vectorized Naive bitget loop     => 7.553345 sec 
Kernighan algorithm       => 17.154692 sec 
length(find(bitget(val, 1:32)))  => 67.368278 sec 
nnz(bitget(val, 1:32))     => 349.620259 sec 
Justin Scheiner's algorithm, unrolled loops => 370.846031 sec 
Justin Scheiner's algorithm     => 398.786320 sec 
Naive bitget loop       => 456.016731 sec 
sum(dec2bin(val) == '1')      => 1069.851993 sec 

टिप्पणी: MATLAB में dec2bin() फ़ंक्शन बहुत खराब लागू किया जा रहा है। यह बहुत धीमी गति से चलता है।

टिप्पणी: "अनुभवहीन bitget लूप" एल्गोरिथ्म के रूप में कार्यान्वित किया जाता है इस प्रकार है:

w=0; 
for i=1:32 
    if bitget(val, i) == 1 
     w = w + 1; 
    end 
end 

टिप्पणी: इस प्रकार Scheiner एल्गोरिथ्म के पाश unrolled संस्करण लगता है जैसे:

function w=computeWeight(val) 
w = val; 
w = bitand(bitshift(w, -1), uint32(1431655765)) + ... 
    bitand(w, uint32(1431655765)); 

w = bitand(bitshift(w, -2), uint32(858993459)) + ... 
    bitand(w, uint32(858993459)); 

w = bitand(bitshift(w, -4), uint32(252645135)) + ... 
    bitand(w, uint32(252645135)); 

w = bitand(bitshift(w, -8), uint32(16711935)) + ... 
    bitand(w, uint32(16711935)); 

w = bitand(bitshift(w, -16), uint32(65535)) + ... 
    bitand(w, uint32(65535)); 

Answer 1

मैं देखना कितनी तेजी से यह समाधान है रुचि होगी:

function r = count_bits(n) 

shifts = [-1, -2, -4, -8, -16]; 
masks = [1431655765, 858993459, 252645135, 16711935, 65535]; 

r = n; 
for i=1:5 
    r = bitand(bitshift(r, shifts(i)), masks(i)) + ... 
     bitand(r, masks(i)); 
end 

वापस जा रहे हैं, मुझे लगता है कि यह 'समानांतर' bithacks पेज पर दिए गए समाधान है।

Answer 2

संपादित करें: नया समाधान

ऐसा प्रतीत होता है कि आप UINT32 मानों के 4096-by-4096 सरणी में प्रत्येक तत्व के लिए गणना दोहराना चाहते हैं। यदि आप यही कर रहे हैं, तो मुझे लगता है कि MATLAB में ऐसा करने का सबसे तेज़ तरीका इस तथ्य का उपयोग करना है कि BITGET मूल्यों के matrices पर काम करने के लिए डिज़ाइन किया गया है। कोड इस तरह दिखेगा:

numArray = ...your 4096-by-4096 matrix of uint32 values... 
w = zeros(4096,4096,'uint32'); 
for iBit = 1:32, 
    w = w+bitget(numArray,iBit); 
end 

आप अन्य एल्गोरिदम में से कुछ की vectorized संस्करणों बनाना चाहते हैं, मेरा मानना ​​है कि BITAND भी मैट्रिक्स पर संचालित करने के लिए बनाया गया है।

---

पुराना समाधान ...

सबसे आसान तरीका है मैं के बारे में सोच सकते हैं DEC2BIN समारोह है, जो आप द्विआधारी प्रतिनिधित्व एक गैर नकारात्मक पूर्णांक के देता है (एक स्ट्रिंग के रूप में) का उपयोग करने के लिए है:

w = sum(dec2bin(num) == '1'); % Sums up the ones in the string 

यह धीमी है, लेकिन यह आसान है । =)

Answer 3

जब तक यह एक MATLAB कार्यान्वयन अभ्यास नहीं है, तो आप प्रति लक्ष्य प्लेटफॉर्म पर एक बार अपने तेज सी ++ कार्यान्वयन को एक मैक्स फ़ंक्शन के रूप में लेना चाहते हैं।

Answer 4

नौकरी को छोटे भागों में विभाजित करने का प्रयास करें। मेरा अनुमान है कि यदि आप एक ही समय में सभी डेटा को संसाधित करना चाहते हैं, तो मैटलैब लगातार चरणों को लेने से पहले सभी इंटीग्रियों पर प्रत्येक ऑपरेशन करने की कोशिश कर रहा है और प्रत्येक चरण के साथ प्रोसेसर का कैश अमान्य है।

for i=1:4096, 
    «process bits(i,:)» 
end 

Answer 5

मैं यहाँ एक पुराने धागा पुनर्जीवित कर रहा हूँ, लेकिन मैं इस समस्या को भर में भाग गया और मैं इसके लिए कोड का यह छोटा सा लिखा है:

distance = sum(bitget(bits, 1:32)); 

बहुत संक्षिप्त लग रहा है, लेकिन मुझे लगता है कि डर कर रहा हूँ bitget ओ (एन) bitshift संचालन में लागू किया गया है। कोड जो मैं जा रहा हूं उसके लिए काम करता है, लेकिन मेरी समस्या सेट वजन घटाने पर निर्भर नहीं है।

Answer 6

num_ones=uint8(zeros(intmax('uint32')/2^6,1)); 
% one time load of array not implemented here 
tic 
for i=1:4096*4096 
%v=num_ones(rem(i,64)+1)+num_ones(floor(i/64)+1); % 1.24 sec 
v=num_ones(mod(i,64)+1)+num_ones(floor(i/64)+1); % 1.20 sec 
end 
toc 
tic 
num_ones=uint8(zeros(65536,1)); 
for i=0:65535 
num_ones(i+1)=length(find(bitget(i, 1:32))) ; 
end 
toc 
% 0.43 sec to load 
% smaller array to initialize 
% one time load of array 
tic 
for i=1:4096*4096 
v=num_ones(mod(i,65536)+1)+num_ones(floor(i/65536)+1); % 0.95 sec 
%v=num_ones(mod(i,65536)+1)+num_ones(bitshift(i,-16)+1); % 16 sec for 4K*1K 
end 
toc 
%vectorized 
tic 
num_ones=uint8(zeros(65536,1)); 
for i=0:65535 
num_ones(i+1)=length(find(bitget(i, 1:32))) ; 
end % 0.43 sec 
toc 
vt=randi(2^32,[4096*4096,1])-1; 
tic 
v=num_ones(mod(vt,65536)+1)+num_ones(floor(vt/65536)+1); % 0.85 sec 
toc 

Answer 7

मैटलैब कोडी पर कुछ समय तुलना की गई। एक विभाजित संशोधित वेक्टरिज्ड Scheiner निर्धारित अधिकतम प्रदर्शन देता है।

> एल = 4096 * 4096 वेक्टर के लिए कोडी 1.30 सेकंड से 0.60 सेकेंड के आधार पर 50% समय की कमी है।

function w = Ham(w) 
% Input uint32 
% Output vector of Ham wts 

b1=uint32(1431655765); % evaluating saves 15% of time 1.30 to 1.1 sec 
b2=uint32(858993459); 
b3=uint32(252645135); 
b4=uint32(16711935); 
b5=uint32(65535); 

for i=1:4096:length(w) 
    w(i:i+4095)=Ham_seg(w(i:i+4095),b1,b2,b3,b4,b5); 
end 
end 

% Segmentation reduced time by 50% 

function w=Ham_seg(w,b1,b2,b3,b4,b5) 
% Passing variables or could evaluate b1:b5 here 


w = bitand(bitshift(w, -1), b1) + bitand(w, b1); 
w = bitand(bitshift(w, -2), b2) + bitand(w, b2); 
w = bitand(bitshift(w, -4), b3) + bitand(w, b3); 
w = bitand(bitshift(w, -8), b4) + bitand(w, b4); 
w = bitand(bitshift(w, -16), b5) + bitand(w, b5); 

end 





vt=randi(2^32,[4096*4096,1])-1; 
% for vt being uint32 the floor function gives unexpected values 
tic 
v=num_ones(mod(vt,65536)+1)+num_ones(floor(vt/65536)+1); % 0.85 sec 
toc 
% a corrected method is 
v=num_ones(mod(vt,65536)+1)+num_ones(floor(double(vt)/65536)+1); 
toc 

Answer 8

शीर्ष पर स्टैनफोर्ड लिंक से "सर्वश्रेष्ठ 32 बिट एल्गोरिदम" कार्यान्वित किया गया। बेहतर एल्गोरिदम ने 6% तक प्रसंस्करण समय कम किया। ने सेगमेंट आकार को भी अनुकूलित किया और पाया कि 32K स्थिर है और 4K से 15% तक समय में सुधार करता है। 4Kx4K समय को वेक्टरिज्ड Scheiner एल्गोरिदम का 40% होने की उम्मीद है।

function w = Ham(w) 
% Input uint32 
% Output vector of Ham wts 
for i=1:32768:length(w) 
    w(i:i+32767)=Ham_seg(w(i:i+32767)); 
end 
end 

% Segmentation gave reduced time by 50% 

function w=Ham_seg(w) 
%speed 
b1=uint32(1431655765); 
b2=uint32(858993459); 
b3=uint32(252645135); 
b7=uint32(63); % working orig binary mask 

w = bitand(bitshift(w, -1), b1) + bitand(w, b1); 
w = bitand(bitshift(w, -2), b2) + bitand(w, b2); 
w =bitand(w+bitshift(w, -4),b3); 
w =bitand(bitshift(w,-24)+bitshift(w,-16)+bitshift(w,-8)+w,b7); 

end 

Answer 9

एक तेज़ दृष्टिकोण एक लुकअप टेबल का उपयोग करके प्रत्येक बाइट में बिट्स की गणना कर रहा है, फिर इन मानों को जोड़ना; वास्तव में, यह प्रश्न में दिए गए वेब पेज पर सुझाए गए दृष्टिकोणों में से एक है। इस दृष्टिकोण के बारे में अच्छी बात यह है कि दोनों लुकअप और योग MATLAB में वेक्टरिजेबल ऑपरेशंस हैं, इसलिए आप इस दृष्टिकोण को सदिश कर सकते हैं और एक साथ बड़ी संख्या में बिट स्ट्रिंग्स के सेट बिट्स के हथौड़ा वजन/संख्या की गणना कर सकते हैं। यह दृष्टिकोण MATLAB फ़ाइल एक्सचेंज पर bitcount सबमिशन में कार्यान्वित किया गया है।