How do I optimize this postfix expression tree for speed?
- by Peter Stewart
Thanks to the help I received in this post:
I have a nice, concise recursive function to traverse a tree in postfix order:
deque <char*> d;
void Node::postfix()
{
if (left != __nullptr) { left->postfix(); }
if (right != __nullptr) { right->postfix(); }
d.push_front(cargo);
return;
};
This is an expression tree. The branch nodes are operators randomly selected from an array, and the leaf nodes are values or the variable 'x', also randomly selected from an array.
char *values[10]={"1.0","2.0","3.0","4.0","5.0","6.0","7.0","8.0","9.0","x"};
char *ops[4]={"+","-","*","/"};
As this will be called billions of times during a run of the genetic algorithm of which it is a part, I'd like to optimize it for speed. I have a number of questions on this topic which I will ask in separate postings.
The first is: how can I get access to each 'cargo' as it is found. That is: instead of pushing 'cargo' onto a deque, and then processing the deque to get the value, I'd like to start processing it right away.
I don't yet know about parallel processing in c++, but this would ideally be done concurrently on two different processors.
In python, I'd make the function a generator and access succeeding 'cargo's using .next(). But I'm using c++ to speed up the python implementation. I'm thinking that this kind of tree has been around for a long time, and somebody has probably optimized it already. Any Ideas? Thanks
