SORRY: n.(n-1)/2 but stll n^2 Sent from Heinz Nabielek
> On 03 Feb 2018, at 15:57, Heinz <[email protected]> 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:[email protected]] On Behalf Of Rafael > Guerra > Sent: 03 February 2018 12:42 > To: [email protected] > 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 > [email protected] > http://lists.scilab.org/mailman/listinfo/users > _______________________________________________ users mailing list [email protected] http://lists.scilab.org/mailman/listinfo/users
