Reverse a list

Mike Kerner MikeKerner at roadrunner.com
Mon Feb 9 09:12:09 EST 2015


What about using an index, instead of the actual data?  With the times
quoted in 7, I wonder if using an SQLite or mySQL db would be faster.

On Mon, Feb 9, 2015 at 7:03 AM, Dave Cragg <dave.cragg at lacscentre.co.uk>
wrote:

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



-- 
On the first day, God created the heavens and the Earth
On the second day, God created the oceans.
On the third day, God put the animals on hold for a few hours,
   and did a little diving.
And God said, "This is good."



More information about the Use-livecode mailing list