Re: Yet Another Vectorization Quiz

[Judd Storrs]

On Tue, Dec 14, 2010 at 5:12 PM, Carlo de Falco <address@hidden> wrote:
> Hi all,
>
> I need to shift all the zeros in a (possibly very large) matrix
> to the end of each column without changing the ordering of the
> remaing elements, e.g.:
>
> a = [ 1 2 4 0         [ 1 2 4 6
>      2 3 5 6    ==>    2 3 5 7
>      3 0 0 7           3 4 6 0
>      0 4 6 0]          0 0 0 0]
>
> with a for loop this can be done as
>
> for j = 1:columns (a)
>  v = zeros (rows (a), 1);
>  v(1:nnz (a(:, j))) = a(a(:, j) != 0, j);
>  a(:, j) = v;
> endfor
>
> I personally see no obvious way to improve this,
> does anyone have any idea?

idx = find(a) ;
idx2 = (0:numel(idx)-1)' + ceil(idx/size(a,1)) ;
b = zeros(size(a)) ;
b(idx2) = a(idx) ;

But, I'm not sure this is so hot for a large a. In that case you could
maybe save some memory by processing a smaller set of columns at a
time. Maybe something like (not tested)

function b = sortzeros(a)
   idx = find(a) ;
   idx2 = (0:numel(idx)-1)' + ceil(idx/size(a,1)) ;
   b = zeros(size(a)) ;
   b(idx2) = a(idx) ;
endfunction

n = size(a,2) ;
m = 8 ;   # process in chunks of 8 columns at a time
for i=1:m:n
   j = min(i+m-1,n) ;
   a(:,i:j) = sortzeros(a(:,i:j)) ;
endfor


--judd