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
