-----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