[PD] array-abs

Mon Oct 5 17:26:55 CEST 2015

When I say "left-side" I'm talking about the left side of the list itself,
which is sent for processing by the [>> 1]-[list split] on the right side
of the patch. Depth-first ensures that all of the left parts of the list
chunks will all be processed before the corresponding right chunks.

Again, it may be easier to look at [list-rdrip].

On Mon, Oct 5, 2015 at 11:08 AM, Jonathan Wilkes <jancsika at yahoo.com> wrote:

> > Depth-first ensures that all of the left-side processing will happen
> before any of the right side.
>
> Not sure I understand that.
> The right-side [>> 1]--[list split] will recurse and end up sending the
> first element to the outlet before [trigger] ever sends anything
> to the left side.  "Depth-first" applies equally to recursive depth.  You
> keep doing somersaults until you have no more somersaults
> to do.
>
> As for C, recursion is still difficult but it's also equally powerful.
> However, if everything except the first argument got borked when
> you tried to do recursive functions I doubt anyone would be using it. :)
>
> -Jonathan
>
>
>
>
>
> On Monday, October 5, 2015 9:57 AM, Matt Barber <brbrofsvl at gmail.com>
> wrote:
>
>
> Recursion can be difficult to understand even in c or a functional
> programming language. Sticking a [print] in various stages should help
> visualization.
>  Here's how I'd describe it:
> Input list. Split it in half – [>> 1]-[list split] – and send the left
> side for processing first and the right side last. Depth-first ensures that
> all of the left-side processing will happen before any of the right side.
> Keep splitting and sending left sides until a list arrives whose length is
> less than 2 – [list split 2] at the top. If it is, it's either an empty
> list or a singleton, so it doesn't need to be processed further – [spigot]
> – and we can send it out (filtering out any empty lists). Then the right
> side of the most recent list to be sent in for processing (let's name that
> list Greg) is sent for processing, and when Greg's right side has all been
> split and output, then the right side of Greg's parent list can be sent.
> As with most binary procedures you could graph the process as a simple
> binary tree where the root node represents the initial list and daughter
> nodes are the left and right halves of lists that have been split.
> Traversing the tree means that when you get to a node you haven't visited
> yet, always take the left side of the fork first to get to the next level
> down. When you return to that node you can then take the right side of the
> fork. Once you've taken both paths all the way to the branches you can go
> back up a level. Continue this until you've taken both branches of the root
> node.
>
> The [>> 1] isn't just to avoid a stack overflow – splitting the lists as
> close as possible to half also happens to be the fastest way of going about
> the recursion. It's one of the reasons quick sort is still one of the
> fastest available sorts.
> 
> On Oct 5, 2015 3:16 AM, "Jonathan Wilkes" <jancsika at yahoo.com> wrote:
>
> Yes that's true about iterative approaches and dataflow in general.
>
> What gets me about [list-drip] is the necessity of the [>> 1] to prevent
> stack overflow.  So even if you can follow the order of operations with
> recursion through that object chain, you have to also keep track of
> the order in which those two branches interact during the recursion.
>
> I can visualize that using a small set of data to the inlet, and taking my
> time.
> But at that point the diagram itself isn't elucidating anything useful
> about
> the flow of data.  For that you'd need some way to animate the flow through
> the wires in greater than zero logical time.  And even then you'd want to
> show
> the actual data associated with each cycle of animation.
>
> -Jonathan
>
>
>
>
> On Monday, October 5, 2015 1:59 AM, Matt Barber <brbrofsvl at gmail.com>
> wrote:
>
>
> Not supporting recursion in a dataflow environment is not a huge problem
> IMO, especially since so many classically recursive problems (binary
> search, quick sort, etc.) can be solved iteratively. The iterative solution
> is almost always going to be clearer in an environment like Pd.
>
> [list-drip] is a decent model for how recursion would have to work --
> [list-rdrip] even more, since it can take advantage of the native
> right-to-left output to reduce the number of objects. Anything solved using
> a divide-and-conquer strategy could even be a bit faster using the stack
> vs. an until loop. A while back I made a kind of clunky iterative quick
> sort; I wonder if it would be possible to throw ranges to partition onto
> Pd's stack without it overflowing ... probably not since there's nothing to
> guarantee that quick sort doesn't run at O(n^2) in the worst case. Binary
> search almost certainly could; I'll do that in the next few days and post
> benchmarks comparing an [until] loop solution with recursion.
>
> On Sun, Oct 4, 2015 at 4:12 PM, Jonathan Wilkes <jancsika at yahoo.com>
> wrote:
>
> I think matju wrote the [list-drip] algorithm partly to show the difficulty
> of using recursion in Pd.  That the actual author of Pd's messaging
> system refrains from using recursion to solve the same problem adds
> weight to that point.
>
> -Jonathan
>
>
>
>
>
> On Sunday, October 4, 2015 3:45 PM, Matt Barber <brbrofsvl at gmail.com>
> wrote:
>
>
> It takes almost a full second to output a list of n=1,000,000 with a
> 100-cycle until on my computer.
>
> On Sun, Oct 4, 2015 at 3:38 PM, Matt Barber <brbrofsvl at gmail.com> wrote:
>
> This is still much slower than [list-drip], and it freezes Pd for me when
> I get up to lists of n=100,000 or so. I think it's because Pd has to copy
> the list to an output every cycle of [until], so when n=10, you're only
> outputting something of size 10 10 times, but that grows by n^2 so when
> it's n=10,000 times 10,000 outputs, it's a lot. 1,000,000 seems impossible
> unless the list decreases in size each cycle, which it does in [list-drip],
> recursively.
>
> On Sun, Oct 4, 2015 at 2:48 PM, Miller Puckette <msp at ucsd.edu> wrote:
>
> Here's a way to serialize a list in (I believe) linear time:
>
> #N canvas 881 291 450 300 10;
> #X msg 136 14 list 3 . 1 4 1 5 9;
> #X obj 83 97 list length;
> #X obj 77 211 list split;
> #X obj 101 186 list;
> #X obj 139 55 t l b l;
> #X obj 83 119 until;
> #X obj 83 141 f;
> #X obj 114 142 + 1;
> #X msg 166 117 0;
> #X obj 83 163 t b f;
> #X obj 117 278 print;
> #X obj 116 250 list split 1;
> #X connect 0 0 4 0;
> #X connect 1 0 5 0;
> #X connect 2 1 11 0;
> #X connect 3 0 2 0;
> #X connect 4 0 1 0;
> #X connect 4 1 8 0;
> #X connect 4 2 3 1;
> #X connect 5 0 6 0;
> #X connect 6 0 7 0;
> #X connect 6 0 9 0;
> #X connect 7 0 6 1;
> #X connect 8 0 6 1;
> #X connect 9 0 3 0;
> #X connect 9 1 2 1;
> #X connect 11 0 10 0;
>
> cheers
> Miller
>
> On Sun, Oct 04, 2015 at 02:27:37PM -0400, Matt Barber wrote:
> > Your [pd drip] does a lot of extra work. It's go basically linear stack
> > performance, and you're recopying the list every loop (an until loop
> would
> > solve this for a little extra cpu time). The secret of [list-drip] is
> that
> > it doesn't recopy the list using the [list] object, and it avoids stack
> > overflows by doing the recursion split at the midpoint of the list and
> only
> > outputting when it's done the binary split down to lists of size 1, which
> > are the elements, or size zero, which are bangs (and which are filtered
> > out).
> >
> > Since it's binary recursion on the list, the stack only grows
> > proportionally to log_2(n), which is about 20 for n=1,000,000. It's still
> > going to be slower than an object written in C that can just iterate over
> > the contents in a single loop, and lists in Pd are slower in general than
> > arrays, so an until loop and tabread over an array is going to be
> quicker.
> > It is much slower for copying though -- an until loop with tabread and
> > tabwrite has way more overhead than an [array get]-[array set] pair.
> >
> >
> > On Sun, Oct 4, 2015 at 1:06 PM, Christof Ressi <christof.ressi at gmx.at>
> > wrote:
> >
> > > Please don't use the previous version of the multi-dimensional
> arrays!!!
> > > First, I forget to get rid of one [drip] object. Second, I discovered
> that
> > > [pd drip] will create a stack overflow if there are more than ca. 300
> > > elements! (Why???) So I replaced it with [list-drip] which works fine.
> > >
> > > So here's the corrected pure vanilla version + a zexy version using
> > > [drip]. I prefer to use the latter one because it's waaaaay faster
> than all
> > > the drip abstractions based on [list split].
> > >
> > > Vanilla:
> https://www.dropbox.com/s/wd0avxtaneqgdic/carray_vanilla.zip?dl=0
> > > Zexy: https://www.dropbox.com/s/ea8kihwbdqhcajr/carray_zexy.zip?dl=0
> > >
> > > Christof
> > >
> > > PS:  I did a benchmark test of iterating through an array of 1 million
> > > elements, using [realtime], and here's what I found on my system:
> > >
> > > [array get] + [drip] --> ca. 6.5-9ms
> > > [until] + [tabread] --> ca. 120-200ms
> > > [array get] + [list-drip] --> ca. 340-400ms
> > >
> > > To me this result was a bit surprising...
> > >
> > > You can test yourself with the attached patch.
> > > *Gesendet:* Sonntag, 04. Oktober 2015 um 17:32 Uhr
> > > *Von:* "Christof Ressi" <christof.ressi at gmx.at>
> > > *An:* "Matt Barber" <brbrofsvl at gmail.com>
> > >
> > > *Cc:* Pd-List <pd-list at lists.iem.at>
> > > *Betreff:* Re: [PD] array-abs
> > > Wow, looks cool!
> > >
> > > Just a few days ago I reworked some of my personal table abstractions,
> > > which also make use of the [array] object. However, some of them
> depend on
> > > zexy externals (I hope I didn't miss any other dependencies). I haven't
> > > shared them yet so the documentation is quite poor (no help files, docs
> > > inside the abstraction) and they look a bit messy. But maybe you can
> get
> > > some inspiration for your library...
> > > https://www.dropbox.com/s/xvj031korqw8guf/ctab-abs.zip?dl=0
> > >
> > > Additionally I've been working on three basic abstractions for
> creating,
> > > setting and reading multi-dimensional arrays of any number of
> dimensions.
> > > They are pure vanilla style and even come with a help file :-D.  (a
> object
> > > for array resizing is yet to be done...)
> > > https://www.dropbox.com/s/6xfgdyt697138e6/carray.zip?dl=0
> > >
> > > Would be cool to hear your opinion on the multi-dimensional array
> stuff!
> > >
> > > Christof
> > >
> > >
> > >
> > >
> > > *Gesendet:* Samstag, 03. Oktober 2015 um 22:32 Uhr
> > > *Von:* "Matt Barber" <brbrofsvl at gmail.com>
> > > *An:* "IOhannes m zmölnig" <zmoelnig at iem.at>
> > > *Cc:* Pd-List <pd-list at lists.iem.at>
> > > *Betreff:* Re: [PD] array-abs
> > > Thanks.
> > >
> > > Yes. Right now I'm just looking to see if these would be useful, if
> > > there's anything awful about the syntax, if they try to do too much or
> are
> > > too fussy, if anyone would want to contribute, etc. When I get them
> > > polished a bit I'll do a regular release on the normal channels (I
> can't
> > > remember if I have access to anything officially Pd related).
> > >
> > > Matt
> > >
> > > On Sat, Oct 3, 2015 at 4:22 PM, IOhannes m zmölnig <zmoelnig at iem.at>
> > > wrote:
> > >>
> > >> hi,
> > >>
> > >> great!
> > >>
> > >> On 10/03/2015 07:36 PM, Matt Barber wrote:
> > >> >
> > >> > https://www.dropbox.com/s/45tk62dpz0z2mqo/array-abs.zip?dl=0
> > >> >
> > >>
> > >> db?
> > >>
> > >> would you like to put those on a version control system of sorts, e.g.
> > >> the puredata svn or some publicly available git repository (e.g.
> github)?
> > >>
> > >> (read as: please let us not go back to the dark ages, where code was
> > >> shared by sending files around by on floppy disks and you never new
> > >> which version was the current one)
> > >>
> > >> fgmards
> > >> IOhannes
> > >>
> > >>
> > >>
> > >> _______________________________________________
> > >> Pd-list at lists.iem.at mailing list
> > >> UNSUBSCRIBE and account-management ->
> > >> http://lists.puredata.info/listinfo/pd-list
> > >>
> > >
> > > _______________________________________________ Pd-list at lists.iem.at
> > > mailing list UNSUBSCRIBE and account-management ->
> > > http://lists.puredata.info/listinfo/pd-list
> > > _______________________________________________ Pd-list at lists.iem.at
> > > mailing list UNSUBSCRIBE and account-management ->
> > > http://lists.puredata.info/listinfo/pd-list
> > >
>
> > _______________________________________________
> > Pd-list at lists.iem.at mailing list
> > UNSUBSCRIBE and account-management ->
> http://lists.puredata.info/listinfo/pd-list
>
>
>
>
> _______________________________________________
> Pd-list at lists.iem.at mailing list
> UNSUBSCRIBE and account-management ->
> http://lists.puredata.info/listinfo/pd-list
>
>
>
>
>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puredata.info/pipermail/pd-list/attachments/20151005/b5045e34/attachment-0001.html>