Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.postscript > #3728

Re: in-place reverse?

Show all headers | View raw

On Friday, January 21, 2022 at 4:11:00 AM UTC-6, David Newall wrote:
> On 22/10/21 5:24 pm, luser droog wrote: 
> > I was reading through some old code and found this function to 
> > reverse an array.
> > ...
> > And I wondered if it were possible to do it in-place, without creating 
> > a new array.
> My first idea was this: 
> 
> /reverse { 
> dup aload
> 0 1 2 index length 1 sub {
> 1 index exch 4 -1 roll put 
> } for 
> pop 
> } bind def 
> 
> It works, is fast, but uses a lot of stack if the array is large. 
> 

That's pretty good. It took me a second to think through it. But I think you
can go further and remove the 'dup' and the 'pop' (it's the same array you're
popping, or I suppose you could 'exch pop' to get rid of the other one).

> So I came up with this, which uses minimal stack and gives similar 
> performance (when bound): 
> 
> /reverse { 
> dup xcheck exch 
> dup length 1 sub 
> 0 1 3 index length 2 idiv 1 sub { 
> 2 index exch 
> 1 index 3 index get 
> 2 index 4 index 1 index 4 index get put 
> put 
> 1 sub
> } for 
> pop 
> exch {cvx} if
> } bind def 
> 
> By the way, I liked the xcheck. Obviously that's something I borrowed.

That's a nice balance. for gives you one index. keeping the other on the
stack is simple. And actually doing a swap avoids the erroneous path
I followed trying to do everything like map().

I start to wish there were a nicer syntax to do 'index' operations. When there's
too many I start to write stack comments to follow it. But over time it's started
to seem like that's a warning sign and there's usually a different way to 
conceive the problem where all the stack business falls neatly into place.
Until then I guess there's something like:

  << /2nd{1 index} /3rd{2 index} /4th{3 index} /5th{4 index} /6th{5 index} >> begin

(or up to whatever number you like.)

Back to comp.lang.postscript | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

in-place reverse? luser droog <luser.droog@gmail.com> - 2021-10-21 23:24 -0700
  Re: in-place reverse? luser droog <luser.droog@gmail.com> - 2021-10-22 17:13 -0700
    Re: in-place reverse? luser droog <luser.droog@gmail.com> - 2021-10-22 17:42 -0700
    Re: in-place reverse? luser droog <luser.droog@gmail.com> - 2021-10-23 16:54 -0700
  Re: in-place reverse? luser droog <luser.droog@gmail.com> - 2021-10-22 17:16 -0700
  Re: in-place reverse? James <news@oxdrove.co.uk> - 2021-10-24 11:04 +0100
    Re: in-place reverse? luser droog <luser.droog@gmail.com> - 2021-10-24 17:59 -0700
    Re: in-place reverse? luser droog <luser.droog@gmail.com> - 2021-11-08 10:08 -0800
  Re: in-place reverse? David Newall <davidn@davidnewall.com> - 2022-01-21 21:10 +1100
    Re: in-place reverse? luser droog <luser.droog@gmail.com> - 2022-01-21 21:22 -0800
      Re: in-place reverse? jdaw1 <jdawiseman@gmail.com> - 2022-08-10 13:11 -0700

csiph-web