<html><body><div style="color:#000; background-color:#fff; font-family:HelveticaNeue, Helvetica Neue, Helvetica, Arial, Lucida Grande, sans-serif;font-size:16px"><div id="yui_3_16_0_1_1443986988909_6611" dir="ltr">I think matju wrote the [list-drip] algorithm partly to show the difficulty</div><div id="yui_3_16_0_1_1443986988909_6669" dir="ltr">of using recursion in Pd. That the actual author of Pd's messaging</div><div id="yui_3_16_0_1_1443986988909_6725" dir="ltr">system refrains from using recursion to solve the same problem adds</div><div id="yui_3_16_0_1_1443986988909_7024" dir="ltr">weight to that point.</div><div id="yui_3_16_0_1_1443986988909_6722" dir="ltr"><br></div><div id="yui_3_16_0_1_1443986988909_6957" dir="ltr">-Jonathan<br></div><div id="yui_3_16_0_1_1443986988909_6497" dir="ltr"><br></div><div id="yui_3_16_0_1_1443986988909_6496" dir="ltr"><br></div><div id="yui_3_16_0_1_1443986988909_6233"><span></span></div> <br><div class="qtdSeparateBR"><br><br></div><div style="display: block;" class="yahoo_quoted"> <div style="font-family: HelveticaNeue, Helvetica Neue, Helvetica, Arial, Lucida Grande, sans-serif; font-size: 16px;"> <div style="font-family: HelveticaNeue, Helvetica Neue, Helvetica, Arial, Lucida Grande, sans-serif; font-size: 16px;"> <div dir="ltr"> <font face="Arial" size="2"> On Sunday, October 4, 2015 3:45 PM, Matt Barber <brbrofsvl@gmail.com> wrote:<br> </font> </div> <br><br> <div class="y_msg_container"><div id="yiv7369224518"><div><div dir="ltr"><div class="yiv7369224518gmail_default" style="font-family:verdana, sans-serif;">It takes almost a full second to output a list of n=1,000,000 with a 100-cycle until on my computer.</div></div><div class="yiv7369224518yqt2790716660" id="yiv7369224518yqt92863"><div class="yiv7369224518gmail_extra"><br clear="none"><div class="yiv7369224518gmail_quote">On Sun, Oct 4, 2015 at 3:38 PM, Matt Barber <span dir="ltr"><<a rel="nofollow" shape="rect" ymailto="mailto:brbrofsvl@gmail.com" target="_blank" href="mailto:brbrofsvl@gmail.com">brbrofsvl@gmail.com</a>></span> wrote:<br clear="none"><blockquote class="yiv7369224518gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div dir="ltr"><div class="yiv7369224518gmail_default" style="font-family:verdana, sans-serif;">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.</div></div><div class="yiv7369224518HOEnZb"><div class="yiv7369224518h5"><div class="yiv7369224518gmail_extra"><br clear="none"><div class="yiv7369224518gmail_quote">On Sun, Oct 4, 2015 at 2:48 PM, Miller Puckette <span dir="ltr"><<a rel="nofollow" shape="rect" ymailto="mailto:msp@ucsd.edu" target="_blank" href="mailto:msp@ucsd.edu">msp@ucsd.edu</a>></span> wrote:<br clear="none"><blockquote class="yiv7369224518gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">Here's a way to serialize a list in (I believe) linear time:<br clear="none">
<br clear="none">
#N canvas 881 291 450 300 10;<br clear="none">
#X msg 136 14 list 3 . 1 4 1 5 9;<br clear="none">
#X obj 83 97 list length;<br clear="none">
#X obj 77 211 list split;<br clear="none">
#X obj 101 186 list;<br clear="none">
#X obj 139 55 t l b l;<br clear="none">
#X obj 83 119 until;<br clear="none">
#X obj 83 141 f;<br clear="none">
#X obj 114 142 + 1;<br clear="none">
#X msg 166 117 0;<br clear="none">
#X obj 83 163 t b f;<br clear="none">
#X obj 117 278 print;<br clear="none">
#X obj 116 250 list split 1;<br clear="none">
#X connect 0 0 4 0;<br clear="none">
#X connect 1 0 5 0;<br clear="none">
#X connect 2 1 11 0;<br clear="none">
#X connect 3 0 2 0;<br clear="none">
#X connect 4 0 1 0;<br clear="none">
#X connect 4 1 8 0;<br clear="none">
#X connect 4 2 3 1;<br clear="none">
#X connect 5 0 6 0;<br clear="none">
#X connect 6 0 7 0;<br clear="none">
#X connect 6 0 9 0;<br clear="none">
#X connect 7 0 6 1;<br clear="none">
#X connect 8 0 6 1;<br clear="none">
#X connect 9 0 3 0;<br clear="none">
#X connect 9 1 2 1;<br clear="none">
#X connect 11 0 10 0;<br clear="none">
<br clear="none">
cheers<br clear="none">
Miller<br clear="none">
<div><div><br clear="none">
On Sun, Oct 04, 2015 at 02:27:37PM -0400, Matt Barber wrote:<br clear="none">
> Your [pd drip] does a lot of extra work. It's go basically linear stack<br clear="none">
> performance, and you're recopying the list every loop (an until loop would<br clear="none">
> solve this for a little extra cpu time). The secret of [list-drip] is that<br clear="none">
> it doesn't recopy the list using the [list] object, and it avoids stack<br clear="none">
> overflows by doing the recursion split at the midpoint of the list and only<br clear="none">
> outputting when it's done the binary split down to lists of size 1, which<br clear="none">
> are the elements, or size zero, which are bangs (and which are filtered<br clear="none">
> out).<br clear="none">
><br clear="none">
> Since it's binary recursion on the list, the stack only grows<br clear="none">
> proportionally to log_2(n), which is about 20 for n=1,000,000. It's still<br clear="none">
> going to be slower than an object written in C that can just iterate over<br clear="none">
> the contents in a single loop, and lists in Pd are slower in general than<br clear="none">
> arrays, so an until loop and tabread over an array is going to be quicker.<br clear="none">
> It is much slower for copying though -- an until loop with tabread and<br clear="none">
> tabwrite has way more overhead than an [array get]-[array set] pair.<br clear="none">
><br clear="none">
><br clear="none">
> On Sun, Oct 4, 2015 at 1:06 PM, Christof Ressi <<a rel="nofollow" shape="rect" ymailto="mailto:christof.ressi@gmx.at" target="_blank" href="mailto:christof.ressi@gmx.at">christof.ressi@gmx.at</a>><br clear="none">
> wrote:<br clear="none">
><br clear="none">
> > Please don't use the previous version of the multi-dimensional arrays!!!<br clear="none">
> > First, I forget to get rid of one [drip] object. Second, I discovered that<br clear="none">
> > [pd drip] will create a stack overflow if there are more than ca. 300<br clear="none">
> > elements! (Why???) So I replaced it with [list-drip] which works fine.<br clear="none">
> ><br clear="none">
> > So here's the corrected pure vanilla version + a zexy version using<br clear="none">
> > [drip]. I prefer to use the latter one because it's waaaaay faster than all<br clear="none">
> > the drip abstractions based on [list split].<br clear="none">
> ><br clear="none">
> > Vanilla: <a rel="nofollow" shape="rect" target="_blank" href="https://www.dropbox.com/s/wd0avxtaneqgdic/carray_vanilla.zip?dl=0">https://www.dropbox.com/s/wd0avxtaneqgdic/carray_vanilla.zip?dl=0</a><br clear="none">
> > Zexy: <a rel="nofollow" shape="rect" target="_blank" href="https://www.dropbox.com/s/ea8kihwbdqhcajr/carray_zexy.zip?dl=0">https://www.dropbox.com/s/ea8kihwbdqhcajr/carray_zexy.zip?dl=0</a><br clear="none">
> ><br clear="none">
> > Christof<br clear="none">
> ><br clear="none">
> > PS: I did a benchmark test of iterating through an array of 1 million<br clear="none">
> > elements, using [realtime], and here's what I found on my system:<br clear="none">
> ><br clear="none">
> > [array get] + [drip] --> ca. 6.5-9ms<br clear="none">
> > [until] + [tabread] --> ca. 120-200ms<br clear="none">
> > [array get] + [list-drip] --> ca. 340-400ms<br clear="none">
> ><br clear="none">
> > To me this result was a bit surprising...<br clear="none">
> ><br clear="none">
> > You can test yourself with the attached patch.<br clear="none">
</div></div>> > *Gesendet:* Sonntag, 04. Oktober 2015 um 17:32 Uhr<br clear="none">
> > *Von:* "Christof Ressi" <<a rel="nofollow" shape="rect" ymailto="mailto:christof.ressi@gmx.at" target="_blank" href="mailto:christof.ressi@gmx.at">christof.ressi@gmx.at</a>><br clear="none">
> > *An:* "Matt Barber" <<a rel="nofollow" shape="rect" ymailto="mailto:brbrofsvl@gmail.com" target="_blank" href="mailto:brbrofsvl@gmail.com">brbrofsvl@gmail.com</a>><br clear="none">
> ><br clear="none">
> > *Cc:* Pd-List <<a rel="nofollow" shape="rect" ymailto="mailto:pd-list@lists.iem.at" target="_blank" href="mailto:pd-list@lists.iem.at">pd-list@lists.iem.at</a>><br clear="none">
> > *Betreff:* Re: [PD] array-abs<br clear="none">
<span>> > Wow, looks cool!<br clear="none">
> ><br clear="none">
> > Just a few days ago I reworked some of my personal table abstractions,<br clear="none">
> > which also make use of the [array] object. However, some of them depend on<br clear="none">
> > zexy externals (I hope I didn't miss any other dependencies). I haven't<br clear="none">
> > shared them yet so the documentation is quite poor (no help files, docs<br clear="none">
> > inside the abstraction) and they look a bit messy. But maybe you can get<br clear="none">
> > some inspiration for your library...<br clear="none">
> > <a rel="nofollow" shape="rect" target="_blank" href="https://www.dropbox.com/s/xvj031korqw8guf/ctab-abs.zip?dl=0">https://www.dropbox.com/s/xvj031korqw8guf/ctab-abs.zip?dl=0</a><br clear="none">
> ><br clear="none">
> > Additionally I've been working on three basic abstractions for creating,<br clear="none">
> > setting and reading multi-dimensional arrays of any number of dimensions.<br clear="none">
> > They are pure vanilla style and even come with a help file :-D. (a object<br clear="none">
> > for array resizing is yet to be done...)<br clear="none">
> > <a rel="nofollow" shape="rect" target="_blank" href="https://www.dropbox.com/s/6xfgdyt697138e6/carray.zip?dl=0">https://www.dropbox.com/s/6xfgdyt697138e6/carray.zip?dl=0</a><br clear="none">
> ><br clear="none">
> > Would be cool to hear your opinion on the multi-dimensional array stuff!<br clear="none">
> ><br clear="none">
> > Christof<br clear="none">
> ><br clear="none">
> ><br clear="none">
> ><br clear="none">
> ><br clear="none">
</span>> > *Gesendet:* Samstag, 03. Oktober 2015 um 22:32 Uhr<br clear="none">
> > *Von:* "Matt Barber" <<a rel="nofollow" shape="rect" ymailto="mailto:brbrofsvl@gmail.com" target="_blank" href="mailto:brbrofsvl@gmail.com">brbrofsvl@gmail.com</a>><br clear="none">
> > *An:* "IOhannes m zmölnig" <<a rel="nofollow" shape="rect" ymailto="mailto:zmoelnig@iem.at" target="_blank" href="mailto:zmoelnig@iem.at">zmoelnig@iem.at</a>><br clear="none">
> > *Cc:* Pd-List <<a rel="nofollow" shape="rect" ymailto="mailto:pd-list@lists.iem.at" target="_blank" href="mailto:pd-list@lists.iem.at">pd-list@lists.iem.at</a>><br clear="none">
> > *Betreff:* Re: [PD] array-abs<br clear="none">
<div><div>> > Thanks.<br clear="none">
> ><br clear="none">
> > Yes. Right now I'm just looking to see if these would be useful, if<br clear="none">
> > there's anything awful about the syntax, if they try to do too much or are<br clear="none">
> > too fussy, if anyone would want to contribute, etc. When I get them<br clear="none">
> > polished a bit I'll do a regular release on the normal channels (I can't<br clear="none">
> > remember if I have access to anything officially Pd related).<br clear="none">
> ><br clear="none">
> > Matt<br clear="none">
> ><br clear="none">
> > On Sat, Oct 3, 2015 at 4:22 PM, IOhannes m zmölnig <<a rel="nofollow" shape="rect" ymailto="mailto:zmoelnig@iem.at" target="_blank" href="mailto:zmoelnig@iem.at">zmoelnig@iem.at</a>><br clear="none">
> > wrote:<br clear="none">
> >><br clear="none">
> >> hi,<br clear="none">
> >><br clear="none">
> >> great!<br clear="none">
> >><br clear="none">
> >> On 10/03/2015 07:36 PM, Matt Barber wrote:<br clear="none">
> >> ><br clear="none">
> >> > <a rel="nofollow" shape="rect" target="_blank" href="https://www.dropbox.com/s/45tk62dpz0z2mqo/array-abs.zip?dl=0">https://www.dropbox.com/s/45tk62dpz0z2mqo/array-abs.zip?dl=0</a><br clear="none">
> >> ><br clear="none">
> >><br clear="none">
> >> db?<br clear="none">
> >><br clear="none">
> >> would you like to put those on a version control system of sorts, e.g.<br clear="none">
> >> the puredata svn or some publicly available git repository (e.g. github)?<br clear="none">
> >><br clear="none">
> >> (read as: please let us not go back to the dark ages, where code was<br clear="none">
> >> shared by sending files around by on floppy disks and you never new<br clear="none">
> >> which version was the current one)<br clear="none">
> >><br clear="none">
> >> fgmards<br clear="none">
> >> IOhannes<br clear="none">
> >><br clear="none">
> >><br clear="none">
> >><br clear="none">
> >> _______________________________________________<br clear="none">
> >> <a rel="nofollow" shape="rect" ymailto="mailto:Pd-list@lists.iem.at" target="_blank" href="mailto:Pd-list@lists.iem.at">Pd-list@lists.iem.at</a> mailing list<br clear="none">
> >> UNSUBSCRIBE and account-management -><br clear="none">
> >> <a rel="nofollow" shape="rect" target="_blank" href="http://lists.puredata.info/listinfo/pd-list">http://lists.puredata.info/listinfo/pd-list</a><br clear="none">
> >><br clear="none">
> ><br clear="none">
> > _______________________________________________ <a rel="nofollow" shape="rect" ymailto="mailto:Pd-list@lists.iem.at" target="_blank" href="mailto:Pd-list@lists.iem.at">Pd-list@lists.iem.at</a><br clear="none">
> > mailing list UNSUBSCRIBE and account-management -><br clear="none">
> > <a rel="nofollow" shape="rect" target="_blank" href="http://lists.puredata.info/listinfo/pd-list">http://lists.puredata.info/listinfo/pd-list</a><br clear="none">
> > _______________________________________________ <a rel="nofollow" shape="rect" ymailto="mailto:Pd-list@lists.iem.at" target="_blank" href="mailto:Pd-list@lists.iem.at">Pd-list@lists.iem.at</a><br clear="none">
> > mailing list UNSUBSCRIBE and account-management -><br clear="none">
> > <a rel="nofollow" shape="rect" target="_blank" href="http://lists.puredata.info/listinfo/pd-list">http://lists.puredata.info/listinfo/pd-list</a><br clear="none">
> ><br clear="none">
<br clear="none">
> _______________________________________________<br clear="none">
> <a rel="nofollow" shape="rect" ymailto="mailto:Pd-list@lists.iem.at" target="_blank" href="mailto:Pd-list@lists.iem.at">Pd-list@lists.iem.at</a> mailing list<br clear="none">
> UNSUBSCRIBE and account-management -> <a rel="nofollow" shape="rect" target="_blank" href="http://lists.puredata.info/listinfo/pd-list">http://lists.puredata.info/listinfo/pd-list</a><br clear="none">
<br clear="none">
</div></div></blockquote></div><br clear="none"></div>
</div></div></blockquote></div><br clear="none"></div></div></div></div><br><div class="yqt2790716660" id="yqt00021">_______________________________________________<br clear="none"><a shape="rect" ymailto="mailto:Pd-list@lists.iem.at" href="mailto:Pd-list@lists.iem.at">Pd-list@lists.iem.at</a> mailing list<br clear="none">UNSUBSCRIBE and account-management -> <a shape="rect" href="http://lists.puredata.info/listinfo/pd-list" target="_blank">http://lists.puredata.info/listinfo/pd-list</a><br clear="none"></div><br><br></div> </div> </div> </div></div></body></html>