Some random idea: repeated fields support stl-style iterators; should be possible to use regular std::sort() on it with a custom functor. You probably can hide a lot of code complexity by writing such functors and avoiding runtime complexity by keeping stuff sorted, indeed.
On Sun, Feb 14, 2010 at 11:35, J Jack <jjjac...@yahoo.com> wrote: > Hello, > > We're using protocol buffers extensively within our application, in > what I believe is a somewhat strange manner. > > We define a message type, that essentially looks like a struct of an > id, possibly some data, and a type, and add this include the struct > within the message (i.e, infinite recursability), to give us a tree- > like structure. > > We add nodes with some data, as well as nodes to those nodes with some > other data (specifically related to those nodes), etc. > > Quite often, we haveto merge two of these structures based on > arbitrary rules (for instance, add this to container X, but only if it > doesn't contain Y, or contain "something" already), etc. > Right now, we're essentially iterating through both containers at the > top level matching up ids, etc, and then recursing into each sub-node > based on the id, this works fine, but, the code isn't as nice as it > could be. > > What I'm wondering is if there's any way to store the messages sorted > in some manner within each record (by the id), this would allow us to > just do a binary search on merges, turning time into (I believe) log > N, drastically speeding up both searches, and merges. > > I understand that protocol buffers itself offers no such facility, but > I'm wondering if implementing one on top is advisable? Essentially I > guess I'd haveto rebuild the structure everytime I do a merge (in > order to keep it sorted). Each structure individually is fairly small > (~1kb), but, we deal with billions of these structures on a daily > basis(merging, searching through them, etc), I'm worried having to > keep them always sorted (and hence re-building the structure on each > merge) will cause memory fragmentation in the long run. > > On the top level (i.e, right below the root), we have maybe 10-15 > nodes, each of which contain up to 1000 items, (a random amount of > these will be nodes that contain subnodes too). > > Another idea I had was to store the entire thing as a hashmap of > hashmaps, but, right now, the coding/overhead for it doesn't seem to > be worth it. > > And finally, is there some way Swap could be used to maintain a sorted > structure efficiently? > > Any responses appreciated, > > Thanks! > > -- > You received this message because you are subscribed to the Google Groups > "Protocol Buffers" group. > To post to this group, send email to proto...@googlegroups.com. > To unsubscribe from this group, send email to > protobuf+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/protobuf?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Protocol Buffers" group. To post to this group, send email to proto...@googlegroups.com. To unsubscribe from this group, send email to protobuf+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/protobuf?hl=en.
