[PD] list-sort

[Matt Barber]

Very fast, but what I like about list-abs is its pedagogical potential
for students who will never look at C-code but might be interested to
see things go in Pd.

But yeah, a set of externals for production purposes might be neat.

Matt

On Wed, Dec 3, 2008 at 12:25 PM, Martin Peach <martin.peach at sympatico.ca> wrote:
> Matt Barber wrote:
>>
>> So instead, actually implement it in an array and sort it in place!
>>
>> Very fast.
>>
>
> (Of course it works for lists of numbers only). It would be even faster to
> have coded externals that operate on tables like that. I have made one,
> [mrpeach/tabfind], that gives the nth index of a number or list of numbers
> found in a table. This follows Miller's suggestion that tables are the right
> way to manipulate strings without adding them to the symbol table. An
> external that sorted a table in place would be very fast.
>
>
> Martin
>
>
>
>
>
>
>>
>> On Tue, Dec 2, 2008 at 10:16 PM, Matt Barber <brbrofsvl at gmail.com> wrote:
>> > Also, I find it extremely tempting to think of a list of numbers as an
>> > array[ ], but this analogy won't hold because you can't operate on the
>> > list in-place -- I'm sure a lot of the overhead is in feeding entire
>> > lists back and forth and around to the different parts of the patches.
>> >  Maybe the algorithm with the fewest total [list] operations sometimes
>> > wins out over the algorithm that's in general more efficient.
>> >
>> > Matt
>> >
>> >
>> >
>> > On Tue, Dec 2, 2008 at 10:01 PM, Matt Barber <brbrofsvl at gmail.com>
>> > wrote:
>> >> For what it's worth,
>> >>
>> >> I just ran one possible benchmark on the [list-*sort] abstractions
>> >> submitted recently, using [list-random] and [realtime].
>> >>
>> >> I think overall the overhead for [list-sort] is much less than for
>> >> [list-shellsort] -- for short lists (<100) it takes about half the
>> >> time.  [list-shellsort] is a bit quicker when the variance of the
>> >> elements is smaller (which makes sense because the more alike the
>> >> elements are the less the innermost loop will have to run) -- but
>> >> [list-sort] still beats it.  I have a feeling that some of the
>> >> overhead in [list-shellsort] is in the [list-swap] function and other
>> >> list-abs objects, which are a little too feature-rich and/or
>> >> idiot-proof for this particular use.  =o)
>> >>
>> >>
>> >> However, after some trial and error with [list-sort] I found I am
>> >> unable to sort a list of more than exactly 121 elements without
>> >> freezing Pd -- 122 and up will freeze it.  This is because the main
>> >> loop is not controlled with an [until] -- I think you can see the
>> >> structure of [list-drip] for similar reasoning (the [until] is not
>> >> "needed" logically, but helps with long lists to do it in steps).
>> >> After implementing the [until] loop, I found that [list-sort] is even
>> >> quicker than before, but the efficiency of the [list-shellsort]
>> >> algorithm take over for list sizes >450 -- above that [list-shellsort]
>> >> is substantially quicker (and quicker yet if the variance is low).  It
>> >> beats [list-sort] by half for a list about 1300-1400 elements long or
>> >> so (but not within reason -- it still takes about 2 seconds!).
>> >>
>> >>
>> >> I attached the new [list-sort] and the goofy little diagnostic.
>> >>
>> >> Matt
>> >>
>> >>
>> >>> Date: Tue, 2 Dec 2008 13:59:08 +0100
>> >>> From: Frank Barknecht <fbar at footils.org>
>> >>> Subject: Re: [PD] list-sort
>> >>> To: pd-list at iem.at
>> >>> Message-ID: <20081202125908.GJ18987 at fliwatut.scifi>
>> >>> Content-Type: text/plain; charset="us-ascii"
>> >>>
>> >>> Hallo,
>> >>>
>> >>> oh, and I also now committed two more abstractions that Matt Barber
>> >>> sent me offlist, of which one is a sorting abstraction as well. Matt's
>> >>> [list-shellsort] uses the Shell sorting algorithm:
>> >>> http://en.wikipedia.org/wiki/Shell_sort which generally is a bit
>> >>> faster than insertion sort, but I didn't benchmark the two Pd
>> >>> implementations (the speed in Pd of course also depends on how much
>> >>> element shuffling and list-dripping is needed)
>> >>>
>> >>> Anyway, currently list-shellsort only does ascending sorting, so I
>> >>> just decided to include both Michal's list-sort, which probably is
>> >>> easier to understand, and Matt's list-shellsort in the current SVN's
>> >>> [list]-abs collection. Choose your poison. ;)
>> >>>
>> >>> Ciao
>> >>> --
>> >>> Frank
>> >>>
>> >>> Michal Seta hat gesagt: // Michal Seta wrote:
>> >>>
>> >>>> Hi all,
>> >>>>
>> >>>> It is amazing how we take things for granted.  Most programming
>> >>>> languages provide some sort of list sorting function/method.
>> >>>> Surprisingly (or not) pd does not (or my search skills are null, or I
>> >>>> am not bleeding edge enough).  I needed a solution that works with a
>> >>>> vanilla pd.
>> >>>>
>> >>>> I was almost going to do the academia move and announce a pd exam,
>> >>>> and
>> >>>> have little pd-bees come up with a solution but I needed it *now*
>> >>>> else
>> >>>> I would not sleep or have terrible nightmares.  So here it is.  Thank
>> >>>> heavens (but give your offerings to fbar's footils shrine) for
>> >>>> list-abs.
>> >>>>
>> >>>> Busy pd-bees, should you care to improve on my solution, please be my
>> >>>> guest, I am sure there are better ways of accomplishing this trivial
>> >>>> task.  In any case, go forth and sort the world around (or within)
>> >>>> you.
>> >>>>
>> >>>> ./MiS
>> >>
>> >
>
>
>> << list-shellsort-tab.pd >>
>
>
>> _______________________________________________
>> Pd-list at iem.at mailing list
>> UNSUBSCRIBE and account-management ->
>> http://lists.puredata.info/listinfo/pd-list
>
>
>