Reverse a list

[Peter M. Brigham]

Harking back to the original discussion on reversing a list -- still the subject of this thread, here's the original example as I saved it in my library.

function reverseSort pList, pDelim
   -- reverse sorts an arbitrary list
   --    ie, item/line -1 -> item/line 1, item/line -2 -> item/line 2, etc.
   -- pDelim defaults to cr
   -- from an exchange on the use-LC list
   --    this was the fastest pure LC method of several proposed
   if pDelim = empty then put cr into pDelim
   split pList by pDelim
   put the keys of pList into indexList
   put the number of lines of indexList into i
   repeat for each line tLine in indexList
      -- tLine is never used, but "repeat for each" is faster than "repeat <n> times"
      --    and this iterates the correct number of times
      put pList[i] & pDelim after outList
      subtract 1 from i
   end repeat
   delete char -1 of outList
   return outList
end reverseSort

Note that the repeat is a "repeat for each line tLine…" even though the value of tLine is never actually used within the repeat loop. It's incredibly fast to do it that way, and it's an easy way to repeat something a foreseeable number of times. Using a "repeat n times" is glacial by comparison. I do agree that the dictionary should not just say the "repeat for each" form is much faster, it should say the "repeat for each" form is MUCH, MUCH faster.

-- Peter

Peter M. Brigham
pmbrig at gmail.com
http://home.comcast.net/~pmbrig

On Feb 14, 2015, at 6:00 PM, Richard Gaskin wrote:

> Mike Kerner wrote:
> ...
> > REPEAT FOR is .129 seconds, and REPEAT WITH is TWENTY SEVEN THOUSAND
> > TIMES SLOWER (for this operation)??!?!?!?!?!???
> >
> > Hey, Pete, "That's a common technique"...WHAT?  If it's so common,
> > and all of this is common knowledge, then how come it isn't
> > documented, anywhere
> 
> The Dictionary entry for "repeat" notes that the "for each" form is much faster than "with".
> 
> 
> > and how come this is the first time I remember EVER hearing about this
> > difference?
> 
> Good question.  This comes up in the forums and/or this list almost every month or so.
> 
> The speed difference will vary according to the size of each line and the size of the lines, but "order of magnitude" is usually a pretty fair minimal expectation for the speed boost with this.
> 
> It's one of those things we don't think about until we see it in action, and then it seems almost self-evident:
> 
> Chunk expressions are handy, but expensive.  We usually don't think about the expense because the engine's pretty fast, but with large-scale operations like traversing a long list it adds up enough to be significant.
> 
> Many chunk expressions require the engine to examine the data character by character, keeping track of delimiters as it goes.
> 
> With this:
> 
>  repeat with i = 1 to the number of lines of tData
>     DoSomethingWith line i of tData
>  end repeat
> 
> ...the engine first needs to examine every character in tData to count the number of CRs, then each time through the loop it needs to do it again to the next line.  First time through it reads from the beginning until the first CR, second time through it goes from the beginning until the second CR, and so forth, so by the time you get several thousand lines into it it's doing the same long character-by-character comparison each time through, getting successively slower and slower.
> 
> But here:
> 
>  repeat for each line tLine in tData
>      DoSomethingWith tLine
>   end repeat
> 
> ...the engine only counts to the next CR, puts it into tLine, and remembers where it left off so each time through the loop it's only reading a single line.
> 
> While the former takes logarithmically longer to complete, the latter scales flatly.
> 
> 
> > What else don't I know about???
> 
> Mode 14.  :)
> 
> 
> > You would think that Edinburgh would think about tweaking an
> > algorithm, since REPEAT WITH seems to be a special case of
> > REPEAT FOR, and you can generate the REPEAT WITH behavior
> > by wrapping the REPEAT FOR...
> 
> But there's one key difference which makes each form worth keeping in case you need it:
> 
> With "repeat with i =..." the data in the variable being traversed can change.  Sometimes you may need that.
> 
> But with "repeat for each..." the data being traversed is not allowed to change, because if it did then the line endings might have been altered and its attempt to keep track of where it is would fail.
> 
> So each form has its own special benefits.  I tend to use "repeat for each" most of the time, but I'm glad "repeat with" is available for the rare cases where it's useful.