Cálculo eficiente del peso de Hamming en matlab
https://stackoverflow.com/questions/1024904
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Dado que un MATLAB uint32 debe interpretarse como una cadena de bits, ¿cuál es una manera eficiente y concisa de contar cuántos bits distintos de cero hay en la cadena?
Tengo un enfoque funcional e ingenuo que recorre los bits, pero eso es demasiado lento para mis necesidades. (Una implementación de C ++ usando std :: bitset count () se ejecuta casi instantáneamente).
He encontrado una página bastante agradable que enumera varias técnicas de conteo de bits, pero espero que haya una forma fácil de MATLAB.
http://graphics.stanford.edu/~seander/bithacks.html# CountBitsSetNaive
Actualización # 1
Acabo de implementar el algoritmo Brian Kernighan de la siguiente manera:
w = 0;
while ( bits > 0 )
bits = bitand( bits, bits-1 );
w = w + 1;
end
El rendimiento sigue siendo malo, más de 10 segundos para calcular solo 4096 ^ 2 cálculos de peso. Mi código C ++ usando count () de std :: bitset hace esto en un segundo.
Actualización # 2
Aquí hay una tabla de tiempos de ejecución para las técnicas que he probado hasta ahora. Lo actualizaré a medida que tenga 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 implementada. Funciona extremadamente lento.
Comentario : El " Bucle de bitget ingenuo " El algoritmo se implementa de la siguiente manera:
w=0;
for i=1:32
if bitget( val, i ) == 1
w = w + 1;
end
end
Comentario : La versión desenrollada en bucle del algoritmo de Scheiner tiene el siguiente aspecto:
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));
Solución
Me interesaría ver qué tan rápida es esta solución:
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 'paralela' dada en la página de bithacks.
Otros consejos
A menos que este sea un ejercicio de implementación de MATLAB, es posible que desee tomar su rápida implementación de C ++ y compilarla como una función mex, una vez por plataforma de destino.
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 que BITAND también está diseñado para operar en matrices.
La solución anterior ...
La forma más fácil que se me ocurre es utilizar el Función DEC2BIN , que le proporciona la representación binaria (como una cadena) de un entero no negativo:
w = sum(dec2bin(num) == '1'); % Sums up the ones in the string
Es lento, pero es fácil. =)
Implementó el " Mejor algoritmo de 32 bits " desde el enlace de Stanford en la parte superior. El algoritmo mejorado redujo el tiempo de procesamiento en un 6%. También optimicé el tamaño del segmento y descubrí que 32K es estable y mejora el tiempo en un 15% sobre 4K. Se espera que el tiempo de 4Kx4K sea el 40% del algoritmo de Scheiner vectorizado.
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
Hice algunas comparaciones de tiempo en Matlab Cody. Determinar un esquema vectorizado modificado segmentado proporciona un rendimiento óptimo.
Tiene una reducción de tiempo de > 50% basada en el cambio de Cody 1.30 segundos a 0.60 segundos 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
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 que figura 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 establecidos de un gran número de cadenas de bits simultáneamente, muy rápidamente. Este enfoque se implementa en el bitcount en el intercambio de archivos MATLAB.
Intente dividir el trabajo en partes más pequeñas. Supongo que si desea procesar todos los datos a la vez, matlab está tratando de hacer cada operación en todos los enteros antes de tomar pasos sucesivos y la memoria caché del procesador se invalida con cada paso.
for i=1:4096,
«process bits(i,:)»
end
Estoy reviviendo un hilo antiguo aquí, pero me encontré con este problema y escribí este pequeño código para él:
distance = sum(bitget(bits, 1:32));
Parece bastante conciso, pero tengo miedo de que bitget se implemente en las operaciones O (n) bitshift . El código funciona para lo que voy, pero mi conjunto de problemas no depende del peso pesado.
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
