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
