Скажем, у меня есть массив
k = [1 2 0 0 5 4 0]
Я могу вычислить маску следующим образом
m = k > 0 = [1 1 0 0 1 1 0]
Использование только маски m и следующих операций
- Сдвиг влево/вправо
- И/или
- Добавление/Вычитание/Умножение
Я могу записать k в следующее
[1 2 5 4]
Вот как я это делаю (псевдокод MATLAB):
function out = compact( in )
d = in
for i = 1:size(in, 2) %do (# of items in in) passes
m = d > 0
%shift left, pad w/ 0 on right
ml = [m(2:end) 0] % shift
dl = [d(2:end) 0] % shift
%if the data originally has a gap, fill it in w/ the
%left shifted one
use = (m == 0) & (ml == 1) %2 comparison
d = use .* dl + ~use .* d
%zero out elements that have been moved to the left
use_r = [0 use(1:end-1)]
d = d .* ~use_r
end
out = d(1 : size(find(in > 0), 2)) %truncate the end
end
Интуиция
На каждой итерации мы сдвигаем маску влево и сравниваем маску. Мы устанавливаем индекс, чтобы иметь сдвинутые слева данные, если мы обнаружим, что после этого сдвига теперь был введен индекс, который был первоначально недействительным (mask [i] = 0) (mask [i] = 1).
Вопрос
Вышеупомянутый алгоритм имеет O (N * (3 сдвига + 2 сравнения + AND + add + 3 умножает)). Есть ли способ повысить его эффективность?