Эффективное вычисление веса Хэмминга в matlab
https://stackoverflow.com/questions/1024904
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Учитывая, что MATLAB uint32 интерпретируется как битовая строка, каков эффективный и краткий способ подсчета количества ненулевых битов в строке?
У меня есть работающий, наивный подход, который перебирает биты, но это слишком медленно для моих нужд.(Реализация на C ++ с использованием std::bitset count() выполняется почти мгновенно).
Я нашел довольно приятную страницу, на которой перечислены различные методы подсчета битов, но я надеюсь, что есть простой способ в стиле MATLAB.
http://graphics.stanford.edu /~seander/bithacks.html#Подсчет битсетей
Обновление № 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 кажется очень плохо реализованной.Он работает чрезвычайно медленно.
Комментарий:Алгоритм "Наивного цикла bitget" реализован следующим образом:
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));
Решение
Мне было бы интересно посмотреть, насколько быстрым будет это решение:
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.
Другие советы
Если это не упражнение по реализации MATLAB, вы можете просто взять свою быструю реализацию на C ++ и скомпилировать ее как mex-функцию один раз для каждой целевой платформы.
Редактировать:НОВОЕ РЕШЕНИЕ
Похоже, что вы хотите повторить вычисление для каждого элемента в массиве 4096 на 4096 значений UINT32.Если это то, что вы делаете, я думаю, что самый быстрый способ сделать это в MATLAB - использовать тот факт, что БИТГЕТ предназначен для работы с матрицами значений.Код будет выглядеть примерно так:
numArray = ...your 4096-by-4096 matrix of uint32 values...
w = zeros(4096,4096,'uint32');
for iBit = 1:32,
w = w+bitget(numArray,iBit);
end
Если вы хотите создать векторизованные версии некоторых других алгоритмов, я полагаю БИТАНД также предназначен для работы с матрицами.
Старое решение...
Самый простой способ, который я могу придумать, - это использовать ДЕКАБРЬ 2BIN функция, которая дает вам двоичное представление (в виде строки) неотрицательного целого числа:
w = sum(dec2bin(num) == '1'); % Sums up the ones in the string
Это медленно, но это легко.=)
Реализован "Лучший 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
Провел несколько временных сравнений в 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
Быстрый подход заключается в подсчете битов в каждом байте с использованием таблицы подстановки, затем суммировании этих значений;действительно, это один из подходов, предложенных на веб-странице, приведенной в вопросе.Приятная особенность этого подхода заключается в том, что и поиск, и сумма являются векторизуемыми операциями в MATLAB, поэтому вы можете векторизовать этот подход и очень быстро вычислить вес Хэмминга / количество установленных битов большого количества битовых строк одновременно.Этот подход реализован в количество битов отправка на файлообменник MATLAB.
Попробуйте разделить задание на более мелкие части.Я предполагаю, что если вы хотите обработать все данные сразу, matlab пытается выполнить каждую операцию со всеми целыми числами перед выполнением последовательных шагов, и кэш процессора становится недействительным с каждым шагом.
for i=1:4096,
«process bits(i,:)»
end
Я восстанавливаю здесь старую тему, но я столкнулся с этой проблемой и написал для нее этот небольшой фрагмент кода:
distance = sum(bitget(bits, 1:32));
Выглядит довольно лаконично, но я боюсь, что bitget реализован в O(n) bitshift операции.Код работает для того, что я собираюсь сделать, но мой набор задач не зависит от веса Хэмминга.
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
