Calcular el peso de Hamming eficientemente en matlab

Question

Dado que MATLAB uint32 debe interpretarse como una cadena de bits, ¿cuál es una forma eficiente y concisa de contar cuántos bits distintos de cero hay en la cadena?

Tengo un enfoque ingenuo y funcional que recorre los bits, pero eso es demasiado lento para mis necesidades. (Una implementación C++ usando std :: bitset count() se ejecuta casi instantáneamente).

He encontrado una página muy bonita que enumera varias técnicas de conteo de bits, pero espero que haya una manera fácil de MATLAB.

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

Actualización # 1

Sólo se aplicó el algoritmo de Brian Kernighan de la siguiente manera:

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

rendimiento sigue siendo malo, más de 10 segundos para calcular acaba de 4096^2 Peso cálculos Mi código de C++ que utiliza count() desde std :: bitset hace esto en tiempo de segundo.

Actualización # 2

Aquí es una tabla de tiempos de ejecución de las técnicas que he probado hasta ahora. Lo actualizaré a medida que obtenga ideas/sugerencias adicionales.

 
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 

comentario: La función DEC2BIN() en MATLAB parece estar muy mal implementado. Funciona extremadamente lento.

comentario: El algoritmo de "bucle bitget Naive" se lleva a cabo de la siguiente manera:

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

comentario: La versión desenrollado del bucle del algoritmo de Scheiner es el siguiente:

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

estaría interesado en ver lo rápido que esta solución es:

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 

Volviendo, veo que esta es la solución 'paralelo' dada en la página bithacks.

Answer 2

EDITAR: NUEVA SOLUCIÓN

Parece que desea repetir el cálculo para cada elemento en una matriz 4096 por 4096 de valores UINT32. Si esto es lo que está haciendo, creo que la forma más rápida de hacerlo en MATLAB es utilizar el hecho de que BITGET está diseñado para operar en matrices de valores. El código se vería así:

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 desea hacer versiones vectorizadas de algunos de los otros algoritmos, creo BITAND también está diseñado para funcionar en matrices.

---

La solución anterior ...

La manera más fácil de lo que puedo pensar es utilizar la función DEC2BIN, que le da la representación binaria (como una cadena) de un número entero no negativo:

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

Es lento, pero es fácil . =)

Answer 3

A menos que se trate de un ejercicio de implementación de MATLAB, puede tomar simplemente su implementación rápida de C++ y compilarla como una función mex, una vez por plataforma de destino.

Answer 4

Intente dividir el trabajo en partes más pequeñas. Supongo que si desea procesar todos los datos a la vez, matlab intenta realizar cada operación en todos los enteros antes de dar pasos sucesivos y la memoria caché del procesador se invalida en cada paso.

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

Answer 5

estoy reviviendo un viejo hilo aquí, pero me encontré con este problema y me escribió este poco de código para ello:

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

ve bastante conciso, pero tengo miedo de que bitget se implementa en O (n) bitshift operaciones. El código funciona para lo que voy, pero mi conjunto de problemas no depende de aumentar el peso.

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

hicimos algunas comparaciones de tiempo en Matlab Cody. Determinado un Esquema Vectorizado Modificado y Segmentado que proporciona un rendimiento óptimo.

Tienen> 50% de reducción de tiempo en función de Cody 1,30 segundos a 0,60 segundos de cambio para un vector 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 8

Implementado el "Mejor algoritmo de 32 bits" del enlace de Stanford en la parte superior. El algoritmo mejorado redujo el tiempo de procesamiento en un 6%. También se optimizó el tamaño del segmento y se encontró que 32K es estable y mejora el tiempo en un 15% con respecto a 4K. Espere que el tiempo de 4Kx4K sea el 40% del algoritmo Vectorizado de 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 9

Un enfoque rápido es contar los bits en cada byte utilizando una tabla de búsqueda, y luego sumar estos valores; de hecho, es uno de los enfoques sugeridos en la página web dada en la pregunta. Lo bueno de este enfoque es que tanto la búsqueda como la suma son operaciones vectorizables en MATLAB, por lo que puede vectorizar este enfoque y calcular el peso/número de bits configurados de una gran cantidad de cadenas de bits simultáneamente, muy rápidamente. Este enfoque se implementa en el envío bitcount en MATLAB File Exchange.