Optimizing Euclidian distance code

Dear all,

I am trying to optimize my code for calulating the minimum distance to the origin, given a set of 3D points specified by column vectors x, y and z. I use profile to obtain the computing time.

x = [25; 40; 63];
y = [12; 34; 56];
z = [30; 55; 77];

profile on
d = minDistance(x,y,z);
profile viewer
function d = minDistance(x,y,z)
% Given a set of 3D points specified by column vectors x,y,z, this
% function computes the minimum distance to the origin
% preallocate
d = zeros(length(x),1);
% compute distance for every point
for k = 1:length(x)
d(k) = sqrt(x(k)^2 + y(k)^2 + z(k)^2);
end
% get minimum distance
d = min(d)
end

I'm aware of the fact that the biggest time consumer is the for-loop, but I don't know how to optimize such a loop.

Anyone who can explain how such an optimization is done?

Thanks on beforehand!

Answer 1

[Ameer Hamza]

Try this

function d = minDistance(x,y,z)
    d = min(vecnorm([x y z], 2, 2));
end

[Stephan van Kalmthout]

Ameer Hamza,

Thank you for your answer, but I ran the code and the total computing time increased from 0.005 to 0.033.

Your code is indeed more compact, but takes more time to compute

[Ameer Hamza]

Yes, you are correct. I tried a bit, and vecnorm() seems to be consuming a lot of time because it is a quite general function and its internal implementation takes some time to decide which vector norm to take and along which dimension. Also, my code spends some time to concatenate [x y z], although I think it does not make a copy of these vectors (because MATLAB use copy on write), It will still take some time to concatenate them.

Note that you can improve the performance of your current code by not using sqrt() at each iteration. Instead, just take sqrt() at the end.

function d = minDistance2(x,y,z)
    % Given a set of 3D points specified by column vectors x,y,z, this
    % function computes the minimum distance to the origin
    % preallocate
    d = zeros(length(x),1);
    % compute distance for every point
    for k = 1:length(x)
    d(k) = x(k)^2 + y(k)^2 + z(k)^2;
    end
    % get minimum distance
    d = sqrt(min(d));
end

I tried a bit further and found that the following code can give you comparable performance while being concise. Note that it requires that you pass it a matrix X instead of 3 vectors.

function d = minDistance(X)
    d = sqrt(min(sum(X.^2,2)));
end

The following code shows that both codes almost have comparable performance. Note that I used input vectors of size 10000x1.

x = rand(1000000,1);
y = rand(1000000,1);
z = rand(1000000,1);

X = [x y z];

t1 = timeit(@() minDistance(X))
t2 = timeit(@() minDistance2(x,y,z))

function d = minDistance(X)
    d = sqrt(min(sum(X.^2,2)));
end

function d = minDistance2(x,y,z)
% Given a set of 3D points specified by column vectors x,y,z, this
% function computes the minimum distance to the origin
% preallocate
d = zeros(length(x),1);
% compute distance for every point
for k = 1:length(x)
d(k) = x(k)^2 + y(k)^2 + z(k)^2;
end
% get minimum distance
d = sqrt(min(d));
end

Result

t1 =
    0.0045
t2 =
    0.0041