<html><head></head><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_1448207469028_14162">Are you trying to add Pd messages to a queue of Pd messages, or create a fifo <br></div><div id="yui_3_16_0_1_1448207469028_14163">for atoms?</div><div id="yui_3_16_0_1_1448207469028_14164"><br></div><div id="yui_3_16_0_1_1448207469028_14166">-Jonathan<br></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, November 22, 2015 11:17 AM, Roman Haefeli <reduzent@gmail.com> wrote:<br></font></div> <br><br> <div class="y_msg_container">On Sun, 2015-11-22 at 16:57 +0100, Jack wrote:<br clear="none">> Why you don't use [text] to build a fifo abs ?<br clear="none"><br clear="none"><br clear="none">One of the three examples I posted uses [text] as storage. While popping<br clear="none">is fast, adding messages to the buffer gets slower the more messages are<br clear="none">in the buffer. I was looking for an implementation that is fast with<br clear="none">pushing and popping.<br clear="none"><br clear="none">Roman<div class="yqt0895089178" id="yqtfd29443"><br clear="none"><br clear="none">> <br clear="none">> Le 22/11/2015 09:47, Roman Haefeli a écrit :<br clear="none">> > On Sun, 2015-11-22 at 01:47 -0500, Matt Barber wrote:<br clear="none">> >> Your [fifo-list] is very much like [list-fifo] from list-abs,<br clear="none">> >> which suffers from the poor [list] performance. The message-box<br clear="none">> >> one also suffers from having to use lists to dequeue.<br clear="none">> >> <br clear="none">> >> <br clear="none">> >> I've thought of a way to do it using [list fromsymbol], [list <br clear="none">> >> tosymbol], and an elaborate array storage scheme which would<br clear="none">> >> store the length of each list at the beginning of the list like<br clear="none">> >> you do in the others, and then the length of each symbol before<br clear="none">> >> each symbol (or -1 to store a float). Enqueueing would cost one<br clear="none">> >> [list-drip] plus the encoding and storing per list, but since the<br clear="none">> >> array is random-access, it should be O(n) over all with the size<br clear="none">> >> of the fifo.<br clear="none">> >> <br clear="none">> >> <br clear="none">> >> Retrieving would do it in reverse, which would cost one [list <br clear="none">> >> prepend]X[t a] loop plus reading and decoding per list, which<br clear="none">> >> should also be O(n) with the size of the fifo.<br clear="none">> >> <br clear="none">> >> <br clear="none">> >> You'd maintain a write and a read index into the array; [array<br clear="none">> >> size] the array to 2^24. What to do when you reach the end of the<br clear="none">> >> array is the tricky part. If you want to be able to do a<br clear="none">> >> ringbuffer kind of thing, you could just maintain another array<br clear="none">> >> to prewrite the list encoding into. By doing this, you'll know<br clear="none">> >> the entire length of what needs to be written, and if that<br clear="none">> >> exceeds what you have in your table, you could write an<br clear="none">> >> instruction (-100, say), to start at the beginning again, and<br clear="none">> >> then reset your write index to 0. You'd need to test to make sure<br clear="none">> >> that an incoming write doesn't allow your "write head" to lap<br clear="none">> >> your "read head".<br clear="none">> > <br clear="none">> > <br clear="none">> > Yeah, I thought about something similar, too. It'll basically look<br clear="none">> > like this:<br clear="none">> > <br clear="none">> > [list-fromlist] <- converts any list to list of numbers | [nfifo]<br clear="none">> > <- FIFO using a table as a ring-buffer | [list-tolist] converts<br clear="none">> > back to lists with symbols<br clear="none">> > <br clear="none">> >> If you needed REALLY arbitrary size, if you got to the end of<br clear="none">> >> one array, you'd dynamically allocate a new one, and write an<br clear="none">> >> instruction to move reading to the next array when your read<br clear="none">> >> index reaches it.<br clear="none">> > <br clear="none">> > I guess if I would go for the route of converting everything to<br clear="none">> > numbers first, I'd use simply a [table] and it could be resized<br clear="none">> > when necessary.<br clear="none">> > <br clear="none">> >> I have no idea if this would work (it should), or what the<br clear="none">> >> constant time complexity factors are here; my guess is that it's<br clear="none">> >> slower than the others for short fifos. [array set] and [array<br clear="none">> >> get] are faster than you'd think, though, allowing you to write<br clear="none">> >> chunks at a time, unlike [tabwrite].<br clear="none">> > <br clear="none">> >> If you make it I'll tweak it (for style) to include in my<br clear="none">> >> array-abs collection; otherwise I'll add it to my list and make<br clear="none">> >> it later.<br clear="none">> > <br clear="none">> > Sounds interesting to do, but I'm not sure whether I'm going to<br clear="none">> > invest time in it. [fifop] works pretty well for my current use<br clear="none">> > case.<br clear="none">> > <br clear="none">> > Roman<br clear="none">> > <br clear="none">> > <br clear="none">> >> On Sat, Nov 21, 2015 at 7:52 PM, Roman Haefeli<br clear="none">> >> <<a shape="rect" ymailto="mailto:reduzent@gmail.com" href="mailto:reduzent@gmail.com">reduzent@gmail.com</a>> wrote: On Sun, 2015-11-22 at 00:47 +0100,<br clear="none">> >> Christof Ressi wrote:<br clear="none">> >>> Just in case you don't know: There's the [fifop] object in<br clear="none">> >> zexy which works with lists and also lets you set the priority.<br clear="none">> >> I'm sure it's also faster than anything one can do with Pd<br clear="none">> >> objects.<br clear="none">> >> <br clear="none">> >> Thanks, somehow I forgot that zexy has that. It is indeed fast <br clear="none">> >> (as in linear fast). I'm going to use it.<br clear="none">> >> <br clear="none">> >> Just out of curiosity, I wonder if there is a O(n) vanilla <br clear="none">> >> implementation, too.<br clear="none">> >> <br clear="none">> >> Roman<br clear="none">> >> <br clear="none">> >> <br clear="none">> >>>> Gesendet: Sonntag, 22. November 2015 um 00:24 Uhr Von: "Roman<br clear="none">> >>>> Haefeli" <<a shape="rect" ymailto="mailto:reduzent@gmail.com" href="mailto:reduzent@gmail.com">reduzent@gmail.com</a>> An: Pd-List<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>> Betreff: [PD] Efficient FIFO in Pd:<br clear="none">> >>>> How?<br clear="none">> >>>> <br clear="none">> >>>> Hi all<br clear="none">> >>>> <br clear="none">> >>>> I'm looking for a way to implement a FIFO buffer in Pd.<br clear="none">> >> I'd like it to<br clear="none">> >>>> be able enqueue messages with an arbitrary number of<br clear="none">> >> elements in order<br clear="none">> >>>> to retrieve them in the same order later. I came up with<br clear="none">> >> three different<br clear="none">> >>>> methods, but they are all either slow at enqueuing or at<br clear="none">> >> dequeuing or<br clear="none">> >>>> even both. It seems for a quick implementation you need<br clear="none">> >> something like a<br clear="none">> >>>> ring buffer, but I can't think of any method that would<br clear="none">> >> work for<br clear="none">> >>>> symbolic elements, too (as opposed to numbers).<br clear="none">> >>>> <br clear="none">> >>>> Attached patch comparison.pd compares the methods. Isn't<br clear="none">> >> there really a<br clear="none">> >>>> O(n) implementation as opposed to O(n^2)?<br clear="none">> >>>> <br clear="none">> >>>> Roman _______________________________________________ <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 UNSUBSCRIBE and<br clear="none">> >>>> account-management -><br clear="none">> >> <a shape="rect" href="http://lists.puredata.info/listinfo/pd-list" target="_blank">http://lists.puredata.info/listinfo/pd-list</a><br clear="none">> >>>> <br clear="none">> >> <br clear="none">> >> <br clear="none">> >> <br clear="none">> >> _______________________________________________ <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 UNSUBSCRIBE and<br clear="none">> >> account-management -> <br clear="none">> >> <a shape="rect" href="http://lists.puredata.info/listinfo/pd-list" target="_blank">http://lists.puredata.info/listinfo/pd-list</a><br clear="none">> >> <br clear="none">> >> <br clear="none">> >> <br clear="none">> > <br clear="none">> > <br clear="none">> > <br clear="none">> > _______________________________________________ <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 UNSUBSCRIBE and<br clear="none">> > 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">> > <br clear="none">> <br clear="none">> _______________________________________________<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><div class="yqt0895089178" id="yqtfd62877">_______________________________________________<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>