Calcolo efficiente del peso di Hamming in MATLAB

Question

Dato che uint32 MATLAB deve essere interpretato come una stringa di bit, qual è un modo efficiente e conciso per contare quanti bit diversi da zero sono presenti nella stringa?

Ho un approccio ingenuo e funzionante che scorre sui bit, ma è troppo lento per le mie esigenze. (Un'implementazione in C++ che utilizza std :: bitset count() viene eseguita quasi istantaneamente).

Ho trovato una pagina molto carina che elenca varie tecniche di conteggio dei bit, ma spero che esista un semplice modo MATLAB.

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

Update # 1

appena implementato l'algoritmo di Brian Kernighan come segue:

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

performance è ancora scadente, più di 10 secondi per calcolare solo 4096^2 Peso calcoli. Il mio codice C++ che usa count() da std :: bitset lo fa in un secondo tempo.

Aggiornamento # 2

Ecco una tabella dei tempi di funzionamento per le tecniche che ho provato finora. Lo aggiornerò man mano che avrò altre 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 molto scarsamente applicata. Funziona estremamente lentamente.

Commento: L'algoritmo "Naive ciclo bitget" è implementato come segue:

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

Commento: La versione anello srotolato dell'algoritmo di Scheiner si presenta come segue:

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

Sarei curioso di vedere quanto velocemente 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 

Andando indietro, vedo che questa è la soluzione di 'parallelo' dato sulla pagina bithacks.

Answer 2

MODIFICA: NUOVA SOLUZIONE

Sembra che si desidera ripetere il calcolo per ogni elemento in una matrice 4096 per 4096 di valori UINT32. Se questo è quello 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 a questa:

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 si vuole fare in versioni vectorized di alcuni degli altri algoritmi, credo BITAND è inoltre progettato per operare su matrici.

---

La vecchia soluzione ...

Il modo più semplice che posso pensare è quello di utilizzare la funzione di DEC2BIN, che vi dà la rappresentazione binaria (come una stringa) di un intero non negativo:

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

E 'lento, ma è facile . =)

Answer 3

A meno che non si tratti di un'esercitazione di implementazione di MATLAB, è possibile prendere semplicemente l'implementazione rapida di C++ e compilarla come funzione di messaggistica una volta per piattaforma di destinazione.

Answer 4

Prova a suddividere il lavoro in parti più piccole. La mia ipotesi è che se si desidera elaborare tutti i dati contemporaneamente, Matlab sta tentando di eseguire ogni operazione su tutti gli interi prima di eseguire i passaggi successivi e la cache del processore viene invalidata a ogni passaggio.

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

Answer 5

sto facendo rivivere un vecchio thread qui, ma mi sono imbattuto in questo problema e ho scritto questo po 'di codice per esso:

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

sembra piuttosto concisa, ma ho paura che bitget è implementato nelle operazioni O (n) bitshift. Il codice funziona per quello che sto andando, ma il mio problema non dipende dal 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

Ha effettuato alcuni confronti temporali su Matlab Cody. Determinato uno Scheiner vettorizzato modificato segmentato fornisce prestazioni ottimali.

Avere> 50% di riduzione del tempo in base a 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 

Answer 8

Implementato il "Miglior algoritmo a 32 bit" dal collegamento Stanford in alto. L'algoritmo migliorato ha ridotto i tempi di elaborazione del 6%. Anche ottimizzato la dimensione del segmento e trovato che 32K è stabile e migliora il tempo del 15% su 4K. Aspettatevi che il tempo di 4Kx4K sia il 40% di Algoritmo 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 

Answer 9

Un approccio veloce sta contando i bit in ciascun byte utilizzando una tabella di ricerca, quindi sommando tali valori; in effetti, è 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 vettoriali in MATLAB, quindi è possibile vettorizzare questo approccio e calcolare il peso/numero di bit di un grande numero di stringhe di bit simultaneamente, molto rapidamente. Questo approccio è implementato nell'invio di bitcount su MATLAB File Exchange.