speed up for loops

1 view (last 30 days)
parmida nabi
parmida nabi on 20 Dec 2013
Commented: Image Analyst on 21 Dec 2013
how can I speed up these for loops? it seems to run forever! shrtPth is an array which contains shortest path of two nodes. i.e. this code is a kind of Floyd algorithm for nodes with two indices, such as: E(:,ii,i) & E(:,jj,j).
for m=1:N
for n=1:blk
for i=1:N
for ii=1:blk
for j=1:N
for jj=1:blk
shrtPth(i,ii,j,jj)=min(shrtPth(i,ii,j,jj),shrtPth(i,ii,m,n)+shrtPth(m,n,j,jj));
end
end
end
end
end
end
thanks by advance...

Answers (2)

Matt J
Matt J on 20 Dec 2013
Edited: Matt J on 20 Dec 2013
There doesn't seem to be a good reason to have two indices per node. You can equally well index them with one index and then you will have fewer for-loops, which should be faster.
However, before you reinvent the wheel, you should know that there are many shortest path routines on the File Exchange,
  3 Comments
Matt J
Matt J on 20 Dec 2013
Using SUB2IND, you can convert multi-dimensional indices to one-dimensional linear indices.
parmida nabi
parmida nabi on 21 Dec 2013
do you mean I should use: shrtPth([sub2ind(size(shrtPth),i,ii,j,jj)]) ? and now what about for loops? don't we need them any more?!

Sign in to comment.


Image Analyst
Image Analyst on 20 Dec 2013
Reverse the order of the indexes. You're doing it the exact opposite way you should be doing it. You're doing it the slowest way possible. MATLAB goes down the rows (left most index) before it does the others. Look, try this code:
n=300;
m = rand(n,n,n);
tic;
for i1 = 1 : n
for i2 = 1 : n
for i3 = 1 : n
m(i1,i2,i3) = m(i1,i2,i3)+1;
end
end
end
toc;
tic;
for i3 = 1 : n
for i2 = 1 : n
for i1 = 1 : n
m(i1,i2,i3) = m(i1,i2,i3)+1;
end
end
end
toc;
In the command window, notice almost a 4x speedup:
Elapsed time is 0.911281 seconds.
Elapsed time is 0.246471 seconds.
  2 Comments
parmida nabi
parmida nabi on 21 Dec 2013
Edited: parmida nabi on 21 Dec 2013
your example is about for loops with same size, but mine have different sizes: N & blk. changing the order may be helpful, but not enough in my code. however, I have checked your example and now I know a key point, thanks...
Image Analyst
Image Analyst on 21 Dec 2013
The sizes don't matter. I could have made different sizes and the results would be the same. It was faster to create the code with the same size so that's why I did it. I hope it didn't confuse you. If the total number of iterations on the inner most loop is not more than a million or so, then you might not notice any difference in time.

Sign in to comment.

Categories

Find more on Loops and Conditional Statements in Help Center and File Exchange

Tags

Community Treasure Hunt

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

Start Hunting!