Quickly shifting a matrix

Hi everyone,

Consider a large MxN matrix of randomly placed ones and zeros (call it A). I need to create a matrix (call it B) that shifts the location of the ones in the original matrix to the right depending on the number of preceding ones in the row. For example, consider an arbitrary row:

A(i,:) = [0 1 0 0 0 1 0 0 0 1 1 1 1 0 0 0];

This should become:

B(i,:) = [0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0];

Because the number of ones in each row is random, B will need to have as many columns as necessary to accommodate the row with the most ones. Trailing zeros can be added to the end of any row to equalize the number of columns. Note that consecutive ones stay grouped together.

I have implemented this using a loop (see MWE below). But because M and N are both large, my current code is relatively slow.

    M=10000;
    N=1000;
    out0     = binornd(1,0.3,M,N);
    out_cum0 = zeros(M,N);
    out_cum1 = zeros(M,N);
    for i=2:N
        out_cum0(:,i)=out_cum0(:,i-1)+out0(:,i-1);
        if i>1
            out_cum1( and(out0(:,i-1)==1,out0(:,i)==1 ), i ) = out_cum1( and(out0(:,i-1)==1,out0(:,i)==1 ), i-1 );
            out_cum1(~and(out0(:,i-1)==1,out0(:,i)==1 ), i ) = out_cum0(~and(out0(:,i-1)==1,out0(:,i)==1 ), i );
        end
    end 

    out1       = zeros(M,2*N);
    loc0       = find(out0==1);
    [row,col]  = ind2sub(size(out0),loc0);
    loc1       = sub2ind(size(out1),row,col+out_cum1(loc0));
    out1(loc1) = 1;

I suspect there's a faster way to do this, particularly the loop, but I'm not sure what it is. Any suggestions? Thanks in advance.

Answer 1

[Raunak Gupta]

Hi,

Since the mentioned code contains only a single for loop, I don’t think introducing vectorization with the help of a custom function that is fast at shifting matrix will increase the speed of the code much.

As I can see from the code column of out_cum0 and out_cum1 are updating based on the value of preceding column so vectorization is very difficult to achieve. Even using parfor doesn’t help much because it will need to assign variable to a classification as mentioned here. So that will increase the memory required for the code.