Reverse a list
Peter Haworth
pete at lcsql.com
Wed Feb 11 19:16:56 EST 2015
I just tried this with an in memory SQLite DB using 6.6.2 and 7.0.1.
Results were pretty much identical in both cases. Here they are:
Time to open in-memory db and create a table with one text column: zero
milliseconds
Time to load approx 100k rows into the db: 900 milliseconds
Time to return the data into a variable sorted descending: 300 milliseconds
So the times don't compare with the LC scripts that have been suggested.
If I already had an SQLite database with the data in it then I'd use it for
sure. It's one SELECT statement rather than quite a number of LC script
lines so much easier to read, and pretty sure most users could not tell the
difference between 300 milliseconds and the lower times from the very
inventive scripts that have been suggested.
Oh yes, and doesn't matter whether you're using LC 7 or something prior to
that, although that problem appears to be a bug that is already being fixed.
Pete
lcSQL Software <http://www.lcsql.com>
Home of lcStackBrowser <http://www.lcsql.com/lcstackbrowser.html> and
SQLiteAdmin <http://www.lcsql.com/sqliteadmin.html>
On Mon, Feb 9, 2015 at 7:08 AM, Mike Bonner <bonnmike at gmail.com> wrote:
> 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
> >
> _______________________________________________
> 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