# Speed up nested loops

9 views (last 30 days)
this code to calculate the shortest distance between lines and the distance between the mid point of the line and the the point of minimum distance vector between them then compare it with 0, if it is less than zero it will beark the second loop and change the orientation of the new line and check it with ALL previous lines. I tried 2000 lines with 100 trails the PC takes more than 48 hrs.
n=2000;
maxtrial=100;
Rx=rand(n,1)*0.2;
Ry=rand(n,1)*0.2;
Rz=rand(n,1)*0.2;
MT=0;
k=1;
while k<=n
% Create the angels for fiber oreintation
%For Phi
Phi_min=-0.1745329; %Angle Phi minimum value
Phi_max=0.1745329; %Angle Phi maximum value
Phi=Phi_min+rand(1,1)*(Phi_max-Phi_min);
%For theta
Z = (-1) + (1-(-1)) * rand(1,1); % value of Z to use in angle theta which will be within +- 10 degree
theta = acos (Z);
d1= sin(theta)*sin(Phi);
d2= sin(theta)*cos(Phi);
d3=cos(theta);
%first point coordinats
x2= Rx(k)+(Lf*0.5*d1);
y2= Ry(k)+(Lf*0.5*d2);
z2= Rz(k)+(Lf*0.5*d3);
%second point coordinats
x3= Rx(k)-(Lf*0.5*d1);
y3= Ry(k)-(Lf*0.5*d2);
z3= Rz(k)-(Lf*0.5*d3);
P=[x3-x2 y3-y2 z3-z2]; %orientation vector
P_all(k,:)=P;
if k>=2 && k<=n
t=k-1;
for t=1:k-1
normal_vector=((cross(P_all(k-t,:),P_all(k,:))/(norm(cross(P_all(k-t,:),P_all(k,:)))))); % unit vector normal to both lines
min_distance= norm(dot((R_all(k-t,:)-R_all(k,:)),normal_vector))-Df; % the minimum distance between two lines
L_ij=(-(dot((R_all(k-t,:)-R_all(k,:)),P_all(k-t,:)))+(dot((R_all(k-t,:)-R_all(k,:)),P_all(k,:)))*dot(P_all(k-t,:),P_all(k,:)))/(1-(dot(P_all(k-t,:),P_all(k,:)))^2); % distance between the center of line and the point that minimum distance occure at
if min_distance<0 && L_ij<=Lf/2
k=k-1;
MT=MT+1;
break
else
MT=0;
end
end
end
if MT==maxtrial
x2=0;
x3=0;
y2=0;
y3=0;
z2=0;
z3=0;
break
end
G1(k,:)= [z2 x2 y2]; %first points coordinates matrix
G2(k,:)= [z3 x3 y3]; %second points coordinates matrix
k=k+1;
end
Jan on 23 Nov 2019
You see warnings in the editor already, which explain the disadvantages of iteratively growing arrays. Use a proper pre-allocation in any way.
A simple code will not run faster, but it is easier to read: Compare
Z = (-1) + (1-(-1)) * rand(1,1)
with
Z = 2 * rand - 1;
I cannot run your code, because Lf, Df and R_all are undefined. It looks strange, that MT is not reset and comparing MT==maxtrial can match 1 time only.

Jan on 23 Nov 2019
Edited: Jan on 23 Nov 2019
This line is expensive:
normal_vector = ((cross(P_all(k-t,:),P_all(k,:)) / ...
(norm(cross(P_all(k-t,:),P_all(k,:))))));
Matlab's cross() is not efficient and norm() can be accelerated also. Calling cross() twice for the same data is a waste of time in addition. P_all(k, :) is available as P also. Faster and nicer:
v = cross(P_all(k-t, :), P);
normal_vector = v / norm(v);
Or use a faster M-function:
normal_vector = NormCross(P_all(k-t, :), P);
function c = NormCross(a, b)
c = [a(2) * b(3) - a(3) * b(2), ...
a(3) * b(1) - a(1) * b(3), ...
a(1) * b(2) - a(2) * b(1)];
c = c / sqrt(c(1) * c(1) + c(2) * c(2) + c(3) * c(3));
end
Equivalent improvements can be applied to the DOT commands also.
By the way: The 2 leading and trailing parentheses in "normal_vector = ((" decrease the readability of the code only.
A short run time test:
P = rand(100, 3);
t = 100;
tic
for r = 1:1e5
for k = 1:100
v = cross(P(k, : ), P(t, :)) / norm(cross(P(k, :), P(t, :)));
end
end
toc
tic
for r = 1:1e5
Pt = P(t, :);
for k = 1:100
v = NormCross(P(k, : ), Pt);
end
end
toc
% Elapsed time is 11.122618 seconds.
% Elapsed time is 2.686646 seconds.
4 times faster just by avoiding calling cross twice and norm.
Instead of comparing min_distance=norm(...), you can compare the squared distance to save the computational time for the square root:
v = rand(1, 3);
min_distance = norm(v) - Df;
if min_distance < 0
...
end
Df2 = Df ^ 2;
...
v = rand(1, 3);
min_dist2 = v * v' - Df2; % Faster than: sum(v .* v)
if min_dist2 < 0
...
end
Abdulmajeed Altassan on 15 Dec 2019
Dear Jan;
Thank you for your answers, it was jamming with me when I set n=2000 and maxtrial=5 it tooks 48 hr and it dose not finished.
I will follow you idea thank you very much