Re: [boost] Interest in a "breadth first" algorithm?
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<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/>
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@gmail.com> 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<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/>
participants (1)
-
Brian Wood