Reverse a list

Richard Gaskin ambassador at fourthworld.com
Sun Feb 15 00:00:17 CET 2015


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.

-- 
  Richard Gaskin
  Fourth World Systems
  Software Design and Development for the Desktop, Mobile, and the Web
  ____________________________________________________________________
  Ambassador at FourthWorld.com                http://www.FourthWorld.com



More information about the use-livecode mailing list