حساب المبالغة الوزن بكفاءة في matlab

Question

نظرا MATLAB uint32 أن تفسر على أنها سلسلة بت, ما هو فعال وموجزة طريقة إحصاء عدد غير صفرية بت في السلسلة ؟

لدي العامل ، من السذاجة نهج الحلقات على البتات ، لكنها بطيئة جدا لاحتياجاتي.(تنفيذ C++ باستخدام std::bitset عدد() يعمل على الفور تقريبا).

لقد وجدت جميلة جدا صفحة سرد مختلف قليلا تقنيات العد, ولكن أنا على أمل هناك سهلة MATLAB سقو.

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

تحديث #1

فقط نفذ براين كيرنيغان الخوارزمية على النحو التالي:

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

الأداء لا يزال كربي, أكثر من 10 ثوان إلى حساب فقط 4096^2 حسابات الوزن.بلدي رمز C++ باستخدام عدد() من الأمراض المنقولة جنسيا::bitset هل هذا في subsecond الوقت.

تحديث #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

التعليق:على dec2bin() وظيفة في مطلب يبدو ضعيفا جدا تنفيذها.تشغيله بطيئة للغاية.

التعليق:"من السذاجة bitget حلقة" خوارزمية تنفذ على النحو التالي:

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

التعليق:حلقة بسطه نسخة من Scheiner خوارزمية يبدو كما يلي:

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

إلا إذا كان هذا هو مطلب تنفيذ العملية ، قد تريد أن تأخذ فقط الخاص بك سريع C++ تنفيذ وتجميع أنها mex وظيفة ، مرة واحدة في النظام الأساسي الهدف.

Answer 3

تحرير:حل جديد

ويبدو أن كنت ترغب في تكرار حساب لكل عنصر في 4096-من قبل-4096 مجموعة من UINT32 القيم.إذا كان هذا هو ما تقوم به, أعتقد أن أسرع طريقة للقيام بذلك في MATLAB هو استخدام حقيقة أن BITGET هي مصممة للعمل على المصفوفات من القيم.رمز تبدو مثل هذا:

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 4

نفذت "أفضل 32 بت خوارزمية" من جامعة ستانفورد الرابط في الأعلى.تحسين خوارزمية تخفيض وقت المعالجة بنسبة 6%.الأمثل أيضا حجم قطعة وجدت أن 32K مستقرة ويحسن الوقت بنسبة 15% على 4K.نتوقع 4Kx4K الوقت إلى أن 40% من Vectorized Scheiner الخوارزمية.

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 5

هل توقيت بعض المقارنات على Matlab كودي.تحديد مجزأة تعديل Vectorized Scheiner يعطي optimimum الأداء.

لديك >50% تخفيض الوقت على أساس كودي 1.30 ثانية إلى 0.60 ثانية تغيير L=4096*4096 ناقلات.

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 6

سريع النهج عد بت في كل بايت باستخدام جدول البحث ، ثم تلخيص هذه القيم ؛ في الواقع, انها واحدة من النهج المقترح على صفحة ويب معينة في السؤال.الشيء الجميل في هذا النهج هو أن كل بحث و المبلغ vectorizable العمليات في MATLAB ، حتى تتمكن من vectorize هذا النهج وحساب المبالغة الوزن / عدد تعيين بت من عدد كبير من بت سلاسل في آن واحد ، بسرعة جدا.هذا النهج هو الذي نفذ في bitcount التقديم على MATLAB تبادل الملفات.

Answer 7

حاول تقسيم العمل إلى أجزاء أصغر.تخميني هو أنه إذا كنت تريد أن عملية جميع البيانات دفعة واحدة ، matlab تحاول أن تفعل كل عملية على جميع الأعداد الصحيحة قبل اتخاذ الخطوات المتعاقبة و المعالج ذاكرة التخزين المؤقت يبطل مع كل خطوة.

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

Answer 8

أنا إحياء قديم الموضوع هنا لكن انا صادفت هذه المشكلة و لقد كتبت هذا قليلا من التعليمات البرمجية لذلك:

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

تبدو جميلة موجزة ، ولكن أنا خائفة أن bitget يتم تنفيذها في O(n) bitshift عمليات.الكود يعمل ما أنا ذاهب ولكن مشكلتي مجموعة لا تعتمد على المبالغة الوزن.

Answer 9

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