About running time in matrix.

2 次查看(过去 30 天)
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!

采纳的回答

Sean de Wolski
Sean de Wolski 2013-1-4
编辑:Sean de Wolski 2013-1-4
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 个评论
C Zeng
C Zeng 2013-1-4
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!

请先登录,再进行评论。

更多回答(0 个)

类别

Help CenterFile Exchange 中查找有关 Logical 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by