Subject: Re: [boost] Interest in a "breadth first" algorithm?
From: Brian Wood (woodbrian77_at_[hidden])
Date: 2012-06-26 15:19:39
I didn't see a reply to this. I'm copying Gary this time.
On Sat, Jun 23, 2012 at 11:20 AM, Brian Wood <woodbrian77_at_[hidden]> wrote:
> Gary Powell:
> > A while ago I needed to serialize and de-serialize a std::map and I
> > realized that the only interface was begin(), end() which of course meant
> > that re-creating this same map was the least efficient way possible, as
> > the elements were added in sorted order. Because I wrote them out using
> > begin() -> end() So I wrote a breadth first template which takes a
> > container, a template to use as the core of a queue, a template for the
> > allocator, the container and a function to apply to the elements.
> > It doesn't quite do a true breadth first traversal because I don't look
> > the inner data structure of the map, (works with sets as well) but
> > does a middle, then right, left push until it's hit all of the nodes. And
> > it doesn't copy the elements, it pushes the iterators, and calls the
> > function on that iterator when the length is 1.
> > It ended up speeding up my map recreation by about 20% (because I start
> > with a center enough node that it should never have to be rebalanced) at
> > cost of about 5% to write it this way (It's more expensive to create the
> > queue, and traverse the map from center on out), for a roughly 15% gain
> > speed.
> > Is there any interest this for boost? I've got working code but not any
> > documentation. And rather than spend a huge amount of time on that I'm
> > looking to see if anyone else has an interest in this.
> I'm interested. If you like I'll give you an investment in Ebenezer
> Enterprises . If you post it here or send it to me, I'll probably use
> it in the archive available here --
>  Past performance is not a guarantee of future results.
> > "Come gather 'round people wherever you roam. And admit that the waters
> > around you have grown. And accept it that soon you'll be drenched to the
> > bone. If your time to you is worth savin'. Ahh you better start swimmin'
> > you'll sink like a stone. For the times they are a-changin'" Bob Dylan
> Huh. Bob Dylan is from the Hibbing/Duluth part of Minnesota.
> In the days after you posted, that area received a summer's worth
> of rain in 36 hours. An 8 year old boy nearly died in the flooding
> when he was swept down a culvert. Thankfully he popped up a mile
> down the system and has been giving interviews since.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk