Reverse a list

Mike Kerner MikeKerner at roadrunner.com
Mon Feb 9 16:46:22 CET 2015


and don't get me wrong, it's not ideal to have to kluge this way, just like
it's not ideal to have to kluge around the last item in a container being
empty.  I'm not a fan of either behavior.  Both should be dealt with, and
this is just another reason why I will be avoiding 7.0 as long as
possible.  I'm just curious for the sake of asking the question, whether
having the db do the sort is faster.

I guess that makes me ask another question:  I wonder if somehow making
unicode optional for those of us who don't deal with two-byte languages
would be possible, so we're not stuck with the extra...stuff...that comes
with it.

On Mon, Feb 9, 2015 at 10:40 AM, Mike Kerner <MikeKerner at roadrunner.com>
wrote:

> If you use SQLite or mySQL, you'd have to do the same thing with the
> index, so unless you already have the data structure in place, you'ld have
> to create the table, populate the table with the values and the indexes,
> and then order by the index and read the data back, but all of that is done
> with the db commands in the language.
>
> On Mon, Feb 9, 2015 at 10: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
>>
>
>
>
> --
> 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."
>



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