About running time in matrix.

Hi, I am running a small program, that first sortrows of a matrix by the some column and then compare the order with another column, if there is a flip order, then delete that row, if not continue.

The code is below:

-------------
%M of size[3^N,N+2]. M has a very large size.
M=sortrows(M,N+1); %finish sorting

i=2; %no need to start from first one, obvious.
j=0;
stop=M(3^N,N+1);
while M(i,N+1)<stop % loop has not finish till last row
    if M(i,N+2)>=M(i+1,N+2)% M(i,N+2) is the maximum number so far
        M(i+1,:)=[]; %delete i+1 row
        j=j+1;
    else
        i=i+1;
    end
end

------------- The program runs ok, and I tried some tests, however when N is 12 or 13, the program can run more than 3 hours. I wonder why is so? sortrows takes no more than 1 minute, why compare procedure(3^N steps) takes so much time? Is delete a row is time-consuming or something else?

Thanks!

Answer 1

[Sean de Wolski]

The problem is that you are resizing the matrix each time the if criteria is met. This requires a memory copy and is very slow for large matrices.

Instead, use a for-loop and build up a vector of rows to remove. Then remove them all at the same time. Simple example:

N = 20;
idx = false(N,1);
M = magic(N);
for ii = 1:N
  if max(M(ii,:))>min(M(ii,:))*N/2
      idx(ii) = true; %This row will be removed.
  end
end
M(idx,:) = []; %remove all of the rows here!

[C Zeng]

Sean, you are right! Thanks so much! yes, removing these together at the very last end is efficient!

Also, is sortrows be more efficient? I am thinking does Matlab provide divide-and-conquer method to approach that? Here when N is 12 or 13, sortrows to a [3^N,N+2] matrix is a little slow, more than 10 seconds.

I want to be perfect here, thanks!