Эффективное вычисление веса Хэмминга в matlab

Ответ 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

Возвращаясь назад, я вижу, что это "параллельное" решение, данное на странице bithacks.

Ответ 2

EDIT: NEW SOLUTION

Кажется, что вы хотите повторить вычисление для каждого элемента массива 4096 на 4096 значений UINT32. Если это то, что вы делаете, я думаю, что самый быстрый способ сделать это в 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

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

Ответ 3

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

Ответ 4

Реализован "Лучший 32-битный алгоритм" из ссылки "Стэнфорд" наверху. Улучшенный алгоритм сократил время обработки на 6%. Также оптимизирован размер сегмента и установлено, что 32K стабильно и улучшает время на 15% за 4K. Ожидайте, что время 4Kx4K будет составлять 40% векторизованного алгоритма 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

Ответ 5

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

У > 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

Ответ 6

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

Ответ 7

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

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

Ответ 8

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

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

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

Ответ 9

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