Эффективный расчет веса Хэмминга в Matlab

Question

Учитывая, что MATLAB uint32 должен интерпретироваться как битовая строка, каков эффективный и краткий способ подсчета количества ненулевых битов в строке?

У меня есть рабочий, наивный подход, который повторяется, но это слишком медленно для моих нужд. (Реализация C ++ с использованием std :: bitset count () выполняется почти мгновенно).

Я нашел довольно симпатичную страницу со списком различных методов подсчета битов, но я надеюсь, что есть простой способ MATLAB-esque.

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

Обновление № 1

Только что реализовал алгоритм Брайана Кернигана следующим образом:

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

Производительность по-прежнему дурная, более 10 секунд, чтобы вычислить всего 4096 ^ 2 весовых расчетов. Мой код C ++, использующий count () из std :: bitset, делает это за секунду.

Обновление № 2

Вот таблица времени выполнения техник, которые я уже пробовал. Я буду обновлять его по мере поступления дополнительных идей / предложений.

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

Комментарий : Функция dec2bin () в MATLAB выглядит очень плохо реализованной. Работает очень медленно.

Комментарий : Алгоритм "Наивный цикл битов" реализован следующим образом:

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

Комментарий : Развернутая в цикле версия алгоритма Шайнера выглядит следующим образом:

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

Мне было бы интересно посмотреть, насколько быстро это решение:

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

Возвращаясь, я вижу, что это «параллельное» решение, приведенное на странице битхэков.

Answer 2

Реализован «Лучший 32-битный алгоритм» из ссылки Стенфорда вверху. Улучшенный алгоритм сократил время обработки на 6%. Также оптимизирован размер сегмента и установлено, что 32K стабильно и улучшает время на 15% по сравнению с 4K. Ожидайте, что время 4Kx4K будет составлять 40% от векторизованного алгоритма Шайнера.

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 3

Если это не упражнение по реализации MATLAB, вы можете просто взять вашу быструю реализацию на C ++ и скомпилировать ее как mex-функцию, один раз для целевой платформы.

Answer 4

РЕДАКТИРОВАТЬ: НОВОЕ РЕШЕНИЕ

Похоже, что вы хотите повторить вычисления для каждого элемента в массиве значений UINT32 размером 4096 на 4096. Если это то, что вы делаете, я думаю, что самый быстрый способ сделать это в MATLAB - это использовать тот факт, что BITGET предназначен для работы с матрицами значений. Код будет выглядеть так:

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

Если вы хотите создавать векторизованные версии некоторых других алгоритмов, я считаю, что BITAND также предназначен для работы с матрицами.

---

Старое решение ...

Самым простым способом, который я могу придумать, является использование функции DEC2BIN , которая дает двоичное представление (в виде строки) неотрицательного целого числа:

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

Это медленно, но легко. =)

Answer 5

Быстрый подход заключается в подсчете битов в каждом байте с использованием таблицы поиска, а затем суммировании этих значений; действительно, это один из подходов, предложенных на веб-странице, приведенной в вопросе. Хорошая особенность этого подхода заключается в том, что поиск и суммирование являются векторизуемыми операциями в MATLAB, поэтому вы можете векторизовать этот подход и очень быстро вычислить вес Хемминга / количество установленных битов большого числа битовых строк одновременно. Этот подход реализован в представлении bitcount на файловом обмене MATLAB.

Answer 6

Сделал некоторые временные сравнения на Matlab Cody. Определяемый сегментированный модифицированный векторизованный шайнер дает оптимальную производительность.

Сокращение времени> 50% на основе изменения Коди от 1,30 с до 0,60 с для вектора 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 7

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 8

Я возрождаю здесь старую ветку, но натолкнулся на эту проблему и написал для нее небольшой кусочек кода:

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

Выглядит довольно лаконично, но я боюсь, что bitget реализовано в O (n) bitshift операциях. Код работает для того, что я собираюсь, но мой набор задач не зависит от веса Хэмминга.

Answer 9

Попробуйте разбить работу на более мелкие части. Я предполагаю, что если вы хотите обработать все данные одновременно, Matlab пытается выполнить каждую операцию со всеми целыми числами, прежде чем предпринимать последовательные шаги, и кэш процессора аннулируется с каждым шагом.

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