14

ビット文字列として解釈される MATLAB uint32 が与えられた場合、文字列に含まれる非ゼロ ビットの数を効率的かつ簡潔にカウントする方法は何ですか?

ビットをループする実用的で単純なアプローチがありますが、それは私のニーズには遅すぎます。(std::bitset count() を使用した C++ 実装はほぼ瞬時に実行されます)。

さまざまなビット カウント手法をリストしている非常に優れたページを見つけましたが、簡単な MATLAB 風の方法があることを願っています。

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


更新 #1

Brian Kernighan アルゴリズムを次のように実装しました。

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

パフォーマンスは依然として悪く、4096^2 の重み計算を計算するのに 10 秒以上かかります。std::bitset の count() を使用する私の C++ コードは、これを 1 秒未満の時間で実行します。


アップデート #2

これまでに試した手法の実行時間の表を次に示します。追加のアイデアや提案があれば更新します。

ベクトル化されたシャイナー アルゴリズム => 2.243511 秒
ベクトル化された Naive bitget ループ => 7.553345 秒
カーニガン アルゴリズム => 17.154692 秒
length( find( bitget( val, 1:32 ) ) ) => 67.368278 秒
nnz( bitget( val, 1:32 ) ) => 349.620259 秒
Justin Scheiner のアルゴリズム、展開されたループ => 370.846031 秒
Justin Scheiner のアルゴリズム => 398.786320 秒
単純な bitget ループ => 456.016731 秒
合計 (dec2bin(val) == '1') => 1069.851993 秒


コメント: MATLAB の dec2bin() 関数は、実装が非常に不十分なようです。実行速度が非常に遅いです。

コメント: 「Naive bitget loop」アルゴリズムは次のように実装されています。

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

コメント: シャイナーのアルゴリズムのループ展開バージョンは次のようになります。

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));
4

9 に答える 9

5

これがMATLAB実装の演習でない限り、高速のC ++実装を使用して、ターゲットプラットフォームごとに1回、mex関数としてコンパイルすることをお勧めします。

于 2009-06-22T00:24:53.117 に答える
5

上部のスタンフォード リンクから「ベスト 32 ビット アルゴリズム」を実装しました。改善されたアルゴリズムにより、処理時間が 6% 短縮されました。また、セグメント サイズを最適化し、32K が安定しており、4K よりも 15% 時間が改善されることがわかりました。4Kx4K の時間は、ベクトル化されたシャイナー アルゴリズムの 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
于 2012-07-01T16:24:24.550 に答える
5

編集：新しいソリューション

UINT32 値の 4096 行 4096 列の配列内のすべての要素に対して計算を繰り返したいようです。これがあなたがしていることである場合、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

他のいくつかのアルゴリズムのベクトル化バージョンを作成したい場合、BITANDも行列で動作するように設計されていると思います。

古いソリューション...

私が考えることができる最も簡単な方法は、DEC2BIN関数を使用することです。これは、負でない整数のバイナリ表現 (文字列として) を提供します。

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

遅いですが、簡単です。=)

于 2009-06-21T23:49:56.993 に答える
1

手っ取り早い方法は、ルックアップ テーブルを使用して各バイトのビットをカウントし、これらの値を合計することです。実際、これは質問で指定された Web ページで提案されているアプローチの 1 つです。このアプローチの優れた点は、ルックアップと合計の両方が MATLAB でベクトル化可能な操作であるため、このアプローチをベクトル化して、多数のビット文字列のハミング重み/セット ビット数を同時に非常に迅速に計算できることです。このアプローチは、MATLAB File Exchangeのbitcountサブミッションに実装されています。

于 2013-11-27T11:34:38.310 に答える
1

Matlab Cody でタイミング比較を行いました。セグメント化された修正済みのベクトル化されたシャイナーが最適なパフォーマンスを提供すると判断しました。

L=4096*4096 ベクトルの Cody 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
于 2012-07-01T06:12:16.327 に答える
0 
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
于 2012-06-29T14:09:38.540 に答える