In the example, N and M are not the size of the rows/columns of the matrix, instead:
N is the number of elements in the matrix so a 5000x2000 matrix has N=10**7. M is the number of greatest elements you want from the call to maximum_n_ind() so to get the top 50 elements then M=50. Hope this helps, Chris On Wed, Oct 22, 2014 at 12:38 AM, Ronak Agrawal <[email protected]> wrote: > Thanks for the input > > Kindly correct me, if I get the big O notation correct > Let N = 2000 , M = 1000 be a matrix- > No of Elem = 2,000,000 > > Then, > > O(N*M) = O(2000*1000) > O(N*ln(N) = O(2000*8) to O(2000*2000) > > Let n = 50; > > I could not find the much difference in small matrix, as my initial step is > taking larger amount of time Multiplying matrix $a(2000,2000) with the > transpose > > $a x transpose($a); > > I guess if n is negligible following the method suggested by you ll be > better... > > I will also check the performance measure for the following: > i.e finding "top20" elements and then again calling the function to find > "top50" elements against qsort > > $m->flat->maximum_n_ind($top25) > $m->flat->maximum_n_ind($top50) > > Comparing with > > Qsort(); > First($top25) > First($top50) > I guess calling First($top25) elements will be done in constant time.. > > On Wed, Oct 22, 2014 at 3:07 AM, Chris Marshall <[email protected]> > wrote: >> >> Since the running time of the maximum_n_ind() is O(N*M) >> and the running time of the quicksort algorithm averages >> as O(N*ln(N)) with a worst case of O(N**2) you'll do better >> with qsort first when ln(N) is about M in size which is 17 >> for N = 5000**2. That means that for small M doing the >> qsort second is best but for large N doing qsort as Derek >> suggested will be faster. >> >> If you really need to optimize your performance, you need >> to time the various approaches to see which is faster and >> when. >> >> Hope this helps, >> Chris >> >> On Mon, Oct 20, 2014 at 9:50 AM, Chris Marshall <[email protected]> >> wrote: >> > qsort is using quicksort so the performance is that of >> > quicksort. It would probably be faster to use maximum_n_ind >> > with an appropriately large number for N and then use qsort >> > or uniq to determine which elements you need. >> > >> > --Chris >> > >> > On Mon, Oct 20, 2014 at 4:17 AM, Ronak Agrawal <[email protected]> >> > wrote: >> >> >> >> Thanks Chris and Derek for the optimized method >> >> >> >> For unique I was going to use squaretotri() and then sort it >> >> The rle had went out of my mind... >> >> >> >> I have a doubt, is it efficient to use the qsort method in large matrix >> >> ( >> >> say 5000 x 5000) > > _______________________________________________ Perldl mailing list [email protected] http://mailman.jach.hawaii.edu/mailman/listinfo/perldl
