there is some timing advantages to the box avoidance after all:
with 1000 partitions of up to 100 items each (random)
'a b'=.;L:1 ([: (,&< (1 (0}) 0 #~ #)leaf) ([: <@:? 1000 #~ [: >:@:? ])("0))
1000 # 100
timespacex 'b ([: ; <@/:~;.1) a'
0.00370112 1.21792e6
timespacex 'b (] {~ [ (] {~ +/\@[ /:@:{~ ]) /:@]) a'
0.00189664 2.112e6
timespacex 'b (] /: ] ,"_1~ [: +/\ [) a'
0.00300384 2.11008e6
timespacex 'b (] /: ] + +/\@[ * +:@(>./)@:|@]) a'
0.00376704 2.6281e6
----- Original Message -----
From: Roger Hui <[email protected]>
To: Programming forum <[email protected]>
Cc:
Sent: Wednesday, April 15, 2015 12:38 PM
Subject: Re: [Jprogramming] partitioned sort
psort is due to Morten Kromberg, I believe.
If the right argument is numeric, there are alternatives to do partition
sort without boxing but using grade or sort just once.
psort1=: ] /: +/\@[ ,"_1 ] NB. y /: (+/\x),"_1 y
psort2=: ] /: ] + +/\@[ * +:@(>./)@:|@] NB. y /: y + (+/\x) * 2*>./|y
On Wed, Apr 15, 2015 at 8:34 AM, Raul Miller <[email protected]> wrote:
> Someone at Dyalog APL (I'm going to guess Brian Becker, but I could
> easily be wrong) posted this tweet:
>
> https://twitter.com/dyalogapl/status/588351556329803776
>
> which was basically about this APL expression:
>
> psort←{g←⍋⍵ ⋄ ⍵[g[⍋(+\⍺)[g]]]} ⋄ 1 0 0 0 1 0 0 psort 100 300 200 400
> 3 2 1
>
> 100 200 300 400 1 2 3
>
> I don't know if that's going to be readable. Here's a direct link into
> an executable APL environment:
>
> http://tinyurl.com/partitionedsortexample
>
> So... what's going on here?
>
> Well, first off, partioned sort is basically this:
>
> 1 0 0 0 1 0 0 ([: ; <@/:~;.1) 100 300 200 400 3 2 1
> 100 200 300 400 1 2 3
>
> This could be described as "sort within each partition". But this
> approach uses boxing, which winds up being inefficient when you need a
> lot of boxes. And it's worth while to be able to think about
> alternatives to boxing.
>
> So here's another approach:
>
> 1 0 0 0 1 0 0 (] {~ /:@] {~ +/\@[ /:@:{~ /:@]) 100 300 200 400 3 2 1
> 100 200 300 400 1 2 3
>
> Translated to explicit J, that might look something like this:
>
> psort=:4 :0
> gy=: /:y
> sx=: +/\x
> pz=: gy { sx
> gz=: /: pz
> ord=: gz { gy
> ord { y
> )
>
> 1 0 0 0 1 0 0 psort 100 300 200 400 3 2 1
> 100 200 300 400 1 2 3
>
> Note that a general principle which is relevant here is that /: /: y
> represents counting integers in the same order as the original
> argument. And /: /: /: y is the same as /: y. (We are not actually
> using /: /: /: but the result of +/\x is similar in character to /: /:
> +/\ x and thinking about things in this way might help you understand
> how this ordering works.)
>
> Note also that I've made all the intermediate results of this explicit
> implementation be global, so they can be inspected:
>
> gy
> 6 5 4 0 2 1 3
>
> This is the indices we need to sort our right argument. This order is
> mildly complex, and should perhaps be thought of as "unstructured".
> (Its complexity reflects the complexity of the right argument.)
>
> sx
> 1 1 1 1 2 2 2
>
> These are key values to distinguish which partition things go in,
> based on our left argument.
>
> pz
> 2 2 2 1 1 1 1
>
> This is what our partition keys would look like, when they get sorted
> using in right argument order. In this case, they are non-overlapping
> because the value ranges in our example problem do not overlap between
> partitions.
>
> gz
> 3 4 5 6 0 1 2
>
> If you look closely, you'll see that in this case these are just
> counting up in sub-sequences for each partition. In this example, just
> like pz, the complexity here is that of our left argument because in
> this example the range of values in each of our partitions do not
> overlap.
>
> But what we have here are the indices we would need select sorted
> values (if y were sorted) into our partitions (without otherwise
> disturbing their order).
>
> ord
> 0 2 1 3 6 5 4
>
> So this is our original sorting keys (gy) sorted into our sorted
> partition order. Using these indices puts our original y argument into
> the desired order - all without boxing.
>
> Which is kind of neat.
>
> Thanks,
>
> --
> Raul
> ----------------------------------------------------------------------
> 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
