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

[Heinz Nabielek]

SORRY: n.(n-1)/2 but stll n^2

Sent from Heinz Nabielek

> On 03 Feb 2018, at 15:57, Heinz <heinznabielek at me.com> wrote:
> 
> 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
>