[PD] Vanilla object for "sort"

[Jack]

-----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 at 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-----
-------------- next part --------------
A non-text attachment was scrubbed...
Name: vanilla-sort-benchmark.pd
Type: application/puredata
Size: 2130 bytes
Desc: not available
URL: <http://lists.puredata.info/pipermail/pd-list/attachments/20150511/35c12a77/attachment-0002.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: vanilla-sort.pd
Type: application/puredata
Size: 1167 bytes
Desc: not available
URL: <http://lists.puredata.info/pipermail/pd-list/attachments/20150511/35c12a77/attachment-0003.bin>