Calculando peso de Hamming de forma eficiente em Matlab

Question

Dada uma uint32 MATLAB a ser interpretado como uma cadeia de bits, o que é uma forma eficiente e concisa de contar quantos bits não nulos estão na corda?

Eu tenho um trabalho, abordagem ingênua que faz um loop sobre os bits, mas isso é muito lento para minhas necessidades. (A implementação C ++ usando std :: bitset count () é executado quase que instantaneamente).

Eu encontrei uma página agradável consideravelmente listando várias técnicas pouco de contagem, mas eu estou esperando há uma maneira MATLAB-esque fácil.

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

Atualização nº 1

Apenas implementado o algoritmo de Brian Kernighan da seguinte forma:

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

O desempenho é ainda de baixa qualidade, com mais de 10 segundos para calcular apenas 4096 ^ 2 cálculos de peso. Meu código C ++ usando count () a partir de std :: bitset faz isso em tempo subsecond.

Atualização # 2

Aqui está uma tabela de tempos de execução para as técnicas que eu tentei até agora. Eu vou atualizá-lo como eu ficar mais idéias / sugestões.

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

Comment : A função DEC2BIN () em MATLAB parece estar muito mal implementado. Corre-se extremamente lento.

Comment : O algoritmo "Naive circuito bitget" é implementado como segue:

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

Comment : A versão de loop desenrolado de olhares algoritmo de Scheiner da seguinte forma:

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

Eu estaria interessado em ver o quão rápido esta solução é:

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

Indo para trás, vejo que esta é a solução 'paralelo' dada na página bithacks.

Answer 2

A menos que este é um exercício de aplicação MATLAB, você pode querer apenas levar a sua rápida implementação C ++ e compilá-lo como uma função mex, uma vez por plataforma de destino.

Answer 3

EDIT: NEW SOLUTION

Parece que você deseja repetir o cálculo para cada elemento em uma matriz de 4096-por-4096 de valores UInt32. Se é isso que você está fazendo, acho que a maneira mais rápida de fazê-lo em MATLAB é usar o fato de que BITGET é projetado para operar em matrizes de valores. O código ficaria assim:

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

Se você quiser fazer versões Vectorized de alguns dos outros algoritmos, acredito BITAND também é projetado para operar em matrizes.

---

A solução antiga ...

A maneira mais fácil que eu posso pensar é usar a função DEC2BIN , que lhe dá a representação binária (como uma string) de um número inteiro não negativo:

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

É lento, mas é fácil. =)

Answer 4

implementou o "Melhor de 32 bits Algorithm" a partir do link Stanford no topo. O algoritmo melhorou o tempo de processamento reduzido em 6%. Além disso optimizado o tamanho do segmento e descobriram que 32K é estável e melhora o tempo de até 15% ao longo de 4K. Espere o tempo 4Kx4K a ser de 40% do Vectorized Scheiner Algorithm.

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

Será que algumas comparações de atraso em Matlab Cody. Determinou uma Vectorized Scheiner segmentada Modificado dá o desempenho óptimo.

Já> redução de tempo de 50% com base no Cody 1,30 seg de 0,60 seg mudança para uma G = 4096 * 4096 vector.

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

Uma abordagem rápida é a contagem dos bits em cada byte, usando uma tabela de consulta, em seguida, soma destes valores; Na verdade, é uma das abordagens sugeridas na página web dada na pergunta. A coisa agradável sobre esta abordagem é que tanto pesquisa e soma são operações vectorizable em MATLAB, para que possa vetorizar esta abordagem e calcular o peso de Hamming / número de bits definidos de um grande número de cadeias de bits simultaneamente, muito rapidamente. Esta abordagem é implementada no bitcount submissão na Bolsa de arquivo MATLAB.

Answer 7

Try splitting the job into smaller parts. My guess is that if you want to process all data at once, matlab is trying to do each operation on all integers before taking successive steps and the processor's cache is invalidated with each step.

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

Answer 8

I'm reviving an old thread here, but I ran across this problem and I wrote this little bit of code for it:

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

Looks pretty concise, but I'm scared that bitget is implemented in O(n) bitshift operations. The code works for what I'm going, but my problem set doesn't rely on hamming weight.

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