python - 在 Python 中将 boolean 表达式计算为字符串的更快方法

Question

我现在已经在这个项目上工作了几个月了。该项目的最终目标是评估整个数字逻辑电路，类似于功能测试；只是为了给出问题的范围。我在这里创建的主题涉及我在分析 boolean 表达式的性能方面遇到的问题。对于数字电路内的任何门，它都有一个根据全局输入的输出表达式。例如:((A&B)|(C&D)^E)。我想要用这个表达式做的是计算所有可能的结果并确定每个输入对结果的影响有多大。

我发现的最快方法是构建一个真值表作为矩阵并查看某些行(不会详细介绍该算法，因为它是题外话)，问题在于唯一输入的数量超过 26-27(大约)，内存使用量远远超过 16GB(我的电脑的最大容量)。您可能会说“购买更多 RAM”，但输入每增加 1，内存使用量就会增加一倍。我分析的一些表达式远超过 200 个独特的输入...

我现在使用的方法是使用compile方法将表达式作为字符串。然后，我使用从编译方法找到的所有输入创建一个数组。然后，我生成一个从可能值样本中随机选择的“True”和“False”列表(这样，如果样本大小与范围大小相同，则它将相当于真值表中的行)当事情变得太长而无法计算时，我可以限制样本大小)。然后，这些值与输入名称一起压缩并用于计算表达式。这将给出初始结果，之后我在随机 boolean 列表中逐列并翻转 boolean 值，然后再次将其与输入一起压缩并再次对其进行评估以确定结果是否发生变化。

所以我的问题是:有没有更快的方法？我已经包含了执行该工作的代码。我尝试过使用正则表达式来查找和替换，但它总是比较慢(据我所知)。请考虑到内部 for 循环将运行 N 次，其中 N 是唯一输入的数量。如果 N> 15，外部 for 循环我限制运行 2^15。所以这会变成执行 eval Min(2^N, 2^15) * (1 + N)...

作为更新来澄清我到底要问什么(对于任何困惑，我们深表歉意)。用于计算我需要的算法/逻辑不是问题。我正在寻求 python 内置“eval”的替代方案，它可以更快地执行相同的操作。 (获取 boolean 表达式格式的字符串，将字符串中的变量替换为字典中的值，然后计算该字符串)。

#value is expression as string
comp = compile(value.strip(), '-', 'eval')
inputs = comp.co_names
control = [0]*len(inputs)

#Sequences of random boolean values to be used
random_list = gen_rand_bits(len(inputs))


for row in random_list:
    valuedict = dict(zip(inputs, row))
    answer = eval(comp, valuedict)

    for column in range(len(row)):
        row[column] = ~row[column]

        newvaluedict = dict(zip(inputs, row))
        newanswer = eval(comp, newvaluedict)

        row[column] = ~row[column]

        if answer != newanswer:
            control[column] = control[column] + 1

Answer 1

我的问题:

Just to make sure that I understand this correctly: Your actual problem is to determine the relative influence of each variable within a boolean expression on the outcome of said expression?

OP回答:

That is what I am calculating but my problem is not with how I calculate it logically but with my use of the python eval built-in to perform evaluating.

---

所以，这似乎是一个经典XY problem 。您有一个实际问题，即确定 boolean 表达式中每个变量的相对影响。您尝试以一种相当无效的方式解决这个问题，现在您实际上“感觉到”效率低下(在内存使用和运行时间方面)，您寻找改进解决方案的方法，而不是寻找更好的方法来解决您原来的问题问题。

无论如何，让我们首先看看您如何尝试解决这个问题。我不太确定 gen_rand_bits 应该做什么，所以我无法真正考虑到这一点。但是，您本质上仍然在尝试变量分配的每种可能的组合，并查看翻转单个变量的值是否会改变公式结果的结果。 “幸运的是”，这些只是 boolean 变量，因此您“仅”正在查看2^N种可能的组合。这意味着您的运行时间呈指数级增长。现在，O(2^N) 算法在理论上非常非常糟糕，而在实践中使用它们通常还可以(因为大多数算法都有可接受的平均情况并且执行速度足够快)。然而，作为一种详尽的算法，您实际上必须查看每一个组合，并且不能走捷径。另外，使用 Python 的 eval 进行编译和值评估显然速度不够快，无法让低效的算法被接受。

