Reverse a list

[Peter TB Brett]

On 2015-02-16 22:02, Mike Kerner wrote:
> I don't think I follow on the first part.  Edinburgh says that the
> complexity of the two traversals are dramatically different.  repeat 
> for
> each is somewhere between nlogn and n, and repeat with is n^2.  At 
> least
> for the case of your squares of integers, I would expect that there is 
> a
> crossover where it's going to be faster to build the list, first.  I 
> don't
> know if that is at 100, 1000, or some bigger number, but n vs. n^2 is a
> very big difference.
> 

You are mistakenly fixating on the "repeat" syntax.  The cost of the 
"repeat with..." form of your loop over lines isn't in the actual repeat 
syntax -- it's what comes before it and what's in the loop body.

     put the number of lines in tData into N -- This chunk op is O(N)
     repeat with i = 1 to N                  -- This is very very cheap
         put line i of tData into tLine      -- This chunk op is O(N) and 
occurs N times
         -- Operate on tLine
     end repeat

Compare with your "printing the squares of integers" example:

     repeat with i = 1 to 100 -- This is very very cheap
         put i*i              -- This is O(1) and occurs N times
     end repeat

The cost is *not* in the repeat form.  The cost is in the chunking 
operations.  The "repeat for each..." form of your loop is faster 
because it requires fewer chunking operations.

                                    Peter

-- 
Dr Peter Brett <peter.brett at livecode.com>
LiveCode Engine Development Team