[PD] list-sort

[Matt Barber]

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
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: list-sort-compare.pd
URL: <http://lists.puredata.info/pipermail/pd-list/attachments/20081202/98bacb97/attachment.asc>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: list-sort.pd
URL: <http://lists.puredata.info/pipermail/pd-list/attachments/20081202/98bacb97/attachment.txt>