Calcolo efficiente del peso di Hamming in MATLAB
https://stackoverflow.com/questions/1024904
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Dato un MATLAB uint32 da interpretare come una stringa di bit, qual è un modo efficiente e conciso di contare quanti bit diversi da zero sono nella stringa?
Ho un approccio funzionante e ingenuo che circola sui bit, ma è troppo lento per le mie esigenze. (Un'implementazione C ++ che usa std :: bitset count () viene eseguita quasi istantaneamente).
Ho trovato una bella pagina che elenca varie tecniche di conteggio dei bit, ma spero che ci sia un modo semplice MATLAB-esque.
http://graphics.stanford.edu/~seander/bithacks.html# CountBitsSetNaive
Aggiornamento n. 1
Ho appena implementato l'algoritmo Brian Kernighan come segue:
w = 0;
while ( bits > 0 )
bits = bitand( bits, bits-1 );
w = w + 1;
end
Le prestazioni sono ancora scadenti, oltre 10 secondi per calcolare solo 4096 ^ 2 calcoli di peso. Il mio codice C ++ che usa count () da std :: bitset lo fa in un secondo.
Aggiornamento n. 2
Ecco una tabella dei tempi di esecuzione per le tecniche che ho provato finora. Lo aggiornerò man mano che ricevo ulteriori idee / suggerimenti.
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
Commento : la funzione dec2bin () in MATLAB sembra essere implementata in modo molto scadente. Funziona estremamente lentamente.
Commento : il loop di quotazioni naïf " l'algoritmo è implementato come segue:
w=0;
for i=1:32
if bitget( val, i ) == 1
w = w + 1;
end
end
Commento : La versione loop srotolata dell'algoritmo di Scheiner ha il seguente aspetto:
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));
Soluzione
Sarei interessato a vedere quanto è veloce questa soluzione:
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
Tornando indietro, vedo che questa è la soluzione "parallela" fornita nella pagina dei bithacks.
Altri suggerimenti
A meno che questo non sia un esercizio di implementazione di MATLAB, potresti voler prendere la tua veloce implementazione C ++ e compilarla come una funzione mex, una volta per piattaforma di destinazione.
MODIFICA: NUOVA SOLUZIONE
Sembra che tu voglia ripetere il calcolo per ogni elemento in un array 4096 per 4096 di valori UINT32. Se questo è ciò che stai facendo, penso che il modo più veloce per farlo in MATLAB sia usare il fatto che BITGET è progettato per operare su matrici di valori. Il codice sarebbe simile al seguente:
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 vuoi creare versioni vettoriali di alcuni degli altri algoritmi, credo BITAND è anche progettato per operare su matrici.
La vecchia soluzione ...
Il modo più semplice a cui riesco a pensare è usare DEC2BIN , che ti dà la rappresentazione binaria (come stringa) di un numero intero non negativo:
w = sum(dec2bin(num) == '1'); % Sums up the ones in the string
È lento, ma è facile. =)
Implementato l'algoritmo Best 32 bit " dal collegamento di Stanford in alto. L'algoritmo migliorato ha ridotto i tempi di elaborazione del 6%. Inoltre ha ottimizzato le dimensioni del segmento e ha scoperto che 32K è stabile e migliora il tempo del 15% su 4K. Aspettatevi che il tempo 4Kx4K sia il 40% dell'algoritmo di Vectorized 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
Ha effettuato alcuni confronti temporali su Matlab Cody. Determinato uno Scheiner Vectorized modificato segmentato offre prestazioni ottimali.
Riduzione del tempo del 50% basata su Cody da 1,30 a 0,60 secondi per un vettore 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 approccio rapido sta contando i bit in ogni byte usando una tabella di ricerca, quindi sommando questi valori; infatti, è uno degli approcci suggeriti nella pagina web fornita nella domanda. La cosa bella di questo approccio è che sia la ricerca che la somma sono operazioni vettorializzabili in MATLAB, quindi puoi vettorializzare questo approccio e calcolare il peso di martellamento / numero di bit impostati di un gran numero di stringhe di bit contemporaneamente, molto rapidamente. Questo approccio è implementato nella bitcount sullo scambio di file MATLAB.
Prova a dividere il lavoro in parti più piccole. La mia ipotesi è che se si desidera elaborare tutti i dati contemporaneamente, matlab sta cercando di eseguire ogni operazione su tutti i numeri interi prima di eseguire passaggi successivi e la cache del processore viene invalidata con ogni passaggio.
for i=1:4096,
«process bits(i,:)»
end
Sto rianimando un vecchio thread qui, ma ho riscontrato questo problema e ho scritto questo piccolo codice per esso:
distance = sum(bitget(bits, 1:32));
Sembra piuttosto conciso, ma ho paura che bitget sia implementato nelle operazioni O (n) bitshift . Il codice funziona per quello che sto andando, ma il mio set di problemi non si basa sul peso martellante.
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
