You use s=:/:~x to get the sort and g=:/:x to get the grade. It's faster
than s=:x{~g=:/:x . (That's the bar bet.) Counter-intuitive to anyone who
thinks indexing is always faster than sorting, or that sorting is
necessarily an expensive slow operation.
Knowing this is a strong hint on how to find the minimum of x faster than
the conventional implementation. Without this hint, even expert C
programmers (the ones I asked) can't solve the puzzle. And I mean EXPERT
in capital letters.
APL/J as a tool of thought:
<./x ←→ 1 i.~ 1 x}M⍴0
⌊/x ←→ b⍳1 ⊣ b[x]←1 ⊣ b←M⍴0
On Wed, Mar 5, 2014 at 8:18 PM, Linda Alvord <lindaalv...@verizon.net>wrote:
> But if you use dyadic /: you won't get g , will you? I'm looking
> forward to reading all the quotes again.
>
> Linda
>
>
> -----Original Message-----
> From: programming-boun...@forums.jsoftware.com [mailto:
> programming-boun...@forums.jsoftware.com] On Behalf Of Roger Hui
> Sent: Wednesday, March 05, 2014 11:00 PM
> To: Programming forum
> Subject: Re: [Jprogramming] a good bar bet!
>
> I respectfully suggest you study the dyad /: . The fact that the dyad /:
> is defined to do what it does is one of Ken Iverson's
> masterstrokes<http://keiapl.org/anec/#sort>
> .
>
>
>
> On Wed, Mar 5, 2014 at 7:46 PM, Linda Alvord <lindaalv...@verizon.net
> >wrote:
>
> > For me slow J is fast enough, but I really was delighted when this
> worked
> > at all. No doubt it is slow.
> >
> >
> > ]A=:?10$100
> > 63 92 51 92 39 15 43 89 36 69
> > f=:/:
> > g=:/: { ]
> > h=:f;g
> > h A
> > --------------------T-----------------------------┐
> > │5 8 4 6 2 0 9 7 1 3│15 36 39 43 51 63 69 89 92 92│
> > L-------------------+------------------------------
> >
> > Linda
> >
> >
> >
> > -----Original Message-----
> > From: programming-boun...@forums.jsoftware.com
> > [mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Roger Hui
> > Sent: Wednesday, March 05, 2014 8:45 PM
> > To: Programming forum
> > Subject: Re: [Jprogramming] a good bar bet!
> >
> > It's necessary to have the g because I asked for both the sort (s) and
> the
> > grade, which would be the g.
> >
> > The problem arose in an application where the sort and the grade are used
> > for something else.
> >
> >
> >
> > On Wed, Mar 5, 2014 at 4:32 PM, Don Kelly <d...@shaw.ca> wrote:
> >
> > > Why is it necessary to have 'g'
> > >
> > > repeating the process on my machine which is obviously slower gives
> an
> > > insignifcant time difference.
> > >
> > > 20 timer 's=:/:~x [ /:x'
> > >
> > > 0.172937
> > >
> > >
> > > 20 timer 's=:/:~x [ g=:/:x'
> > >
> > > 0.173672
> > >
> > > Is it because storage is necessary and it is just as fast to store to a
> > > named location rather than to some temporary storage?
> > > Space differences seem small.
> > >
> > > Don Kelly
> > >
> > >
> > > On 05/03/2014 12:11 PM, Joe Bogner wrote:
> > >
> > >> Yes, the grade is done regardless. Here's my reasoning: In the
> > >> incumbent version, s is taken from the grade with from { which is
> > >> slower than just resorting.
> > >> It seems like the difference between sorting and selecting by indexes.
> > >> I am surprised if that's the answer though because selecting by index
> > >> should be fast since it's a contiguous array.
> > >>
> > >> jtifrom looks more complicated than jtsortc but I haven't been able to
> > >> figure out how jtsortc works.
> > >>
> > >> On Wed, Mar 5, 2014 at 2:50 PM, Roger Hui <rogerhui.can...@gmail.com>
> > >> wrote:
> > >>
> > >>> x=: a.{~ 1e7 ?@$ 256
> > >>> timer=: 6!:2
> > >>>
> > >>> 10 timer 's=:x{~g=:/:x'
> > >>> 0.136961
> > >>> 10 timer 's=:/:~x [ g=:/:x'
> > >>> 0.0765459
> > >>>
> > >>> 10 timer '/:~x'
> > >>> 0.012887
> > >>> 10 timer 'x{~g'
> > >>> 0.065751
> > >>> 10 timer '/:x'
> > >>> 0.0606987
> > >>>
> > >>>
> > >>>
> > >>> On Wed, Mar 5, 2014 at 11:45 AM, 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
> > ----------------------------------------------------------------------
> > 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
