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
#N canvas 69 275 590 319 10; #X obj 327 163 list-shellsort; #X obj 395 95 bng 15 250 50 0 empty empty empty 17 7 0 10 -262144 -1 -1; #X obj 296 210 realtime; #X floatatom 304 240 0 0 0 0 - - -; #X obj 257 139 t b b b; #X obj 159 71 bng 15 250 50 0 empty empty empty 17 7 0 10 -262144 -1 -1; #X obj 60 186 realtime; #X floatatom 68 216 0 0 0 0 - - -; #X obj 21 115 t b b b; #X obj 91 139 list-sort; #X floatatom 197 81 0 0 0 0 - - -; #X floatatom 260 82 5 0 0 0 - - -; #X floatatom 435 99 0 0 0 0 - - -; #X floatatom 496 103 5 0 0 0 - - -; #X obj 91 115 list-random 20000 100; #X obj 327 139 list-random 20000 100; #X connect 1 0 4 0; #X connect 2 0 3 0; #X connect 4 0 2 1; #X connect 4 1 15 0; #X connect 4 2 2 0; #X connect 5 0 8 0; #X connect 6 0 7 0; #X connect 8 0 6 1; #X connect 8 1 14 0; #X connect 8 2 6 0; #X connect 10 0 14 1; #X connect 11 0 14 2; #X connect 12 0 15 1; #X connect 13 0 15 2; #X connect 14 0 9 0; #X connect 15 0 0 0;
#N canvas 422 43 782 540 10; #X obj 169 310 list split 1; #X obj 97 266 list-len; #X obj 203 331 list split 1; #X obj 169 373 list append; #X obj 59 359 list; #X obj 97 287 > 0; #X obj 190 472 outlet; #X obj 203 49 inlet; #X text 55 513 2008 Michal Seta; #X obj 273 393 list prepend; #X obj 190 450 list append; #X obj 492 140 loadbang; #X obj 427 52 inlet; #N canvas 0 0 552 424 mux 0; #X obj 40 52 inlet; #X obj 153 52 inlet; #X obj 255 49 inlet; #X obj 40 266 spigot 1; #X obj 153 266 spigot; #X obj 255 223 unpack 0 0; #X msg 255 177 1 0; #X msg 306 195 0 1; #X obj 357 92 select 0; #X obj 255 70 select asc desc; #X obj 40 317 outlet; #X connect 0 0 3 0; #X connect 1 0 4 0; #X connect 2 0 9 0; #X connect 3 0 10 0; #X connect 4 0 10 0; #X connect 5 0 3 1; #X connect 5 1 4 1; #X connect 6 0 5 0; #X connect 7 0 5 0; #X connect 8 0 6 0; #X connect 8 1 7 0; #X connect 9 0 6 0; #X connect 9 1 7 0; #X connect 9 2 8 0; #X restore 240 252 pd mux; #X obj 427 201 list append \$1; #X obj 427 171 t b a; #X obj 370 392 t a; #X text 332 283 [list-sort] sort an incoming list of numerical values in an ascending or descending order; #N canvas 122 188 842 735 minmaxpos 0; #X obj 128 97 list-drip; #X obj 128 120 route float; #X obj 159 256 f; #X obj 106 664 outlet; #X obj 165 639 f; #X obj 165 666 outlet; #X obj 106 575 t b b; #X obj 106 10 inlet; #X obj 106 636 f; #N canvas 0 0 450 300 once 0; #X obj 110 75 inlet; #X obj 105 187 spigot 1; #X obj 110 104 t b f; #X msg 125 151 0; #X msg 165 99 1; #X obj 165 63 inlet; #X obj 102 219 outlet; #X connect 0 0 2 0; #X connect 1 0 6 0; #X connect 2 0 3 0; #X connect 2 1 1 0; #X connect 3 0 1 1; #X connect 4 0 1 1; #X connect 5 0 4 0; #X restore 262 183 pd once; #X obj 275 258 f; #X obj 244 257 max; #X obj 128 256 min; #X text 323 183 prime [min] and [max] with first item once; #N canvas 0 0 450 300 count 0; #X obj 120 148 f 0; #X obj 148 149 + 1; #X obj 163 100 0; #X obj 117 24 inlet; #X obj 119 176 outlet; #X obj 181 25 inlet; #X obj 114 47 b; #X connect 0 0 1 0; #X connect 0 0 4 0; #X connect 1 0 0 1; #X connect 2 0 0 1; #X connect 3 0 6 0; #X connect 5 0 2 0; #X connect 6 0 0 0; #X restore 168 371 pd count; #X obj 128 470 change; #X obj 244 472 change; #X obj 128 527 f; #X obj 244 525 f; #X obj 128 495 b; #X obj 244 496 b; #X msg 429 356 set \$1; #X msg 601 357 0; #X obj 106 30 t b a b b; #X obj 128 150 t a a b a; #X text 637 358 reset positions; #X text 483 356 set change; #X text 302 475 if min or max changes \, store the new positions.; #X text 227 24 output positions of min and max float in a list (zero-based) ; #X connect 0 0 1 0; #X connect 1 0 24 0; #X connect 2 0 12 1; #X connect 4 0 5 0; #X connect 6 0 8 0; #X connect 6 1 4 0; #X connect 7 0 23 0; #X connect 8 0 3 0; #X connect 9 0 11 1; #X connect 9 0 12 1; #X connect 9 0 21 0; #X connect 9 0 22 0; #X connect 10 0 11 1; #X connect 11 0 10 0; #X connect 11 0 16 0; #X connect 12 0 2 0; #X connect 12 0 15 0; #X connect 14 0 18 1; #X connect 14 0 17 1; #X connect 15 0 19 0; #X connect 16 0 20 0; #X connect 17 0 8 1; #X connect 18 0 4 1; #X connect 19 0 17 0; #X connect 20 0 18 0; #X connect 21 0 16 0; #X connect 21 0 15 0; #X connect 22 0 4 1; #X connect 22 0 8 1; #X connect 23 0 6 0; #X connect 23 1 0 0; #X connect 23 2 14 1; #X connect 23 3 9 1; #X connect 24 0 12 0; #X connect 24 1 11 0; #X connect 24 2 14 0; #X connect 24 3 9 0; #X restore 240 215 pd minmaxpos; #X obj 203 86 list-filter; #N canvas 0 0 677 293 checknum 0; #X obj 131 95 route float; #X msg 131 116 1; #X obj 205 149 print; #X msg 205 119 list-sort: Warning: dropped a non-number from list; #X obj 131 70 inlet; #X obj 131 149 outlet; #X connect 0 0 1 0; #X connect 0 1 3 0; #X connect 1 0 5 0; #X connect 3 0 2 0; #X connect 4 0 0 0; #X restore 292 86 pd checknum; #X obj 83 200 until; #X obj 155 407 t b b; #X obj 193 175 t a a a; #X obj 203 120 t b a b; #X obj 97 308 sel 0; #X connect 0 0 3 0; #X connect 0 1 2 0; #X connect 1 0 5 0; #X connect 2 0 9 0; #X connect 2 1 3 1; #X connect 3 0 4 1; #X connect 4 0 23 0; #X connect 5 0 25 0; #X connect 7 0 19 0; #X connect 9 0 10 1; #X connect 9 0 16 0; #X connect 10 0 6 0; #X connect 11 0 14 0; #X connect 12 0 15 0; #X connect 13 0 0 1; #X connect 14 0 13 2; #X connect 15 0 14 0; #X connect 15 1 14 1; #X connect 16 0 9 1; #X connect 18 0 13 0; #X connect 18 1 13 1; #X connect 19 0 24 0; #X connect 19 1 20 0; #X connect 20 0 19 1; #X connect 21 0 4 0; #X connect 22 0 10 0; #X connect 22 1 21 1; #X connect 23 0 1 0; #X connect 23 1 0 0; #X connect 23 2 18 0; #X connect 24 0 21 0; #X connect 24 1 23 0; #X connect 24 2 9 1; #X connect 25 0 22 0;
_______________________________________________ [email protected] mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
