Tree iterator, can you optimize this any further?
- by Ron
As a follow up to my original question about a small piece of this code I decided to ask a follow up to see if you can do better then what we came up with so far.
The code below iterates over a binary tree (left/right = child/next ). I do believe there is room for one less conditional in here (the down boolean). The fastest answer wins!
The cnt statement can be multiple statements so lets make sure this appears only once
The child() and next() member functions are about 30x as slow as the hasChild() and hasNext() operations.
Keep it iterative <-- dropped this requirement as the recursive solution presented was faster.
This is C++ code
visit order of the nodes must stay as they are in the example below. ( hit parents first then the children then the 'next' nodes).
BaseNodePtr is a boost::shared_ptr as thus assignments are slow, avoid any temporary BaseNodePtr variables.
Currently this code takes 5897ms to visit 62200000 nodes in a test tree, calling this function 200,000 times.
void processTree (BaseNodePtr current, unsigned int & cnt )
{
bool down = true;
while ( true )
{
if ( down )
{
while (true) {
cnt++; // this can/will be multiple statesments
if (!current->hasChild()) break;
current = current->child();
}
}
if ( current->hasNext() )
{
down = true;
current = current->next();
}
else
{
down = false;
current = current->parent();
if (!current)
return; // done.
}
}
}
