So instead, actually implement it in an array and sort it in place! Very fast.
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 >> >
#N canvas 917 330 453 562 10; #X obj 26 -25 inlet; #X obj 45 379 outlet; #N canvas 416 392 593 257 \$0-gap-loop 0; #X obj 137 66 / 2; #X obj 137 89 int; #X obj 34 122 until; #X obj 34 49 t b f; #X obj 189 105 sel 0; #X obj 137 142 t f f; #X obj 59 159 f; #X obj 34 26 inlet; #X obj 59 213 outlet; #X text 91 22 Start with a gap of floor(n/2) \, continue to decrease gap by powers of 1/2.; #X obj 59 181 t f f; #X text 118 182 <== order doesn't matter here \, but we force each iteration of this loop to finish before going on to the next... this seems to save time.; #X connect 0 0 1 0; #X connect 1 0 5 0; #X connect 2 0 6 0; #X connect 3 0 2 0; #X connect 3 1 0 0; #X connect 4 0 2 1; #X connect 5 0 6 1; #X connect 5 1 4 0; #X connect 6 0 10 0; #X connect 7 0 3 0; #X connect 10 0 8 0; #X connect 10 1 0 0; #X restore 104 161 pd \$0-gap-loop; #N canvas 584 66 594 302 \$0-increment-loop 0; #X obj 41 56 inlet; #X obj 222 111 inlet; #X obj 41 113 until; #X obj 41 83 t b f; #X obj 100 130 f; #X obj 150 132 + 1; #X obj 100 182 moses; #X obj 168 199 t b; #X obj 100 218 outlet; #X obj 100 159 t f f; #X text 41 16 Iterate over all the pairs whose indices are related by the current gap size.; #X text 173 155 <== order doesn't matter here \, but we force each iteration of this loop to finish before going on to the next... this seems to save time.; #X obj 168 222 s \$0-stop-inc-loop; #X obj 86 83 r \$0-stop-inc-loop; #X connect 0 0 3 0; #X connect 1 0 6 1; #X connect 2 0 4 0; #X connect 3 0 2 0; #X connect 3 1 4 1; #X connect 4 0 9 0; #X connect 5 0 4 1; #X connect 6 0 8 0; #X connect 6 1 7 0; #X connect 7 0 12 0; #X connect 9 0 6 0; #X connect 9 1 5 0; #X connect 13 0 2 1; #X restore 104 206 pd \$0-increment-loop; #X obj 104 136 t f f; #X obj 104 184 t f f; #N canvas 183 142 507 640 \$0-test-swap-loop 0; #X obj 82 90 inlet; #X obj 299 96 inlet; #X obj 82 113 -; #X obj 284 174 +; #X obj 82 479 >; #X obj 82 503 sel 0 1; #X obj 257 529 f; #X obj 290 529 f; #X obj 82 178 until; #X obj 174 241 moses 0; #X obj 174 216 f; #X obj 207 216 -; #X obj 82 134 t b f; #X obj 227 484 t b b; #X obj 213 263 s \$0-idx; #X obj 311 135 r \$0-idx; #X obj 272 472 r \$0-idx; #X obj 97 335 r \$0-idx; #X obj 284 195 s \$0-idx+gap; #X obj 305 496 r \$0-idx+gap; #X obj 220 322 r \$0-idx+gap; #N canvas 468 185 584 529 swap? 0; #X obj 40 52 inlet; #X obj 153 52 inlet; #X obj 361 50 inlet; #X obj 40 272 spigot 1; #X obj 256 272 spigot; #X obj 361 224 unpack 0 0; #X msg 361 178 1 0; #X msg 412 196 0 1; #X obj 463 93 select 0; #X obj 361 71 select asc desc; #X obj 40 437 outlet; #X obj 153 437 outlet; #X obj 256 300 swap; #X obj 153 271 spigot 1; #X obj 317 273 spigot; #X connect 0 0 3 0; #X connect 0 0 4 0; #X connect 1 0 13 0; #X connect 1 0 14 0; #X connect 2 0 9 0; #X connect 3 0 10 0; #X connect 4 0 12 0; #X connect 5 0 3 1; #X connect 5 0 13 1; #X connect 5 1 4 1; #X connect 5 1 14 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 connect 12 0 10 0; #X connect 12 1 11 0; #X connect 13 0 11 0; #X connect 14 0 12 1; #X restore 82 456 pd swap?; #X obj 160 439 r \$0-direction; #X obj 82 572 s \$0-stop-test-loop; #X obj 174 285 s \$0-stop-test-loop; #X obj 130 136 r \$0-stop-test-loop; #X obj 82 547 t b; #X obj 174 262 t b; #X text 74 13 If current pair is out of order \, swap them. Then \, if after the swap the values at the left index and left minus gap are out of order \, swap those too. Keep going backwards through the list in the same manner until a swap no longer needs to be made \, or until left minus gap is smaller than zero.; #X text 336 94 <== gap; #X text 118 90 <== increment; #N canvas 677 165 450 300 \$0-tabswap 0; #X obj 164 23 inlet; #X obj 236 47 inlet; #X obj 250 120 f; #X obj 265 97 tabread \$0-table; #X obj 69 120 tabread \$0-table; #X obj 93 204 tabwrite \$0-table; #X obj 164 46 t b f f; #X connect 0 0 6 0; #X connect 1 0 3 0; #X connect 1 0 5 1; #X connect 2 0 5 0; #X connect 3 0 2 1; #X connect 4 0 5 0; #X connect 6 0 2 0; #X connect 6 1 5 1; #X connect 6 2 4 0; #X restore 257 555 pd \$0-tabswap; #X obj 82 358 f; #X obj 205 356 f; #X obj 205 382 tabread \$0-table; #X obj 82 382 tabread \$0-table; #X obj 82 199 t b b b; #X connect 0 0 2 0; #X connect 1 0 2 1; #X connect 1 0 3 1; #X connect 1 0 11 1; #X connect 2 0 12 0; #X connect 3 0 18 0; #X connect 4 0 5 0; #X connect 5 0 26 0; #X connect 5 1 13 0; #X connect 5 2 26 0; #X connect 6 0 31 0; #X connect 7 0 31 1; #X connect 8 0 36 0; #X connect 9 0 27 0; #X connect 9 1 14 0; #X connect 10 0 11 0; #X connect 10 0 9 0; #X connect 11 0 10 1; #X connect 12 0 8 0; #X connect 12 1 10 1; #X connect 13 0 6 0; #X connect 13 1 7 0; #X connect 15 0 3 0; #X connect 16 0 6 1; #X connect 17 0 32 1; #X connect 19 0 7 1; #X connect 20 0 33 1; #X connect 21 0 4 0; #X connect 21 1 4 1; #X connect 22 0 21 2; #X connect 25 0 8 1; #X connect 26 0 23 0; #X connect 27 0 24 0; #X connect 32 0 35 0; #X connect 33 0 34 0; #X connect 34 0 21 1; #X connect 35 0 21 0; #X connect 36 0 32 0; #X connect 36 1 33 0; #X connect 36 2 10 0; #X restore 104 232 pd \$0-test-swap-loop; #X obj 65 114 sel 0 1; #X obj 26 0 list-filter; #N canvas 0 0 677 293 \$0-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 115 0 pd \$0-checknum; #X text 46 472 2008 Matt Barber; #X obj 311 133 loadbang; #X obj 246 45 inlet; #X obj 246 194 list append \$1; #X obj 246 164 t b a; #X obj 246 222 s \$0-direction; #N canvas 450 410 370 266 \$0-table 0; #X obj 80 75 list-len; #X msg 176 137 resize \$1; #X obj 60 154 s \$0-table; #X obj 41 24 inlet; #X obj 31 178 outlet; #X obj 139 24 table \$0-table; #X obj 60 118 list prepend 0; #X obj 148 92 t f f; #X obj 41 46 t b a a; #X obj 31 109 f; #X connect 0 0 7 0; #X connect 1 0 2 0; #X connect 3 0 8 0; #X connect 6 0 2 0; #X connect 7 0 9 1; #X connect 7 1 1 0; #X connect 8 0 9 0; #X connect 8 1 6 0; #X connect 8 2 0 0; #X connect 9 0 4 0; #X restore 65 49 pd \$0-table; #X obj 45 352 list-tabdump; #X obj 45 306 list prepend \$0-table; #X obj 45 280 f; #X obj 127 86 s \$0-length; #X obj 60 258 r \$0-length; #X obj 26 22 t b b a; #X obj 45 330 list append 0; #X obj 26 434 s \$0-table; #X obj 65 69 t f f; #X text 163 403 <== free the table; #X msg 26 404 resize 1 \, 0 0; #X connect 0 0 8 0; #X connect 2 0 5 0; #X connect 3 0 6 0; #X connect 4 0 2 0; #X connect 4 1 3 1; #X connect 5 0 3 0; #X connect 5 1 6 1; #X connect 7 2 4 0; #X connect 8 0 22 0; #X connect 8 1 9 0; #X connect 9 0 8 1; #X connect 11 0 13 0; #X connect 12 0 14 0; #X connect 13 0 15 0; #X connect 14 0 13 0; #X connect 14 1 13 1; #X connect 16 0 25 0; #X connect 17 0 1 0; #X connect 18 0 23 0; #X connect 19 0 18 0; #X connect 21 0 19 1; #X connect 22 0 27 0; #X connect 22 1 19 0; #X connect 22 2 16 0; #X connect 23 0 17 0; #X connect 25 0 7 0; #X connect 25 1 20 0; #X connect 27 0 24 0;
_______________________________________________ [email protected] mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
