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
