About running time in matrix.

2 views (last 30 days)
C Zeng
C Zeng on 4 Jan 2013
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!

Accepted Answer

Sean de Wolski
Sean de Wolski on 4 Jan 2013
Edited: Sean de Wolski on 4 Jan 2013
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!
  1 Comment
C Zeng
C Zeng on 4 Jan 2013
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!

Sign in to comment.

More Answers (0)

Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!