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