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