Getting indexes of rows of matrix with more than n repetitions
in [Matlab]
|
From: Jan Simon on 9 Jan 2010 08:11 Dear Bruno! > Bad news, I implement an in-place 1D quicksort (the unstable version) and it get beaten by Matlab SORT with two outputs calling. My Matlab is 2010A prerelease; I compile the mex with MSVC 6. My guess is inplace sorting requires accessing in cascade the double data, and it slows the thing down. Your bad news are good news, if I follow the 2nd part of your advice: > So I won't go any further. Better spend the effort on something else. I'll spend my effort on something else and the overall speedup gets higher! Thank you very much, Bruno! Jan
From: Bruno Luong on 9 Jan 2010 09:43 "Jan Simon" <matlab.THIS_YEAR(a)nMINUSsimon.de> wrote in message <hi9v98$qr5$1(a)fred.mathworks.com>... > > Your bad news are good news, if I follow the 2nd part of your advice: Wait a minute Jan, then there is a new bad news ;-) : I modified an indexing in my code, and now it's faster than Matlab (about -50% for 1e6 elements). Bruno
From: Bruno Luong on 9 Jan 2010 09:50 Arrg forget it, the test is not valid. Sorry. > > Wait a minute Jan, then there is a new bad news ;-) : I modified an indexing in my code, and now it's faster than Matlab (about -50% for 1e6 elements). > > Bruno
From: Jan Simon on 9 Jan 2010 11:29 Dear Bruno! I dig in source of quickersort and stabilized quicksort variants. Especially the reduction of recursion is interesting for large arrays, e.g. see: http://www.angelfire.com/pq/jamesbarbetti/articles/sorting/001_QuicksortIsBroken.htm Then it seems, like it is worth to stop quicksorting and start insort, if the block is smaller than 9 (or 15 according to Knuth) elements. But simultaneously I try to find an efficient C-algorithm to create permutations: Choose K elements from a vector without repetitions and with order. I hope I do not confuse both programming threads. CSSMers on saturdays. Jan
From: Bruno Luong on 9 Jan 2010 14:06
"Jan Simon" <matlab.THIS_YEAR(a)nMINUSsimon.de> wrote in message <hiaasf$mge$1(a)fred.mathworks.com>... > Dear Bruno! > > I dig in source of quickersort and stabilized quicksort variants. > Especially the reduction of recursion is interesting for large arrays, e.g. see: > http://www.angelfire.com/pq/jamesbarbetti/articles/sorting/001_QuicksortIsBroken.htm > Then it seems, like it is worth to stop quicksorting and start insort, if the block is smaller than 9 (or 15 according to Knuth) elements. This is exactly what I have done. My implementation of the sort algorithms are adapted from the sparse subindex package on FEX. I'll post the C-mex file of the stable quick sort in the next (long). For large arrays (1e6-1e7 elements), Matlab beats my code by 2-3 time in speed. >> A=randn(1,1e6); >> tic; I=sortidx_mex(A); toc Elapsed time is 0.295162 seconds. >> tic; [trash Imatlab]=sort(A); toc Elapsed time is 0.140457 seconds. >> isequal(I,Imatlab) ans = 1 >> > > But simultaneously I try to find an efficient C-algorithm to create permutations: Choose K elements from a vector without repetitions and with order. I hope I do not confuse both programming threads. > If you want you can compare with my implementation MIN/MAX Selection on FEX. Bruno |