Reverse a list

[Mike Bonner]

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
>