Nested Loops issue

2011 7 18
2 个回答
2 次查看（30 天）

0 个投票

Hi, Please bear with me, as I am still learning with Matlab. I have a problem with efficiency of a nested loop in my Matlab code (I have copied and pasted this below).
for ii=1:nn
for jr1=1:length(PP.AII)
sr1=(d(PP.AII{jr1})'*AA{ii}(PP.AII{jr1},PP.AII{jr1})*d(PP.AII{jr1}));
dr1=dr1+sr1;
end
end
When the number of elements of PP.AII increases, this loop becomes extremely slow. Ideally, I would like to write something like:
for ii=1:nn
sr1=(d(PP.AII)'.*AA{ii}(PP.AII,PP.AII).*d(PP.AII));
sr1=sum(sr1);
end
However, Matlab will not allow this due to the fact that PP.AII consists of cell elements (for example, [90x1 double] [100x1 double] [90x1 double] [100x1 double]). I can find a way around this using the cell2mat and num2cell commands, however I feel that this is still inefficient due to introducing another nested loop, which seems to defeat the object.
Is there a way in which I can employ the dot command in order to speed up the above process? Failing this, does anyone have any other suggestions on how to speed up this area of code?
Any help is appreciated.

1 个评论
显示 -1更早的评论 隐藏 -1更早的评论

Oleg Komarov
Oleg Komarov 2011-7-18
How big is d (m by n size) and how big is PP (in terms of megabytes)? What system do you use (32/64 bit)?

请先登录，再进行评论。

请先登录，再回答此问题。

回答（2 个）

Jan
Jan 2011-7-18

2 个投票

At first I'd omit all repeated calculations output the loop(s) and use temporary variables:
PP_AII = PP.AII;
n = length(PP_AII);
for ii = 1:nn
AAii = AA{ii};
for jr1 = 1:n
t1 = PP_AAI{jr1};
t2 = d(t1);
dr1 = dr1 + (t2' * AAii(t1, t1) * t2);
% [EDITED] If t2 is a column vector, this is much faster:
% dr1 = dr1 + (t2' * t2) * AAii(t1, t1);
end
end
Please compare the speed with your original approach and the CELL2MAT method.
CELL2MAT is not efficient for larger cells (thousands of elements), because it seems to let the output grow dynamically instead of a clean pre-allocation. You can use FEX: Cell2Vec, but some reshaping / permutating might be necessary to create the wanted output.

6 个评论
显示 4更早的评论 隐藏 4更早的评论

James
James 2011-7-18
Hi,
Thanks for the reply. I have tried this, however I do not really notice any increase in speed - maybe about 0.02 seconds on the overall runtime of the program.
James
James 2011-7-18
Hi,
Thank you (again) for your reply. I find that the above does speed up the code. The standard runtime for nn equal to 200 was about 11.9 seconds, now it is 10.6 seconds. I will have a look at different elements of my code to see if I can implement the above throughout.
Jan
Jan 2011-7-18
@James: I hoped that the speedup is higher than 10%. But 10 seconds seems to be surprisingly slow for this piece of code. What is "d()" and how large is n? Is it possible that the main time is spend in the function(?) d()? Please use the PROFILEr or TIC/TOC to find the real bottlenecks of the program.
If I assume that t2 is a [N x 1] vector, the processing is much faster if you reorder the elements:
dr1 = dr1 + (t2' * AAii(t1, t1) * t2);
==>
dr1 = dr1 + (t2' * t2) * AAii(t1, t1);
In the later case MATLAB uses an efficient BLAS method and the external multiplication is much cheaper.
James
James 2011-7-18
Hi,
Apologies for the confusion. This was just a snippet of code that I have taken from a larger code - the reason that I only asked about this was because there are a few places where this type of computation appears. In general, this loop (in the profiler) seems to be taking about 1 seconds, whereas before it was taking about 2.4 seconds - therefore there is actually a fair bit of speedup.
In general, n would be about 4 or 8, whereas nn would be somewhere between 200 and 800. The above times were taken for n=4, nn=200.
James
James 2011-7-18
Thanks for the extra reply. However, the 'improved' output does not correspond to the same dimensions as the original. (t2' * AAii(t1, t1) * t2) is just a scalar, however (t2' * t2) * AAii(t1, t1) will not be a scalar (in fact, the matrix dimensions do not actually agree).
Jan
Jan 2011-7-18
This is the fact, if t1 is not a scalar, in opposite to my wrong assumptions.

请先登录，再进行评论。

Andrei Bobrov
Andrei Bobrov 2011-7-18

0 个投票

variant 1
c = PP.AII;
sr1 = sum(cell2mat(cellfun(@(x)sum(cell2mat(arrayfun(@(i1)d(c{i1})'*x(c{i1},c{i1})*d(c{i1}),1:length(c),'un',0))),AA,'un',0)));
variant 2
nn = length(AA);
mm = length(PP.AII);
sr = zeros(nn,mm);
for ii=1:nn
sr(ii,:) =arrayfun(@(i1)d(PP.AII{i1})'*AA{ii}(PP.AII{i1},PP.AII{i1})*d(PP.AII{i1}),1:mm);
end
sr1 = sum(sr(:));

7 个评论
显示 5更早的评论 隐藏 5更早的评论

James
James 2011-7-18
Hi,
Thanks for the reply. However, if I try to include this in my matlab code, the runtime is actually increased (and pretty substantially as well). In general, nn is normall a value of between 200 and 800.
James
James 2011-7-18
Update: Sorry, however I somehow managed to place the new line of code inside the 'nn' loop, which explains why it was taking so long. I have now got it out of this loop, however the code does not seem to work correctly with the above line?!?
James
James 2011-7-18
Hi,
Thanks (again) for the reply. However, I am unsure that the above is equivalent to the original, as when I try to include the above in my code I find that it will not work?!?
Jan
Jan 2011-7-18
@James: Please describe "it will not work" with any details. Solving problems is dramatically more efficient, if the problems are known already.
James
James 2011-7-18
Hi,
When I stated that 'it will not work', what I meant was that when I tried to input the lines into my code, I found that when I tried to run the code I was obtaining an incorrect output. This is why I suggested that maybe the above lines are not quite equivalent to the original lines?
Jan
Jan 2011-7-18
@Andrei: Your method evaluates "d(PP.AII{i1})" twice and "PP.AII{i1}" 4 times. Using a temp variable would be more efficient.
Andrei Bobrov
Andrei Bobrov 2011-7-19
Dear Jan! I completely agree with your approach.

请先登录，再进行评论。

类别

在 帮助中心 和 File Exchange 中查找有关 Loops and Conditional Statements 的更多信息

标签

提问:

James
James
2011-7-18

Community Treasure Hunt

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

Start Hunting!

Translated by