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@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@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@footils.org Subject: Re: [PD] list-sort To: pd-list@iem.at Message-ID: 20081202125908.GJ18987@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@iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list