Quickly shifting a matrix
1 view (last 30 days)
Show older comments
Tristan Potter on 2 Dec 2019
Answered: Raunak Gupta on 6 Dec 2019
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.
out0 = binornd(1,0.3,M,N);
out_cum0 = zeros(M,N);
out_cum1 = zeros(M,N);
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 );
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.
Raunak Gupta on 6 Dec 2019
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.
Find more on Loops and Conditional Statements in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!Start Hunting!