Reverse a list

Alex Tweedly alex at tweedly.net
Sun Feb 8 23:37:19 CET 2015


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.
>




More information about the use-livecode mailing list