Space efficient sorting of arrays 
Author Message
 Space efficient sorting of arrays

Bob Bernecky writes on Sunday, December 16:

Quote:

> > Thanks.  Continuing with the sniffing around, can you please
> > time the following expressions.  In each case time the expression
> > using x, then time it using the APV a.

> >    x{is}?5e5{rho}1e6
> >    a{is}1+2{times}{iota}5e5

> > {grade up}x     vs.    {grade up}a
> > x{iota}x        vs.    a{iota}a
> > a{iota}x        vs.    a{iota}a
> > +/x             vs.    +/a
> > {reverse}x      vs.    {reverse}a

> APEX uses Array Morphology [APL93 -- my how time flies] to detect that
> "a" is an APV. This gave us linear-time algorithms for all of the above
> except reverse. We could handle reverse by, as I suggested to you
> back in the dark ages, by separating arrays from descriptors, and
> using addressing polynomials to perform most structural, and some
> selection operations. I think this was done in APL2; the idea was
> pioneered by Guibas and Wyatt in a 1978 POPL paper. ...

But Bob, the reverse of an APV is also an APV.
A demonstration in J.  The linear representation 5!:5
computes an expression that generates the named object,
and:

   lr=: 3 : '5!:5 <''y.'''

   lr 3+4*i.10
3+4*i.10

   lr |. 3+4*i.10
39+_4*i.10



Fri, 04 Jun 2004 04:59:43 GMT  
 Space efficient sorting of arrays
Bob Bernecky writes on Sunday, December 16:

Quote:

> > Thanks.  Continuing with the sniffing around, can you please
> > time the following expressions.  In each case time the expression
> > using x, then time it using the APV a.

> >    x{is}?5e5{rho}1e6
> >    a{is}1+2{times}{iota}5e5

> > {grade up}x     vs.    {grade up}a
> > x{iota}x        vs.    a{iota}a
> > a{iota}x        vs.    a{iota}a
> > +/x             vs.    +/a
> > {reverse}x      vs.    {reverse}a

> APEX uses Array Morphology [APL93 -- my how time flies] to detect that
> "a" is an APV. This gave us linear-time algorithms for all of the above
> except reverse. We could handle reverse by, as I suggested to you
> back in the dark ages, by separating arrays from descriptors, and
> using addressing polynomials to perform most structural, and some
> selection operations. I think this was done in APL2; the idea was
> pioneered by Guibas and Wyatt in a 1978 POPL paper. ...

Also, I would be surprised if any of these things take linear
linear time in APL2, if the interpreter supports APV and
already knows that the argument is an APV.  For example,
{grade up}a   is either   {iota}n   or its reverse depending
on whether the multiplier for a is positive or 0, or negative.
To compute this result (itself an APV) should take constant time.


Fri, 04 Jun 2004 05:23:43 GMT  
 Space efficient sorting of arrays

Quote:

> Bob Bernecky writes on Sunday, December 16:


> > APEX uses Array Morphology [APL93 -- my how time flies] to detect that
> > "a" is an APV. This gave us linear-time algorithms for all of the above
> > except reverse. We could handle reverse by, as I suggested to you
> > back in the dark ages, by separating arrays from descriptors, and
> > using addressing polynomials to perform most structural, and some
> > selection operations. I think this was done in APL2; the idea was
> > pioneered by Guibas and Wyatt in a 1978 POPL paper. ...

> But Bob, the reverse of an APV is also an APV.
> A demonstration in J.  The linear representation 5!:5
> computes an expression that generates the named object,
> and:

>    lr=: 3 : '5!:5 <''y.'''

>    lr 3+4*i.10
> 3+4*i.10

>    lr |. 3+4*i.10
> 39+_4*i.10

Yes, and there are a bazillion other tiny optimizations like this
that are dead easy to implement and of minimal utility in practical
applications. We get fixed-time reverse for free with the Guibas & Wyatt
work on
ALL arrays, not just APVs. I'm just not convinced that we can get them
implemented in interpreted code without slowing down everything else
that doesn't use them. Not a big slowdown, of course, but with enough
bricks, you
can build a wall.

Now, having said that, I also believe there remains substantial utility
in having APVs in a compiler setting, because there still remain useful
optimizations that are not handled in more general settings. [I'm trying
to think
of a good example...]

Also, remember that array morphology gives us the ability to track and
detect
permutation vectors [PV](of which APVs can be considered a rough
subset), which give us
a lot of power on the algorithm design front. Granted, we get fixed-time
upgrade
on an APV, and only linear-time upgrade on a PV, but where do you run
into upgrades
of APVs in real applications? Upgrades of PVs appear in idioms a lot,
such as the
"upgrade upgrade" to perform ranking.

Bob

--
Robert Bernecky                  Snake Island Research Inc.

+1 416 203 0854                  Toronto, Ontario M5J 2B9 Canada
http://www.snakeisland.com



Tue, 08 Jun 2004 12:54:53 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. Space efficient sorting of arrays

2. J/APL memory use [was Re: SV: Space efficient sorting of arrays]

3. J/APL memory use [was Re: SV: Space efficient sorting of

4. re efficient sorting of arrays

5. space-efficient top-N algorithm

6. Anybody know a fast efficient sorting Algorithm

7. GC efficient sort

8. Array#sort! returns nil when array empty

9. Efficient Mutable Arrays

10. Is Ruby Array#shift/unshift Efficient?

11. macro for efficient array operations

12. An efficient way to pass 3-D arrays to functions

 

 
Powered by phpBB® Forum Software