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 <[EMAIL PROTECTED]> 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 <[EMAIL PROTECTED]> >> Subject: Re: [PD] list-sort >> To: [email protected] >> Message-ID: <[EMAIL PROTECTED]> >> 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 > _______________________________________________ [email protected] mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
