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 <[EMAIL PROTECTED]> 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 <[EMAIL PROTECTED]> 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 <[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 >> >> >> > > > >> << list-shellsort-tab.pd >> > > >> _______________________________________________ >> [email protected] mailing list >> UNSUBSCRIBE and account-management -> >> http://lists.puredata.info/listinfo/pd-list > > > _______________________________________________ [email protected] mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
