[Scilab-users] {EXT} need a more efficient and faster code: suggestions welcome

[Heinz]

Nearest neighbour search of n points requires n.(n+1)/2 comparisons,
therefore execution times proportional to n^2.
Heinz

Same as number of matches between n soccer teams........

-----Original Message-----
From: users [mailto:users-bounces at lists.scilab.org] On Behalf Of Rafael
Guerra
Sent: 03 February 2018 12:42
To: users at lists.scilab.org
Subject: Re: [Scilab-users] {EXT} need a more efficient and faster code:
suggestions welcome

Hello,

Heinz's interesting problem allows testing the Scilab limits and to learn
more about Scilab code optimization for very large datasets.
In the figure here below the execution times are plotted for the efficient
single loop code provided by Wozai and the modified vectorized code provided
further below.
<http://mailinglists.scilab.org/file/t495698/NN_problem_loop_and_vectorized.
png> 

The execution times seem to increase with N^2 or worse... which does not
look very good. Maybe faster algorithms exist but lower level languages seem
definitely required for very large number of points. Thanks Stephane for the
example in C.

Scilab 6.0.0 complains about arrays with more than 2147483647 elements and
memory allocation problems are observed in Win7 32GB laptop when doing
computations with smaller matrices, far from that limit. A dummy example:
--> n=4e4; A = ones(n,1)*ones(1,n) + ones(n,1)*ones(1,n);
    Can not allocate 12800.00 MB memory.
However, >21GB of RAM are available.
Are these matrix size constraints going to be lifted in future Scilab 6
releases?


// START OF CODE (Scilab 6)
clear;
n= 30000;
r=23;
radius = r*grand(n,1,'def').^(1/3);
phi = 2*%pi*grand(n,1,'def');
costheta = 1 - 2*grand(n,1,'def');
radsintheta = radius.*sin(acos(costheta)); X = [radsintheta.*cos(phi),
radsintheta.*sin(phi), radius.*costheta]; Xs = sum(X.*X,'c'); XX =
Xs.*.ones(n,1)' + ones(n,1).*.Xs';  // faster than using transpose XX = XX -
2*X*X';
XX(1:n+1:$) = %nan;  // remove diagonal 0's
MinDist1 = min(XX,'r').^0.5;   //min taken along rows is faster
clear  Xs  XX;
//END OF CODE

Thanks and regards,
Rafael




--
Sent from:
http://mailinglists.scilab.org/Scilab-users-Mailing-Lists-Archives-f2602246.
html
_______________________________________________
users mailing list
users at lists.scilab.org
http://lists.scilab.org/mailman/listinfo/users