-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Why you don't use [text] to build a fifo abs ? ++
Jack Le 22/11/2015 09:47, Roman Haefeli a écrit : > On Sun, 2015-11-22 at 01:47 -0500, Matt Barber wrote: >> 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. >> >> >> 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. >> >> >> 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. >> >> >> 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". > > > Yeah, I thought about something similar, too. It'll basically look > like this: > > [list-fromlist] <- converts any list to list of numbers | [nfifo] > <- FIFO using a table as a ring-buffer | [list-tolist] converts > back to lists with symbols > >> 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. > > I guess if I would go for the route of converting everything to > numbers first, I'd use simply a [table] and it could be resized > when necessary. > >> 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]. > >> 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. > > Sounds interesting to do, but I'm not sure whether I'm going to > invest time in it. [fifop] works pretty well for my current use > case. > > Roman > > >> On Sat, Nov 21, 2015 at 7:52 PM, Roman Haefeli >> <reduz...@gmail.com> wrote: On Sun, 2015-11-22 at 00:47 +0100, >> Christof Ressi wrote: >>> 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. >> >> Thanks, somehow I forgot that zexy has that. It is indeed fast >> (as in linear fast). I'm going to use it. >> >> Just out of curiosity, I wonder if there is a O(n) vanilla >> implementation, too. >> >> Roman >> >> >>>> Gesendet: Sonntag, 22. November 2015 um 00:24 Uhr Von: "Roman >>>> Haefeli" <reduz...@gmail.com> An: Pd-List >>>> <pd-list@lists.iem.at> Betreff: [PD] Efficient FIFO in Pd: >>>> How? >>>> >>>> Hi all >>>> >>>> I'm looking for a way to implement a FIFO buffer in Pd. >> I'd like it to >>>> be able enqueue messages with an arbitrary number of >> elements in order >>>> to retrieve them in the same order later. I came up with >> three different >>>> methods, but they are all either slow at enqueuing or at >> dequeuing or >>>> even both. It seems for a quick implementation you need >> something like a >>>> ring buffer, but I can't think of any method that would >> work for >>>> symbolic elements, too (as opposed to numbers). >>>> >>>> Attached patch comparison.pd compares the methods. Isn't >> there really a >>>> O(n) implementation as opposed to O(n^2)? >>>> >>>> Roman _______________________________________________ >>>> Pd-list@lists.iem.at mailing list UNSUBSCRIBE and >>>> account-management -> >> http://lists.puredata.info/listinfo/pd-list >>>> >> >> >> >> _______________________________________________ >> Pd-list@lists.iem.at mailing list UNSUBSCRIBE and >> account-management -> >> http://lists.puredata.info/listinfo/pd-list >> >> >> > > > > _______________________________________________ > Pd-list@lists.iem.at mailing list UNSUBSCRIBE and > account-management -> http://lists.puredata.info/listinfo/pd-list > -----BEGIN PGP SIGNATURE----- Version: GnuPG v1 iQEcBAEBAgAGBQJWUeYCAAoJEOuluecjw8GUVOIH/0iVuh0aimX7PEzrkPZGb9/s oUB1l5gwE2ugZJnaJpErfhawq04Ee3mNk6CE1+sGz7YTr/jMmDmfRiqUZ649Meax PoTiInByVQH4i+uDgF8ExLKSM1uDIzVdJy8yPVJbFfQqBqBKmQXf4yazh6zqu6Rd QMC5tq69z+0DkliECyhhmJaPDPPo6FI0bNvO/niesDSqCMCkStKXMk/z7wlE35jG b+/DXFbTMn3hlDLASC38q4eBO73ls7wswv+CqFaOK/hKhMpY48KRw1kLB1slXwUS iW1M7S02gqXAbtxPEHPncCOgMsUmE5E+6NMTTdgyp28eZYDaY2U8y9m/9lPMtpA= =T85G -----END PGP SIGNATURE----- _______________________________________________ Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list