Closed danjujan closed 11 months ago
Thanks for the pull request. I haven't had a chance to review it yet.
Please help me understand the background by providing an example of how this improves performance.
Sure. When espresso_exprs
is called with only one argument, fscover
is the same as f.cover
. The outvec loop checks if fcube
is in fscube
. But since they are the same, we will always append 1
to the outvec. So we can skip the outvec loop in this case, which saves us len(fscover) * len(f.cover)
operations.
Basically, the function boils down to this:
def __espresso_expr(dnf: Expression) -> Expression:
support = dnf.support
inputs = sorted(support)
ninputs = len(inputs)
noutputs = 1
invec = [0] * ninputs
cover = set()
for cube in dnf.cover:
for i, var in enumerate(inputs):
if ~var in cube:
invec[i] = 1
elif var in cube:
invec[i] = 2
else:
invec[i] = 3
cover.add((tuple(invec), (1,)))
set_config(**CONFIG)
cover = espresso(ninputs, noutputs, cover, intype=FTYPE)
return _cover2exprs(inputs, noutputs, cover)[0]
Before this change, one call to espresso_exprs
took about 30 seconds for an expression with 22 variables and a cover of about 22000 elements. Now it takes only a second.
The fixed size lists just avoid allocating memory for every append in the loop.
LGTM
In case
espresso_exprs
has only one expression as argument, the output vector is always[1]
. This change results in a significant speedup for expressions with a large cover, as we don't need to compare the cover with itself.