Re: [boost] Interest in a "breadth first" algorithm?

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
> all
> > 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
> at
> > the inner data structure of the map, (works with sets as well) but
> instead
> > 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
> a
> > 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
> in
> > 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 [1].  If you post it here or send it to me, I'll probably use
> it in the archive available here --
> http://webEbenezer.net/build_integration.html
>

> .
>
> [1]  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'
> or
> > 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.
>

>
>

Shalom,
Brian Wood
Ebenezer Enterprises
http://webEbenezer.net <http://webebenezer.net/>