def evaluate(f,m): while not f.constant(): nav=f.navigation() i=nav.value() v=Variable(i) c=m[v] if c==0: #terms with x evaluate to zero f=Polynomial(nav.thenBranch()) else: #c==1 f=Polynomial(nav.thenBranch())+Polynomial(nav.elseBranch()) return fFor example, the call
evaluate(x(1)+x(2),{x(1).index():1,x(2).index():0})results in
1
.
We deal here with navigators, which is dangerous, because
they do not increase the internal reference count on the represented polynomial
substructure. So, one has
to ensure, that
is still valid, as long as we use a navigator on
.
But it will show its value on optimized code (e.g. PyRex), where it causes
less overhead.
A second point, why it is desirable to use navigators is, that their
thenBranch
- and elseBranch
-methods immediately return (without
further calculations) the
results of the subset0
and subset1
-functions, when the latter are
called together with the top variable of the diagram
.
In this example, this is the crucial point in terms of performance.
But, since we already call the polynomial construction on the branches,
reference counting of the corresponding subpolynomials is done anyway.
This is quite fast, but suboptimal, because only the inner functions (additions) use caching. Furthermore, it contradicts the usual ZDD recursion and generates complex intermediate results.
2010-09-14