Is /:~ on characters using a radix sort? Even so, both sort and from I would think is O(N). What is all the overhead in from?
On Wed, Mar 5, 2014 at 4:45 PM, Raul Miller <[email protected]> wrote: > The rascal! > > -- > Raul > > > On Wed, Mar 5, 2014 at 4:38 PM, Joe Bogner <[email protected]> wrote: > > > hey hey - I posted my first answer before looking at the source and it > > didn't change my answer. Also, Roger has the source in his head and it > > wasn't ruled out of bounds. > > > > On Wed, Mar 5, 2014 at 4:35 PM, Raul Miller <[email protected]> > 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 <[email protected]> > > 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 <[email protected]> > > 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 <[email protected]> > > >> 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 < > > [email protected]> > > >> > 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 > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
