On this topic we could see an interesting discussion about how make the fastest euclidean distance.

But I have see that on Octave, it is not true at all...

a= rand(1000, 800);

b= rand(1000, 800);

%method A:

tic; d = sqrt( sum((a-b) .* (a-b),2)); toc;

%method B

tic; d = sqrt( sum(a.*a + b.*b - 2 *( a .*b),2)); toc;

%method C

tic;

aa=sum(a.*a,1); bb=sum(b.*b,1);

d = abs(aa( ones(size(bb,2),1), :)' + bb( ones(size(aa,2),1), :) - 2*a'*b); toc

A => Elapsed time is 0.02084 seconds.

B => Elapsed time is 0.0335 seconds.

C => Elapsed time is 1.49 seconds.

So on my machine the naive method is the fastest, certainly due the fact that octave do not use SSE library for my part.

Same on my machine! here the results

ReplyDeleteoctave:1> a= rand(1000, 800);

octave:2> b= rand(1000, 800);

octave:3> tic; d = sqrt( sum((a-b) .* (a-b),2)); toc;

Elapsed time is 0.0249498 seconds.

octave:4> tic; d = sqrt( sum(a.*a + b.*b - 2 *( a .*b),2)); toc;

Elapsed time is 0.030062 seconds.

octave:5> tic;aa=sum(a.*a,1); bb=sum(b.*b,1);d = abs(aa( ones(size(bb,2),1), :)' + bb( ones(size(aa,2),1), :) - 2*a'*b); toc

Elapsed time is 0.341904 seconds.