[PD] array-abs

Mon Oct 5 15:57:37 CEST 2015

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/40c3b572/attachment-0001.html>