[PD] array-abs

Sun Oct 4 22:12:20 CEST 2015

I think matju wrote the [list-drip] algorithm partly to show the difficultyof using recursion in Pd.  That the actual author of Pd's messagingsystem refrains from using recursion to solve the same problem addsweight 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/20151004/300462f2/attachment.html>