Optimizing Euclidian distance code

Question

Stephan van Kalmthout 2020-4-15

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/518055-optimizing-euclidian-distance-code

评论： Ameer Hamza 2020-4-16

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!

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

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

Answer 1

Ameer Hamza 2020-4-15

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/518055-optimizing-euclidian-distance-code#answer_426190

编辑：Ameer Hamza 2020-4-15

在 MATLAB Online 中打开

Try this

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

2 个评论
显示无隐藏无

Stephan van Kalmthout 2020-4-16

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 2020-4-16

在 MATLAB Online 中打开

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