<div dir="ltr"><div class="gmail_default" style="font-family:verdana,sans-serif">Your [fifo-list] is very much like [list-fifo] from list-abs, which suffers from the poor [list] performance. The message-box one also suffers from having to use lists to dequeue.</div><div class="gmail_default" style="font-family:verdana,sans-serif"><br></div><div class="gmail_default" style="font-family:verdana,sans-serif">I've thought of a way to do it using [list fromsymbol], [list tosymbol], and an elaborate array storage scheme which would store the length of each list at the beginning of the list like you do in the others, and then the length of each symbol before each symbol (or -1 to store a float). Enqueueing would cost one [list-drip] plus the encoding and storing per list, but since the array is random-access, it should be O(n) over all with the size of the fifo.</div><div class="gmail_default" style="font-family:verdana,sans-serif"><br></div><div class="gmail_default" style="font-family:verdana,sans-serif">Retrieving would do it in reverse, which would cost one [list prepend]X[t a] loop plus reading and decoding per list, which should also be O(n) with the size of the fifo.</div><div class="gmail_default" style="font-family:verdana,sans-serif"><br></div><div class="gmail_default" style="font-family:verdana,sans-serif">You'd maintain a write and a read index into the array; [array size] the array to 2^24. What to do when you reach the end of the array is the tricky part. If you want to be able to do a ringbuffer kind of thing, you could just maintain another array to prewrite the list encoding into. By doing this, you'll know the entire length of what needs to be written, and if that exceeds what you have in your table, you could write an instruction (-100, say), to start at the beginning again, and then reset your write index to 0. You'd need to test to make sure that an incoming write doesn't allow your "write head" to lap your "read head".</div><div class="gmail_default" style="font-family:verdana,sans-serif"><br></div><div class="gmail_default" style="font-family:verdana,sans-serif">If you needed REALLY arbitrary size, if you got to the end of one array, you'd dynamically allocate a new one, and write an instruction to move reading to the next array when your read index reaches it.</div><div class="gmail_default" style="font-family:verdana,sans-serif"><br></div><div class="gmail_default" style="font-family:verdana,sans-serif">I have no idea if this would work (it should), or what the constant time complexity factors are here; my guess is that it's slower than the others for short fifos. [array set] and [array get] are faster than you'd think, though, allowing you to write chunks at a time, unlike [tabwrite].</div><div class="gmail_default" style="font-family:verdana,sans-serif"><br></div><div class="gmail_default" style="font-family:verdana,sans-serif">If you make it I'll tweak it (for style) to include in my array-abs collection; otherwise I'll add it to my list and make it later.</div><div class="gmail_default" style="font-family:verdana,sans-serif"><br></div><div class="gmail_default" style="font-family:verdana,sans-serif">Matt</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Nov 21, 2015 at 7:52 PM, Roman Haefeli <span dir="ltr"><<a href="mailto:reduzent@gmail.com" target="_blank">reduzent@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">On Sun, 2015-11-22 at 00:47 +0100, Christof Ressi wrote:<br>
> Just in case you don't know: There's the [fifop] object in zexy which works with lists and also lets you set the priority. I'm sure it's also faster than anything one can do with Pd objects.<br>
<br>
</span>Thanks, somehow I forgot that zexy has that. It is indeed fast (as in<br>
linear fast). I'm going to use it.<br>
<br>
Just out of curiosity, I wonder if there is a O(n) vanilla<br>
implementation, too.<br>
<span class="HOEnZb"><font color="#888888"><br>
Roman<br>
</font></span><div class="HOEnZb"><div class="h5"><br>
<br>
> > Gesendet: Sonntag, 22. November 2015 um 00:24 Uhr<br>
> > Von: "Roman Haefeli" <<a href="mailto:reduzent@gmail.com">reduzent@gmail.com</a>><br>
> > An: Pd-List <<a href="mailto:pd-list@lists.iem.at">pd-list@lists.iem.at</a>><br>
> > Betreff: [PD] Efficient FIFO in Pd: How?<br>
> ><br>
> > Hi all<br>
> ><br>
> > I'm looking for a way to implement a FIFO buffer in Pd. I'd like it to<br>
> > be able enqueue messages with an arbitrary number of elements in order<br>
> > to retrieve them in the same order later. I came up with three different<br>
> > methods, but they are all either slow at enqueuing or at dequeuing or<br>
> > even both. It seems for a quick implementation you need something like a<br>
> > ring buffer, but I can't think of any method that would work for<br>
> > symbolic elements, too (as opposed to numbers).<br>
> ><br>
> > Attached patch comparison.pd compares the methods. Isn't there really a<br>
> > O(n) implementation as opposed to O(n^2)?<br>
> ><br>
> > Roman<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>
<br>
</div></div><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></blockquote></div><br></div>