Reverse a list

[Mike Bonner]

Yeah, the difference is rather shocking.  Really hoping for a major tuneup.


On Sun, Feb 8, 2015 at 4:37 PM, 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
>