> No, in the depth-traversal implementation, a function
> can avoid calling itself (at least in my
> implementation it's like this).
How so? It has to keep state of which nodes to visit - so instead of calling
trav, you call functions to store and fetch nodes in a container like a
stl-list. That's the same cost, function-call is function call.
There is no difference - you simply decoupled the tree traversal from the
evaluation - but combined, its the same effort. It's like in my second
example with bytecodes - the traversal is done beforehand (and only once),
and then the eval is only done on the nodes in a row.
> Because you can write seperate functions: a function
> for depth-traversal (say trav()) and another function
> for evaluation (say eval()). trav() may call eval().
> And eval() NEVER call other functions. For one
> arithmetic tree, trav() is called once, and eval() is
> called by trav() at each node. So it is not recursive.
>> Now apart from that, I still fail to see where your
>> method of evaluation has
>> any speed gains.
>
> And if you inplement eval() as an "inline" function,
> there will be no cost for function calls for eval().
> In this way it can gain some speeds.
No. Inlining works only when the actual type of your node is known, e.g.
like this (Constant and Variable are both of type :
{
Constant left;
Variable right;
left.eval();
right.eval();
}
Here the compiler can take advantage from the fact that it knows at
compiletime which eval to inline
But if you have
{
list<Node> nodes;
for(nodes::iterator it = nodes.begin(); it != nodes.end(); it++) {
(*exp).eval();
}
}
the compiler can't possibly know which node is in exp- so it has to resort
to a vtable-lookup and a method call on the result.
--
Regards,
Diez B. Roggisch
--
http://mail.python.org/mailman/listinfo/python-list