因此，我们应该寻找不同的解决方案。在查看您的解决方案时，人们可能会说提高效率实际上是不可能的，但在查看原始问题时，我们可以反驳。

您本质上想要做类似于编译器所做的事情 static analysis 。您想要查看源代码并从那里对其进行分析，而不必实际对其进行评估。由于您正在分析的语言受到高度限制(只是一个带有很少运算符的 boolean 表达式)，因此这并不是那么难。

代码分析通常适用于 abstract syntax tree (或其增强版本)。 Python 通过其 ast 提供代码分析和抽象语法树生成。模块。我们可以用它来解析表达式并获取 AST。然后根据树，我们可以分析表达式的每个部分与整体的相关程度。

现在，评估每个变量的相关性可能会变得相当复杂，但是您可以通过分析语法树来完成这一切。我将向您展示一个支持所有 boolean 运算符的简单评估，但不会进一步检查表达式的语义影响:

import ast

class ExpressionEvaluator:
    def __init__ (self, rawExpression):
        self.raw = rawExpression
        self.ast = ast.parse(rawExpression)

    def run (self):
        return self.evaluate(self.ast.body[0])

    def evaluate (self, expr):
        if isinstance(expr, ast.Expr):
            return self.evaluate(expr.value)
        elif isinstance(expr, ast.Name):
            return self.evaluateName(expr)
        elif isinstance(expr, ast.UnaryOp):
            if isinstance(expr.op, ast.Invert):
                return self.evaluateInvert(expr)
            else:
                raise Exception('Unknown unary operation {}'.format(expr.op))
        elif isinstance(expr, ast.BinOp):
            if isinstance(expr.op, ast.BitOr):
                return self.evaluateBitOr(expr.left, expr.right)
            elif isinstance(expr.op, ast.BitAnd):
                return self.evaluateBitAnd(expr.left, expr.right)
            elif isinstance(expr.op, ast.BitXor):
                return self.evaluateBitXor(expr.left, expr.right)
            else:
                raise Exception('Unknown binary operation {}'.format(expr.op))
        else:
            raise Exception('Unknown expression {}'.format(expr))

    def evaluateName (self, expr):
        return { expr.id: 1 }

    def evaluateInvert (self, expr):
        return self.evaluate(expr.operand)

    def evaluateBitOr (self, left, right):
        return self.join(self.evaluate(left), .5, self.evaluate(right), .5)

    def evaluateBitAnd (self, left, right):
        return self.join(self.evaluate(left), .5, self.evaluate(right), .5)

    def evaluateBitXor (self, left, right):
        return self.join(self.evaluate(left), .5, self.evaluate(right), .5)

    def join (self, a, ratioA, b, ratioB):
        d = { k: v * ratioA for k, v in a.items() }
        for k, v in b.items():
            if k in d:
                d[k] += v * ratioB
            else:
                d[k] = v * ratioB
        return d

expr = '((A&B)|(C&D)^~E)'
ee = ExpressionEvaluator(expr)
print(ee.run())
# > {'A': 0.25, 'C': 0.125, 'B': 0.25, 'E': 0.25, 'D': 0.125}

此实现本质上将为给定表达式生成一个简单的 AST，并递归地遍历树并评估不同的运算符。大的evaluate方法只是将工作委托(delegate)给下面的特定于类型的方法；类似于 ast.NodeVisitor只不过我们在这里返回每个节点的分析结果。不过，我们可以增加节点而不是返回节点。

在这种情况下，评估仅基于表达式中的出现。我没有明确检查语义效果。因此对于表达式 A | (A & B)，我得到 {'A': 0.75, 'B': 0.25}，尽管有人可能会认为 B 在语义上没有相关性完全不影响结果(改为 {'A': 1})。然而，这是我留给你的东西。截至目前，每个二元运算的处理方式都是相同的(每个操作数的相关性为 50%)，但是当然可以进行调整以引入一些语义规则。

无论如何，都没有必要实际测试变量分配。