Doing in O(n) gets you in the door; reducing the coefficient gets you the big bucks. :-)
On Wed, Mar 5, 2014 at 2:19 PM, Yike Lu <yikelu.h...@gmail.com> wrote: > I changed the power of 10 by +/- 1, the timing changed by the same order of > magnitude on both "/:~x" and "g{x". The second result we expect, each > lookup is constant time, so the total operation is O(n). The sort implies > that J defaults to bucket/radix sort under the covers for characters. > > Thus the difference is a constant factor between the two (on my machine, > the factor was about 2x). So why is each lookup so slow? > > Another experiment (for 1e8) -- > > g2 =: i. $ x > timer 'g2 { x' > > This was about as fast as the sort. So random access / branch mispredicts > probably have something to do with why the graded lookup is slow. > > But how is sorting as fast as a sequential lookup? > > Tested it out with x2 =: 1e8 $ (26 ? 26), about a factor of 2.5 slower. > Explanation? ASCII characters are 8 bit, ints 32 or 64 bits; radix sort > performs better with smaller words. > > > On Wed, Mar 5, 2014 at 3:35 PM, Raul Miller <rauldmil...@gmail.com> wrote: > > > My guess would be that it has something to do with cache coherence. > > > > Indexing is random access, sorting is more sequential in nature. > > > > But that's just a guess, because I did not cheat and look at the source > or > > anything (at least... not today). > > > > Thanks, > > > > -- > > Raul > > > > > > > > On Wed, Mar 5, 2014 at 2:45 PM, Roger Hui <rogerhui.can...@gmail.com> > > wrote: > > > > > That's my alternative faster expression as well. But the more > > interesting > > > question is, why is it faster? Since we do the grade in both cases, > the > > > comparison is between /:~x and g{x (or x{~g) with g pre-computed. The > > > answer does not depend knowledge specific to J. > > > > > > > > > > > > > > > > > > On Wed, Mar 5, 2014 at 11:38 AM, Joe Bogner <joebog...@gmail.com> > wrote: > > > > > > > Sorting and grading separately seems faster > > > > > > > > timer=: 6!:2 > > > > x=:(1e7 $ 26?26) { 'abcdefghijklmnopqrstuvwxyz' > > > > NB. incumbent > > > > timer 's=: x{~g=: /:x' > > > > 0.0914002 > > > > > > > > NB. alternate > > > > timer 'S=: /:~x[G=: /:x' > > > > 0.0668677 > > > > > > > > s-:S > > > > 1 > > > > G-:g > > > > 1 > > > > > > > > > > > > I am speculating that sorting does it in place? which is faster than > > > > the selection from the grade > > > > > > > > > > > > > > > > On Wed, Mar 5, 2014 at 2:02 PM, Raul Miller <rauldmil...@gmail.com> > > > wrote: > > > > > Hmm... > > > > > > > > > > G=:a.i.S=:/:~x > > > > > is faster. > > > > > > > > > > But while s-:S, g and G are different. > > > > > > > > > > So I'm drawing a blank here, on how to make the grade. > > > > > > > > > > Thanks, > > > > > > > > > > -- > > > > > Raul > > > > > > > > > > > > > > > > > > > > On Wed, Mar 5, 2014 at 1:52 PM, Roger Hui < > rogerhui.can...@gmail.com > > > > > > > wrote: > > > > > > > > > >> Suppose x is a long vector of characters and you need both its > sort > > > and > > > > its > > > > >> grade. Can you do it faster than s=: x{~g=: /:x ? > > > > >> > > > > >> Posed this way, the answer is of course yes. But how, and why is > it > > > > >> faster? > > > > >> > > ---------------------------------------------------------------------- > > > > >> For information about J forums see > > > http://www.jsoftware.com/forums.htm > > > > >> > > > > > > > ---------------------------------------------------------------------- > > > > > For information about J forums see > > http://www.jsoftware.com/forums.htm > > > > > ---------------------------------------------------------------------- > > > > For information about J forums see > http://www.jsoftware.com/forums.htm > > > > > > > ---------------------------------------------------------------------- > > > For information about J forums see http://www.jsoftware.com/forums.htm > > > > > ---------------------------------------------------------------------- > > For information about J forums see http://www.jsoftware.com/forums.htm > > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm