About running time in matrix.

1 vue (au cours des 30 derniers jours)
C Zeng
C Zeng le 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!

Réponse acceptée

Sean de Wolski
Sean de Wolski le 4 Jan 2013
Modifié(e) : Sean de Wolski le 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 commentaire
C Zeng
C Zeng le 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!

Connectez-vous pour commenter.

Plus de réponses (0)

Catégories

En savoir plus sur Logical dans Help Center et File Exchange

Tags

Community Treasure Hunt

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

Start Hunting!

Translated by