2 Loops of same size, 1 goes very quick but one is very slow.

1 次查看（过去 30 天）

显示更早的评论

Kernel7364 2019-5-2

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/459830-2-loops-of-same-size-1-goes-very-quick-but-one-is-very-slow

评论： Kernel7364 2019-5-8

采纳的回答： Guillaume

在 MATLAB Online 中打开

Hello,

I have 2 loops with 4 index each. Every loop is of this form

X1 =zeros (10,11);
s= zeros(1,10^2*11^2);
for i = 1:10
for j = 1:10
for k = 1:11
for l = 1:11
    
counter = counter + 1
s(counter) = 2;
X1(i,k) = X1(i,k) - 1;
X1(j,l) = X1(j,l) - 1;
X = reshape(X1',1,[]);
T1 = {s,X} ;                 
V1 = horzcat(T1{:}) ;        
A(counter,:) = V1(:);
X1 =zeros(10,11);
s= zeros(1,10^2*11^2);
end
end
end
end

The first loop does what it should do very quickly. And the second one is exactly of the same form but this runs very slowly.

I watch the variable "counter" to see how fast it runs and the first loop is finished after a few seconds, but the second one needs already 2 minutes for the first 500 cycles.

Why is it so slow and what can I do to make it faster ?

Best regards !

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

Kernel7364 2019-5-2

在 MATLAB Online 中打开

I want to create a binary linear optimization problem and this will be the matrix for the constraints Ay

. So y is a vector and I have constraints to s and x and thats why I want to create this matrix.

Thank you very much for the advice with V1.

But your second advice is not what I want. It has to be -2 if i=j=k=l and thats why I have done it this way. My other loop is of the same form, but just with other values for x1(i,j) and s. It looks like this:

X1 =zeros (10,11);
s= zeros(1,10^2*11^2);
for i = 1:10
for j = 1:10
for k = 1:11
for l = 1:11
    
counter = counter + 1
s(counter) = -1;
X1(i,k) = X1(i,k) + 1;
X1(j,l) = X1(j,l) + 1;
X = reshape(X1',1,[]);                
V1 = [s,X] ;        
A(counter,:) = V1(:);
X1 =zeros(10,11);
s= zeros(1,10^2*11^2);
end
end
end
end

I am just a beginner with Matlab, so please excuse me if I have very easy and big mistakes. I know that there are many zeros. But in the first loop which I postet first it takes Matlab just a few seconds. And I dont understand why the second one takes so long. I even did this :

clearvars i j k l s X1 T1 V1

to make it faster but that didnt work too.

Thank you very much for your quick answer !

Guillaume 2019-5-2

在 MATLAB Online 中打开

Are you sure that counter is set to 0 before you start any of these loops? If not, you'll be growing s slowly in the loops to sizes far greater than 12100. I note that there are no

counter = 0;

in any of the code you've posted.

But your second advice is not what I want

The whole thing can be constructed without any loop whatsoever, so please explain exactly what your constraints are. In particular, at the moment your inner loops iterate over columns and the outer loops iterate over rows, which is less efficient than iterating over the rows in the inner loops. So is the order of iteration critical?

Kernel7364 2019-5-2

Sorry for my mistake, i set the counter = 0 in front of the loop, but I forgot it to copy in the code to my question.

I want to minimize

where

I have a transformation :

All in all I have to minimize my vector

, since I have constraints to s and x.

Then i have the following constraints:

The first loop that I postet in my question is to fulfil the first to constraints to

The second loop is to fulfil the last inequality.

Furthermore I have a constraint to my

. But these one is at the end of my matrix A and it is very easy and fast to generate. This are just 10 more rows in my matrix A.

I had no other idea to make the matrix A since the constraints should hold to every

and I have 10*10*11*11 of these variables

and I have 3 constraints to it.

Do you have an idea to create the matrix A faster.

I am very glad that you try to help me. Thank you very much !!!

请先登录，再进行评论。

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

采纳的回答

Guillaume 2019-5-2

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/459830-2-loops-of-same-size-1-goes-very-quick-but-one-is-very-slow#answer_373288

编辑：Guillaume 2019-5-2

在 MATLAB Online 中打开

Here is a simple way to create your A (the one with +1 and +2)

[v1, v2] = ndgrid(num2cell(eye(110), 2));  %110 is 10*11
vsum = cellfun(@plus, v1, v2, 'UniformOutput', false);
vsum = cell2mat(vsum(:));
Apos = [2*eye(size(vsum, 1)), vsum];

Your A with -1 and -2 is simply:

Aneg = [2*eye(size(vsum, 1)), -vsum];

Note that the order of the rows is going to be different from what your loops generate but I assume it doesn't matter.

13 个评论
显示 11更早的评论隐藏 11更早的评论

Guillaume 2019-5-5

编辑：Guillaume 2019-5-5

在 MATLAB Online 中打开

Ok, I completely missed that the two inner loops were both iterating over the same coordinate. There's probably a way to generate the result in that order with my original algorithm with some reshape and permute but I can't be bothered to figure it out. So new tack:

numrows = 3;  %your maximum k and l
numcols = 2;  %your maximum i and j
destcoords = repelem({1:numrows, 1:numcols}, 2); %ranges of k, l, i, j
[destcoords{:}] = ndgrid(destcoords{:});         %cartesian product of ranges in the exact order you want
destcol1 = sub2ind([numrows, numcols], destcoords{1}, destcoords{3});  %convert coordinates into linear indices. This is going to be the destination column in A
destcol2 = sub2ind([numrows, numcols], destcoords{2}, destcoords{4});
destrow = repmat(1:numel(destcol1), 1, 2).';   %destination row in A
Aneg = accumarray([destrow, [destcol1(:); destcol2(:)]], -1);
Apos = accumarray([destrow, [destcol1(:); destcol2(:)]], 1);

S can be constructed the same as before, with eye.

Guillaume 2019-5-7

在 MATLAB Online 中打开

The Cplex solver needed a long time and if I do it for a bigger one it did not solve it after 2 hours

I'm afraid this is not something I can help with. It's completely outside my domain of expertise, I don't even know what CPlex is. However, I wouldn't be surprised if it took a long time to find a solution to whatever it is you're trying to solve. You have 12100 unknown!

The class Cplex has no Constant property or Static method named 'solve'.

Sounds like solve is a normal method of the class, not a static method. If so, you need to call it on an instance of the class, not on the class itself. Something like:

myobj = CPlex(???);  %construct an instance of the CPlex class. Replace the ??? by the required inputs if any.
myobj.solve;   %call solve on the instance.

Kernel7364 2019-5-8

Okay, thank you very much for all your help !

I will try it tomorrow and see if I can do something. I hop that Cplex can solve it a bit faster but I can imagine that it will take quiet a while since there are more than 12000 unknown.

Thank you so much for all your help !

请先登录，再进行评论。