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 > > >
signature.asc
Description: This is a digitally signed message part
_______________________________________________ Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list