How do I optimize this postfix expression tree for speed?
Posted
by Peter Stewart
on Stack Overflow
See other posts from Stack Overflow
or by Peter Stewart
Published on 2010-05-05T11:44:56Z
Indexed on
2010/05/05
11:48 UTC
Read the original article
Hit count: 241
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
© Stack Overflow or respective owner