You can simplify all those algorithms a lot by just moving the test for NULL to a single location near the top. Then treating left and write identically (even when NULL).
CNode * CNode::findStackBased(int number)
{
stack<CNode*> onStack;
onStack.push(this);
while(!onStack.empty())
{
CNode tmp = onStack.top();
onStack.pop();
if (!tmp) {
continue;
}
if (tmp->number == number) {
return tmp;
}
onStack.push(tmp->right);
onStack.push(tmp->left);
}
return NULL;
}
Recursion
CNode* CNode::findRecursion(int number) {
return findRecusion(this, number);
}
CNode* CNode::findRecursion(CNode node, int number) {
if ((node == NULL) || (node->number == number) {
return node;
}
return findRecursion(node->left); // Only do the right side if left
|| findRecursion(node->right); // returns NULL
}
Walking along the edge just seems to be doing depth first left to right traversal. Its just messy and convoluted. It also requires the concept of a parent pointer.
Each of the above have have some advantages/drawbacks, but performance wise 'walking along the edge is the winner so far(out of the 3 given above).
Really. Please name them.
How are you measuring that? Not convinced that it is actually significantly faster because of all the extra comparisons you are doing. But for certain types of trees it could be faster as you don't need to maintain a stack object.
What you are doing is trading space for time (a common optimization). You are adding a parent pointer into each node to help you do the traversal more quickly. The other two techniques require you to build and maintain a stack (the state of the search (one explicitly and one implicitly in the call stack)) while the walk the edge has the information you need built into the graph.
My question is:
Do you see any way to optimize it further (recursive implementation already benefits from the tail recursion optimization, at least gcc seems to optimize it this way)?
I would be surprised if most compilers don't turn the recursion into a loop. Its an easy optimization. I would worry less about optimization and more about readability. Its usually much more important. The compilers are darn good at making the code fast.
You can simplify all those algorithms a lot by just moving the test for NULL to a single location near the top. Then treating left and write identically (even when NULL).
CNode * CNode::findStackBased(int number)
{
stack<CNode*> onStack;
onStack.push(this);
while(!onStack.empty())
{
CNode tmp = onStack.top();
onStack.pop();
if (!tmp) {
continue;
}
if (tmp->number == number) {
return tmp;
}
onStack.push(tmp->right);
onStack.push(tmp->left);
}
return NULL;
}
Recursion
CNode* CNode::findRecursion(int number) {
return findRecusion(this, number);
}
CNode* CNode::findRecursion(CNode node, int number) {
if ((node == NULL) || (node->number == number) {
return node;
}
return findRecursion(node->left); // Only do the right side if left
|| findRecursion(node->right); // returns NULL
}
Walking along the edge just seems to be doing depth first left to right traversal. Its just messy and convoluted. It also requires the concept of a parent pointer.
Each of the above have have some advantages/drawbacks, but performance wise 'walking along the edge is the winner so far(out of the 3 given above).
Really. Please name them.
How are you measuring that? Not convinced that it is actually significantly faster because of all the extra comparisons you are doing. But for certain types of trees it could be faster as you don't need to maintain a stack object.
What you are doing is trading space for time (a common optimization). You are adding a parent pointer into each node to help you do the traversal more quickly. The other two techniques require you to build and maintain a stack (the state of the search (one explicitly and one implicitly in the call stack)) while the walk the edge has the information you need built into the graph.
My question is:
Do you see any way to optimize it further (recursive implementation already benefits from the tail recursion optimization, at least gcc seems to optimize it this way)?
I would be surprised if most compilers don't turn the recursion into a loop. Its an easy optimization. I would worry less about optimization and more about readability. Its usually much more important. The compilers are darn good at making the code fast.
You can simplify all those algorithms a lot by just moving the test for NULL to a single location near the top. Then treating left and write identically (even when NULL).
CNode * CNode::findStackBased(int number)
{
stack<CNode*> onStack;
onStack.push(this);
while(!onStack.empty())
{
CNode tmp = onStack.top();
onStack.pop();
if (!tmp) {
continue;
}
if (tmp->number == number) {
return tmp;
}
onStack.push(tmp->right);
onStack.push(tmp->left);
}
return NULL;
}
Recursion
CNode* CNode::findRecursion(int number) {
return findRecusion(this, number);
}
CNode* CNode::findRecursion(CNode node, int number) {
if ((node == NULL) || (node->number == number) {
return node;
}
return findRecursion(node->left); // Only do the right side if left
|| findRecursion(node->right); // returns NULL
}
Walking along the edge just seems to be doing depth first left to right traversal. Its just messy and convoluted. It also requires the concept of a parent pointer.
Each of the above have have some advantages/drawbacks, but performance wise 'walking along the edge is the winner so far(out of the 3 given above).
Really. Please name them.
How are you measuring that? Not convinced that it is actually significantly faster because of all the extra comparisons you are doing. But for certain types of trees it could be faster as you don't need to maintain a stack object.
What you are doing is trading space for time (a common optimization). You are adding a parent pointer into each node to help you do the traversal more quickly. The other two techniques require you to build and maintain a stack (the state of the search (one explicitly and one implicitly in the call stack)) while the walk the edge has the information you need built into the graph.
My question is:
Do you see any way to optimize it further (recursive implementation already benefits from the tail recursion optimization, at least gcc seems to optimize it this way)?
I would be surprised if most compilers don't turn the recursion into a loop. Its an easy optimization. I would worry less about optimization and more about readability. Its usually much more important. The compilers are darn good at making the code fast.
You can simplify all those algorithms a lot by just moving the test for NULL to a single location near the top. Then treating left and write identically (even when NULL).
CNode * CNode::findStackBased(int number)
{
stack<CNode*> onStack;
onStack.push(this);
while(!onStack.empty())
{
CNode tmp = onStack.top();
onStack.pop();
if (!tmp) {
continue;
}
if (tmp->number == number) {
return tmp;
}
onStack.push(tmp->right);
onStack.push(tmp->left);
}
return NULL;
}
Recursion
CNode* CNode::findRecursion(int number) {
return findRecusion(this, number);
}
CNode* CNode::findRecursion(CNode node, int number) {
if ((node == NULL) || (node->number == number) {
return node;
}
return findRecursion(node->left); // Only do the right side if left
|| findRecursion(node->right); // returns NULL
}
No idea what the walkWalking along the edge is tryingjust seems to do!be doing depth first left to right traversal. Its just messy and convoluted. It also requires the concept of a parent pointer.
Each of the above have have some advantages/drawbacks, but performance wise 'walking along the edge is the winner so far(out of the 3 given above).
Really. Please name them.
How are you measuring that? Does not look likeNot convinced that it shouldis actually significantly faster because of all the extra comparisons you are doing. But for certain types of trees it could be performantfaster as you don't need to maintain a stack object.
What you are doing is trading space for time (a common optimization). You are adding a parent pointer into each node to help you do the traversal more quickly. The other two techniques require you to build and maintain a stack (the state of the search (one explicitly and one implicitly in the call stack)) while the walk the edge has the information you need built into the graph.
My question is:
Do you see any way to optimize it further (recursive implementation already benefits from the tail recursion optimization, at least gcc seems to optimize it this way)?
I would be surprised if most compilers don't turn the recursion into a loop. Its an easy optimization. I would worry less about optimization and more about readability. Its usually much more important. The compilers are darn good at making the code fast.
You can simplify all those algorithms a lot by just moving the test for NULL to a single location near the top. Then treating left and write identically (even when NULL).
CNode * CNode::findStackBased(int number)
{
stack<CNode*> onStack;
onStack.push(this);
while(!onStack.empty())
{
CNode tmp = onStack.top();
onStack.pop();
if (!tmp) {
continue;
}
if (tmp->number == number) {
return tmp;
}
onStack.push(tmp->right);
onStack.push(tmp->left);
}
return NULL;
}
Recursion
CNode* CNode::findRecursion(int number) {
return findRecusion(this, number);
}
CNode* CNode::findRecursion(CNode node, int number) {
if ((node == NULL) || (node->number == number) {
return node;
}
return findRecursion(node->left); // Only do the right side if left
|| findRecursion(node->right); // returns NULL
}
No idea what the walk along the edge is trying to do!
Each of the above have have some advantages/drawbacks, but performance wise 'walking along the edge is the winner so far(out of the 3 given above).
Really. Please name them.
How are you measuring that? Does not look like it should be performant.
My question is:
Do you see any way to optimize it further (recursive implementation already benefits from the tail recursion optimization, at least gcc seems to optimize it this way)?
I would be surprised if most compilers don't turn the recursion into a loop. Its an easy optimization. I would worry less about optimization and more about readability. Its usually much more important. The compilers are darn good at making the code fast.
You can simplify all those algorithms a lot by just moving the test for NULL to a single location near the top. Then treating left and write identically (even when NULL).
CNode * CNode::findStackBased(int number)
{
stack<CNode*> onStack;
onStack.push(this);
while(!onStack.empty())
{
CNode tmp = onStack.top();
onStack.pop();
if (!tmp) {
continue;
}
if (tmp->number == number) {
return tmp;
}
onStack.push(tmp->right);
onStack.push(tmp->left);
}
return NULL;
}
Recursion
CNode* CNode::findRecursion(int number) {
return findRecusion(this, number);
}
CNode* CNode::findRecursion(CNode node, int number) {
if ((node == NULL) || (node->number == number) {
return node;
}
return findRecursion(node->left); // Only do the right side if left
|| findRecursion(node->right); // returns NULL
}
Walking along the edge just seems to be doing depth first left to right traversal. Its just messy and convoluted. It also requires the concept of a parent pointer.
Each of the above have have some advantages/drawbacks, but performance wise 'walking along the edge is the winner so far(out of the 3 given above).
Really. Please name them.
How are you measuring that? Not convinced that it is actually significantly faster because of all the extra comparisons you are doing. But for certain types of trees it could be faster as you don't need to maintain a stack object.
What you are doing is trading space for time (a common optimization). You are adding a parent pointer into each node to help you do the traversal more quickly. The other two techniques require you to build and maintain a stack (the state of the search (one explicitly and one implicitly in the call stack)) while the walk the edge has the information you need built into the graph.
My question is:
Do you see any way to optimize it further (recursive implementation already benefits from the tail recursion optimization, at least gcc seems to optimize it this way)?
I would be surprised if most compilers don't turn the recursion into a loop. Its an easy optimization. I would worry less about optimization and more about readability. Its usually much more important. The compilers are darn good at making the code fast.
You can simplify all those algorithms a lot by just moving the test for NULL to a single location near the top. Then treating left and write identically (even when NULL).
CNode * CNode::findStackBased(int number)
{
stack<CNode*> onStack;
onStack.push(this);
while(!onStack.empty())
{
CNode tmp = onStack.top();
onStack.pop();
if (!tmp) {
continue;
}
if (tmp->number == number) {
return tmp;
}
onStack.push(tmp->right);
onStack.push(tmp->left);
}
return NULL;
}
Recursion
CNode* CNode::findRecursion(int number) {
return findRecusion(this, number);
}
CNode* CNode::findRecursion(CNode node, int number) {
if ((node == NULL) || (node->number == number) {
return node;
}
return findRecursion(node->left); // Only do the right side if left
|| findRecursion(node->right); // returns NULL
}
No idea what the walk along the edge is trying to do!
Each of the above have have some advantages/drawbacks, but performance wise 'walking along the edge is the winner so far(out of the 3 given above).
Really. Please name them.
How are you measuring that? Does not look like it should be performant.
My question is:
Do you see any way to optimize it further (recursive implementation already benefits from the tail recursion optimization, at least gcc seems to optimize it this way)?
I would be surprised if most compilers don't turn the recursion into a loop. Its an easy optimization. I would worry less about optimization and more about readability. Its usually much more important. The compilers are darn good at making the code fast.