-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Just make this abstraction (sorting number in one direction). It works with array objects. Seems promising compare to list-sort. ++
Jack Le 10/05/2015 03:21, Jonathan Wilkes via Pd-list a écrit : > On 05/09/2015 05:54 PM, Miller Puckette wrote: >> On Sat, May 09, 2015 at 05:30:14PM -0400, Jonathan Wilkes via >> Pd-list wrote: >>> On 05/09/2015 11:29 AM, Frank Barknecht wrote: >>>> Hi, >>>> >>>> the list-sort.pd abstraction in the [list]-abs is Pd vanilla >>>> and uses data structures to do the sorting. The actual >>>> sorting is fast, but first the list is copied into a data >>>> structure [struct f float x] and into a subpatch, which takes >>>> a moment. Then you just sort the subpatch with the message >>>> "sort" to it. >>>> >>>> In my benchmarks four yers ago it was faster than the other >>>> sorting algorithms available at the time, which are also >>>> included in the collection. >>> That's probably because the other sorting algorithms spend a >>> significant amount of time copying lists. >>> >>> To get anything close to the speed of the canvas "sort" method >>> you'd have to have an object that manipulates an incoming list >>> in place. However, that'd have serious side effects, which is >>> why I suppose no objects do that kind of thing. >>> >>> -Jonathan >>> >> But I believe Frank's method (which is, by the way, ingenious!) >> also requires copying the objects to be sorted. So I think one >> could do just as well some other way. > > I haven't looked, but I'd guess that: a) converting the list to > scalars requires either no list copying operations, or a single > list copy operation b) converting sorted scalars back to a list > uses the "add2" method > > So even though there may be copying to convert the data, the number > of list copy operations isn't going to grow with the size of the > list. > > My point is that if you try to devise abstraction to sort lists > using Vanilla objects (without relying on canvas' "sort" method), > you will most likely end up needing to do a list copy operation on > each iteration of the algorithm. And that will be substantially > slower than doing it in C. > > I might be wrong about that, but the only non-trivial > list-abstraction I've seen that doesn't copy lists is list-drip. > And it's so difficult to reason about its data-flow that I highly > doubt anyone has used it as a model for solving more difficult > problems. > >> >> Here are three things I could imagine doing for some future >> release: >> >> a [list sort] built-in that outputs two lists, one the sorted >> numbers or symbols, and the other giving the indices of the items >> in order >> >> an [array sort] object - I guess that should write its outputs >> into two other arrays, yuck >> >> a [text sort] object that would act like unix "sort": just sort >> all the lines of the text object. >> >> I don't know which of these would be the most useful. The only >> use case that I've run into personally is my desire to do triage >> on sigmund~ outputs to find, say, the peaks best fitting a >> user-defied criterion about freqency and amplitude (example: >> Fletcher-Munson loudness; or other example: the peaks that best >> continue a collection of pre-existing tracks). For that, the >> [list sort] solution would be best I think. > > I don't know which of those would be most useful, either. > > But I think there's a general issue with dataflow languages to be > teased out here. There was also a thread on the list for Noflo (a > flo-based programming language that can run in a browser) about the > difficulties of implementing quicksort. > > I can't quite put my finger on what the issue is-- I don't think > it's message-passing overhead, because Pd gets around that to some > extent by passing references under the hood. I believe it has more > to do with those times where I get to the bottom of an object chain > and think, "Hm, I really want some of that data from the top of > the chain, but I really don't want to draw yet another line and box > just to prepare a copy of it." > > I think sometimes I just want a single vertical tube, with > syringes stuck in the sides that mutate the data in order from top > to bottom. So the data flowing through the tube would be like a > t_binbuf onto which I can append and/or remove atoms (or change > their values). > > So if you get Luigi going down the tube, you get Luigi coming out > of the tube. (Though he may look very different by that point. :) > > -Jonathan > >> >> cheers Miller > > > _______________________________________________ > Pd-list@lists.iem.at mailing list UNSUBSCRIBE and > account-management -> http://lists.puredata.info/listinfo/pd-list -----BEGIN PGP SIGNATURE----- Version: GnuPG v1 iQEcBAEBAgAGBQJVUKhjAAoJEOuluecjw8GUglQH/iXi1Gm9S/LVuo+o11u1zXIz HlWS6x+TW3ei2PhD/KLDwLKgfzD4NjT62goM2NFWW4FV1XdCrne758ht5/N40Rg9 8EZBF3GzIX4FzFuqNA+pKv1GsUfHxSKg4bDCQ0sIiAVMGoHOZgMjdWY+57Oj2Ibi DdzUp2W+aEMFVE4js6GEXNm+aLIiPa6eaf9RE9v5aJY/N3JwmzYlrUHotBO359kt PAlNxtKzxWGuOLEAVpB9gyXO1CtrBApqW1VNrlloo1A8FIHwnpnSrBc/PR33isAN Pjl/yl+Eo/XS8btjIcnmBsMpXhSyCrQRRzFYNgZNe2MFkgD3UkwZjQ4HJzylr18= =e1IK -----END PGP SIGNATURE-----
vanilla-sort-benchmark.pd
Description: application/puredata
vanilla-sort.pd
Description: application/puredata
_______________________________________________ Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
