Reverse a list
Mike Bonner
bonnmike at gmail.com
Mon Feb 9 10:08:49 EST 2015
I like the idea Mike K.
The slow part with the array method is rebuilding the list. Why not just
build the array, grab and reverse numeric sort the keys and use the data
directly from the array? For 80k lines, the split takes 24 ms. Putting the
keys into a variable, and reverse sorting them takes 2 ms (6.6.2) On
7.0.1 the split takes 56ms, placing the keys and sorting them takes 11ms
total 67ms fastest, the nearest being sort with function at 125ms. After
that is repeat at over 2 sec and the broken by position at 22+ seconds.
Unless the whole list will be spit back out for display purposes, how its
stored shouldn't matter right?
Anyone up to test sqlite? In memory db should be pretty zippy I'd guess.
On Mon, Feb 9, 2015 at 7:12 AM, Mike Kerner <MikeKerner at roadrunner.com>
wrote:
> 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."
> _______________________________________________
> 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
>
More information about the use-livecode
mailing list