Calcul du poids de Hamming efficacement dans matlab

Question

Étant donné que MATLAB uint32 doit être interprété comme une chaîne de bits, quel est un moyen efficace et concis de compter combien de bits non nuls sont dans la chaîne?

J'ai une méthode de travail naïve qui fonctionne, mais c'est trop lent pour mes besoins. (Une implémentation C ++ utilisant std :: bitset count () s'exécute presque instantanément).

J'ai trouvé une page très jolie qui répertorie diverses techniques de comptage de bits, mais j'espère qu'il existe une méthode simple comme MATLAB.

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

Mise à jour n ° 1

Vient de mettre en œuvre l'algorithme de Brian Kernighan comme suit:

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

Les performances sont toujours mauvaises, plus de 10 secondes pour calculer 4096 ^ 2 calculs de poids. Mon code C ++ utilisant count () à partir de std :: bitset le fait en une seconde.

Mise à jour n ° 2

Voici un tableau des temps d'exécution pour les techniques que j'ai essayées jusqu'à présent. Je le mettrai à jour à mesure que des idées / suggestions supplémentaires me parviendront.

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

Commenter : La fonction dec2bin () de MATLAB semble être très mal implémentée. Il est extrêmement lent.

Commentaire : la "boucle de bitmap naïve". L'algorithme est implémenté comme suit:

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

Commentaire : La version déroulée en boucle de l'algorithme de Scheiner se présente comme suit:

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

Je serais intéressé de voir à quelle vitesse cette solution est:

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

En revenant en arrière, je vois qu'il s'agit de la solution "parallèle" indiquée sur la page bithacks.

Answer 2

À moins qu'il s'agisse d'un exercice d'implémentation MATLAB, vous souhaiterez peut-être simplement prendre votre implémentation rapide en C ++ et la compiler en tant que fonction mex, une fois par plate-forme cible.

Answer 3

MODIFIER: NOUVELLE SOLUTION

Il semble que vous souhaitiez répéter le calcul pour chaque élément d'un tableau de valeurs UINT32 4096 sur 4096. Si c'est ce que vous faites, je pense que le moyen le plus rapide de le faire dans MATLAB est d'utiliser le fait que BITGET est conçu pour fonctionner sur des matrices de valeurs. Le code ressemblerait à ceci:

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

Si vous souhaitez créer des versions vectorisées de certains des autres algorithmes, je pense BITAND est également conçu pour fonctionner sur des matrices.

L'ancienne solution ...

Le moyen le plus simple auquel je puisse penser est d'utiliser Fonction DEC2BIN , qui vous donne la représentation binaire (sous forme de chaîne) d'un entier non négatif:

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

C'est lent, mais c'est facile. =)

Answer 4

Implémentation du "Meilleur algorithme 32 bits" du lien Stanford au sommet. L'algorithme amélioré a réduit le temps de traitement de 6%. Également optimisé la taille du segment et constaté que 32K est stable et améliore le temps de 15% sur 4K. Attendez-vous à une durée de 4Kx4K correspondant à 40% de l'algorithme de Scheiner vectorisé.

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

A effectué des comparaisons de temps sur Matlab Cody. Déterminé, un Scheiner vectorisé modifié segmenté donne des performances optimales.

Bénéficiez de> 50% de réduction du temps sur la base d'un changement de Cody de 1,30 à 0,60 seconde pour un vecteur 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

Une approche rapide consiste à compter les bits de chaque octet à l'aide d'une table de correspondance, puis à additionner ces valeurs; En effet, c'est l'une des approches suggérées sur la page Web donnée dans la question. La bonne chose à propos de cette approche est que MATLAB est une opération vectorisable en termes de recherche et de somme. Vous pouvez donc vectoriser cette approche et calculer très rapidement le poids / nombre de bits définis d'un grand nombre de chaînes de bits. Cette approche est implémentée dans la calcul du nombre de bit sur l'échange de fichiers MATLAB.

Answer 7

Essayez de scinder le travail en parties plus petites. Je suppose que si vous souhaitez traiter toutes les données en une fois, Matlab tente d'effectuer chaque opération sur tous les entiers avant de prendre des étapes successives et le cache du processeur est invalidé à chaque étape.

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

Answer 8

Je ressuscite un ancien fil ici, mais je suis tombé sur ce problème et j'ai écrit ce petit code pour cela:

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

Ça a l'air plutôt concis, mais j'ai bien peur que bitget soit implémenté dans les opérations O (n) bitshift . Le code fonctionne pour ce que je vais, mais mon ensemble de problèmes ne repose pas sur le poids de frappe.

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