There are a host of expressions involving ⍋ ⍒ ⍳ ∊ that "everyone knows" but need to be reexamined in view of improved implementations. e.g. there is no need to avoid ⍋⍋x for computing the ranking of x.
Basically, ⍋ ⍒ ⍳ ∊ has linear (i.e. optimal) algorithms for small range arguments. x=: ?~ 20 y=: 1e6+x Both x and y are small range, and: 100 timer '/:x' 3.85803e_6 100 timer '/:y' 4.33854e_6 100 timer '/:/:x' 5.98959e_6 100 timer '/:/:y' 6.26057e_6 ----- Original Message ----- From: Ian Clark <[email protected]> Date: Sunday, May 1, 2011 13:11 Subject: Re: [Jprogramming] A permutation of i.y To: Programming forum <[email protected]> > It must have been the early 1980's I last played with > permutations in > APL, and it would have been VS APL... > > I was well aware of the properties of grade-up (⍋) -- after all it > returns a rearrangement to the ordered list, ie inverts the > rearrangement -- but didn't use it because it did a sort, preferring > to use iota (⍳) --c/f (i.). > > I note your point that we have much better sorts nowadays... > > ] p=: 8?8 > 6 0 1 7 2 3 5 4 > I=: i.8 > p i. I NB. invert p > 1 2 4 5 7 6 0 3 > /:p NB. ditto > 1 2 4 5 7 6 0 3 > timer 'p i. I' > 1.09863e_5 > timer '/:p' > 9.00269e_6 > > I can't believe how I didn't twig Henry's use of (/:) until you > pointed it out, which would have given the game away. In my > haste I > misread it as Transpose, wondered how that could have worked, and > resolved to look into the matter later. Hence my remark about needing > to know my primitives better. :-)) > > > On Sun, May 1, 2011 at 4:00 PM, Roger Hui <[email protected]> wrote: > > Likewise in APL ⍋ computes the inverse of a permutation > > and has been so for 45 years. Some in APL employ > > circumlocutions because ⍋ is slower, but it is slower > > no longer (in at least one APL :-). > > > > > > > > ----- Original Message ----- > > From: Ian Clark <[email protected]> > > Date: Sunday, May 1, 2011 7:26 > > Subject: Re: [Jprogramming] A permutation of i.y > > To: Programming forum <[email protected]> > > > >> Thanks, Roger. > >> I had that feeling ip was more complicated than it need be. I > really>> need to know my primitives better, every-which-way. > >> > >> > >> On Sun, May 1, 2011 at 3:17 PM, Roger Hui > <[email protected]> wrote: > >> > ip is just /: > >> > > >> > ip x=: 10?10 > >> > 0 1 3 9 7 8 4 5 2 6 > >> > /: x > >> > 0 1 3 9 7 8 4 5 2 6 > >> > > >> > If you substitute then tacitize, ip@baa becomes one > >> > of the Rich/Boss creations of earlier today. > >> > > >> > > >> > > >> > ----- Original Message ----- > >> > From: Ian Clark <[email protected]> > >> > Date: Sunday, May 1, 2011 7:12 > >> > Subject: Re: [Jprogramming] A permutation of i.y > >> > To: Programming forum <[email protected]> > >> > > >> >> ...Y'know, once you ask the question in the right way, the > answer>> >> becomes obvious... > >> >> > >> >> I already have a verb around to invert permutations: > >> >> ip=: ] i. [: i. # > >> >> Now the inverse of the permutation we want is easy to > define. We > >> >> simply extract x and haul it to the front: > >> >> baa=: 4 : 'x,(i.y)-.x' > >> >> Hey presto! > >> >> 3 ip@baa 10 > >> >> 1 2 3 0 4 5 6 7 8 9 > >> >> > >> >> Tacitly: > >> >> foo=: (] i. [: i. #)@([ , [ -.~ [: i. ]) > >> >> timer '3 foo 10' > >> >> 2.79236e_5 > >> >> > >> >> ...which I think is one of the fastest. > >> >> > >> >> On Sun, May 1, 2011 at 2:01 PM, Ian Clark > >> >> <[email protected]> wrote: > >> >> >> btw: why is this useful? > >> >> > > >> >> > I was waiting for someone to ask... > >> >> > > >> >> > I often find I'm interactively editing a list t of > strings - > >> - often > >> >> > large, and often (though not always) a 2D char matrix -- > >> frequently>> > sorting them to promote or demote a given > entry. It's > >> >> convenient for > >> >> > me to rearrange t using a permutation, p, like so: > >> >> > p{t > >> >> > especially as successive p's can be multiplied together to > >> >> apply in > >> >> > one-shot, or to apply as the inverse-perm to revert to a > previous>> >> > stage. > >> >> > And to add a new line at position (i) in a comparable way: > >> >> > p=. i foo >:#t > >> >> > p{ newline,t > >> >> > rather than like so: > >> >> > (i{.t),newline, i}.t > >> >> > which growing up on smaller and slower computers > distresses me. > >> >> > > >> >> > What I've been asking for is help towards an efficient p. > >> >> > > >> >> > You can also do: > >> >> > p{ t,newline > >> >> > which is why I'm also interested in solutions floating > the last > >> >> > element down to position i, as well as the first element up. > >> >> > > >> >> > Succint float-down solutions seem to be easier to find. I > >> >> suspect this > >> >> > is thanks to the way A. orders permutations > >> lexicographically, ie > >> >> > back-to-front from the way I'd do it. > >> >> > > >> >> > Now you know what I want to use it for, am I barking up > the wrong > >> >> > tree: is there a far better approach to the problem of > >> rearranging>> > large lists? > >> >> > > >> >> > > >> >> > On Sun, May 1, 2011 at 2:59 AM, Steven Taylor > >> >> <[email protected]> wrote: > >> >> >> 3 /:@:(([,-.~) i.) 10 > >> >> >> neat. I liked Henry's sneaky version: > >> >> >> > >> >> >> 3 /:@(0} i.) 9 > >> >> >> I need to catch up with the thread and think through > the C. > >> >> and A. > >> >> >> approaches a little more. > >> >> >> > >> >> >> btw: why is this useful? > >> >> >> > >> >> >> -Steven > >> >> >> > >> >> >> > >> >> >> On 30 April 2011 23:49, Marshall Lochbaum > >> >> <[email protected]>wrote:>> > >> >> >>> Probably not very fast, but this one is cool: > >> >> >>> 3 /:@:(([,-.~) i.) 10 > >> >> >>> 1 2 3 0 4 5 6 7 8 9 > >> >> >>> > >> >> >>> Marshall > >> >> >>> > >> >> >>> -----Original Message----- > >> >> >>> From: [email protected] > >> >> >>> [mailto:[email protected]] On Behalf Of > >> R.E. Boss > >> >> >>> Sent: Saturday, April 30, 2011 4:48 PM > >> >> >>> To: 'Programming forum' > >> >> >>> Subject: Re: [Jprogramming] A permutation of i.y > >> >> >>> > >> >> >>> This revealed an error in my solution. > >> >> >>> It should be > >> >> >>> > >> >> >>> 3 7 (+/@:!@(]->:@([+ i.@-~)/@[) A. i.@] )10 > >> >> >>> 0 1 2 4 5 6 7 3 8 9 > >> >> >>> > >> >> >>> 0 3 (+/@:!@(]->:@([+ i.@-~)/@[) A. i.@] )10 > >> >> >>> 1 2 3 0 4 5 6 7 8 9 > >> >> >>> > >> >> >>> If only the first item has to be moved, then you get the > >> simpler>> >>> > >> >> >>> 3 (+/@:!@(]->:@i.@[) A. i.@] )10 > >> >> >>> 1 2 3 0 4 5 6 7 8 9 > >> >> >>> > >> >> >>> > >> >> >>> R.E. Boss > >> >> >>> > >> >> >>> > >> >> >>> > -----Oorspronkelijk bericht----- > >> >> >>> > Van: [email protected] > >> [mailto:programming- > >> >> >>> > [email protected]] Namens Brian Schott > >> >> >>> > Verzonden: zaterdag 30 april 2011 17:40 > >> >> >>> > Aan: Programming forum > >> >> >>> > Onderwerp: Re: [Jprogramming] A permutation of i.y > >> >> >>> > > >> >> >>> > Yet another approach? > >> >> >>> > > >> >> >>> > foo0=: +/@:!@:>:@:i. > >> >> >>> > foo =: (<:@]-&foo0-~) A. i.@] > >> >> >>> > 3 foo 9 > >> >> >>> > 1 2 0 3 4 5 6 7 8 > >> >> >>> > > >> >> >>> > > >> >> >>> > On Fri, Apr 29, 2011 at 10:05 AM, Raul Miller > >> >> <[email protected]>>>> wrote: > >> >> >>> > > This might be what you want: > >> >> >>> > > > >> >> >>> > > foo=: (C.~ <)&i.~ > >> >> >>> > > > >> >> >>> > > 3 (C.~ <)&i.~ 9 > >> >> >>> > > 1 2 0 3 4 5 6 7 8 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
