[PD] Vanilla object for "sort"

[Jonathan Wilkes]

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