Reverse a list

[Dave Cragg]

I tried an array method:


function arevers p
   split p by cr
   put empty into t
   put the number of lines in the keys of p into tNumElems
   repeat with i = tNumElems down to 1
      put p[i] & cr after t
   end repeat
   return t
end arevers

This is slower than Alex's method in 6.0.2 (21 ms vs 9ms). And while slower in 7.0.1, now much faster that Alex's method. (74 ms vs 446ms)

The increase in speed of the "put before" method was interesting (from 242ms to 92ms) 


Cheers
Dave Cragg


> On 8 Feb 2015, at 23:37, Alex Tweedly <alex at tweedly.net> wrote:
> 
> Wow. I can see why LC7 would be expected to be slower for this case - in the multi-byte Unicode world, char indexing isn't as simple as it used to be. BUT in this specific case, you can actually replace all use of "char" by "byte" and still be sure it works (ummm - except if the CR equivalent can be multi-byte - but I'll choose to ignore that :-)   However, using position by byte is just as slow !!
> 
> I'll have to play around a bit more to see if I can fathom out why that should be.
> 
> - -Alex.
> 
> On 08/02/2015 23:18, Mike Bonner wrote:
>> Version 6.6.2, your "by position" method is by FAR the fastest 26 millisec
>> for 80k lines.  repeat takes almost 9 seconds.  The sort function method
>> not passing text back and forth,  takes 102 millisec which isn't slouchy by
>> any means.
>> 
>> Jump to version 7.0.1 and the by position method needs some major love.
>> The repeat method is almost twice as fast in 7, the sort without passing
>> the text method is within a few millisec of 6.6.2, and the by position
>> method is unusable at 21 seconds.  REALLY hope they get some optimization
>> going soon.
>> 
>> On Sun, Feb 8, 2015 at 3:37 PM, Alex Tweedly <alex at tweedly.net> wrote:
>> 
>>> Indeed. Jerry was (as usual) correct - if the engine can do it, then the
>>> engine will normally be faster.
>>> 
>>> BUT sorting a list requires moving the data around quite a lot, AND
>>> sorting something that actually reverses it can be a pathologically bad
>>> case (e.g. if the engine uses any variant of quicksort())..
>>> 
>>> SO - take the original idea, and examine how it *might* be improved .....
>>> 
>>> The problem here is that "put ... before ..." requires all existing data
>>> in the destination container to be moved (i.e. copied) to make space.
>>> 
>>> SO, instead, we can use "put ... into char x to y of ..." - since it uses
>>> char indexing, it takes constant time (i.e. no scan, just directly replace
>>> the chars.  I've attached my complete code so anyone can try it easily -
>>> for my test data of approx 8000 lines, this takes 8 msecs, versus 588 for
>>> the original version.
>>> 
>>> -- Alex.
>>> 
>>> on mouseup
>>>    put fld "fldout" into tstart
>>> 
>>>    put tstart into ta
>>>    repeat 200 times
>>>       put tstart after ta
>>>    end repeat
>>>    put ta into tstart
>>> 
>>>    put the millisecs into t1
>>>    put revers(ta) into tb
>>>    put the millisecs - t1 & CR after msg
>>> 
>>>    put tstart into ta
>>>    put the millisecs into t1
>>>    put qrevers(ta) into tc
>>>    put the millisecs - t1 & CR after msg
>>> 
>>>    if tb = tc then put "OK" after msg
>>> end mouseup
>>> 
>>> function revers p
>>>    repeat for each line l  in p
>>>       put L &CR before t
>>>    end repeat
>>>    return t
>>> end revers
>>> 
>>> function qrevers p
>>>    put p into t
>>>    put the number of chars in t into tlen
>>>    repeat for each line l in p
>>>       put the number of chars in l into tl
>>>       put l & cr into char (tLen-tl) to tLen of t
>>>       subtract (tl+1) from tLen
>>>    end repeat
>>>    return t
>>> end qrevers
>>> 
>>> 
>>> On 08/02/2015 21:52, J. Landman Gay wrote:
>>> 
>>>> Just tinkering around on a lazy Sunday, and I thought I'd come up with a
>>>> neat way to reverse a list without using the traditional clunky method:
>>>> 
>>>> function reverseSort pList
>>>>   repeat for each line l in pList
>>>>     put l & cr before tList
>>>>   end repeat
>>>>   return tList
>>>> end reverseSort
>>>> 
>>>> One of the best things I learned from a past LC converence came from
>>>> Jerry Daniels who said "let the engine do it." It's almost always faster
>>>> and more efficient. With that in mind I wrote this:
>>>> 
>>>> local sNum
>>>> 
>>>> function reverseText pList
>>>>   put the number of lines in pList into sNum
>>>>   sort lines of pList numeric by reverseSort(each)
>>>>   return pList
>>>> end reverseText
>>>> 
>>>> function reverseSort pTxt
>>>>   subtract 1 from sNum
>>>>   return sNum && pTxt
>>>> end reverseSort
>>>> 
>>>> Works great and I was proud. Then I did some timing tests and found out
>>>> the two methods are very close to equivalent in timing, and on long lists,
>>>> the first way is actually faster.
>>>> 
>>>> So much for improving on LC's text chunking speed. Pah.
>>>> 
>>>> 
>>> _______________________________________________
>>> use-livecode mailing list
>>> use-livecode at lists.runrev.com
>>> Please visit this url to subscribe, unsubscribe and manage your
>>> subscription preferences:
>>> http://lists.runrev.com/mailman/listinfo/use-livecode
>>> 
>> _______________________________________________
>> use-livecode mailing list
>> use-livecode at lists.runrev.com
>> Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
>> http://lists.runrev.com/mailman/listinfo/use-livecode
> 
> 
> _______________________________________________
> use-livecode mailing list
> use-livecode at lists.runrev.com
> Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
> http://lists.runrev.com/mailman/listinfo/use-livecode