Jef*_*ffb 2 python string expression boolean eval
我现在已经在这个项目上工作了几个月。该项目的最终目标是评估类似于功能测试的整个数字逻辑电路。只是给出问题的范围。我在此处创建的主题处理的是我在分析布尔表达式时遇到的问题。对于数字电路内的任何门，它具有以全局输入表示的输出表达式。例如：((A&B)|(C&D)^E)。然后，我想用这个表达式来计算所有可能的结果并确定每个输入对结果有多大影响。
我发现最快的方法是通过建立一个真值表作为矩阵并查看某些行（因为它的题外话就不再详述该算法），一旦唯一输入的数量超过26，就会出现问题。 -27（大约在此范围内），内存使用量远远超过16GB（我的计算机具有的最大容量）。您可能会说“购买更多RAM”，但是随着输入每增加1，内存使用量就会增加一倍。我分析的某些表达式远远超过200种独特的输入...
我现在使用的方法使用compile方法将表达式作为字符串。然后，我使用从compile方法中找到的所有输入创建一个数组。然后，我会从可能值的样本中随机选择一个逐行生成的“真”和“假”列表（这样，如果样本大小与范围相同，则它等同于真值表中的行，并且当事情太长而无法计算时，将允许我限制样本数量）。然后将这些值与输入名称压缩在一起，并用于评估表达式。这将给出初始结果，此后，我在随机布尔列表中逐列浏览并翻转布尔值，然后再次用输入压缩它，然后再次评估它以确定结果是否更改。
所以我的问题是：有没有更快的方法？我已经包括执行工作的代码。我尝试过查找和替换正则表达式，但是它总是比较慢（从我所见）。考虑到内部for循环将运行N次，其中N是唯一输入的数量。如果N > 15，则外部for循环I限制为运行2 ^ 15。因此这将导致eval被执行Min(2^N, 2^15) * (1 + N)...
作为更新，以澄清我的确切要求（对您的困惑，抱歉）。计算我需要的算法/逻辑不是问题。我正在寻找python内置'eval'的替代方法，它将更快地执行相同的操作。（采用布尔表达式格式的字符串，将字符串中的变量替换为字典中的值，然后求值该字符串）。
#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
我的问题：
只是为了确保我理解正确：您的实际问题是确定布尔表达式中每个变量对所述表达式结果的相对影响？
OP回答：
那就是我正在计算的内容，但是我的问题不在于我如何逻辑地计算它，而是我使用
eval内置的python 来执行评估。
因此，这似乎是一个经典的XY问题。您有一个实际的问题是要确定布尔表达式中每个变量的相对影响。您试图以一种相当无效的方式解决此问题，现在您实际上“感觉到”了效率低下（在内存使用和运行时间方面），您正在寻找改进解决方案的方法，而不是寻找解决原始问题的更好方法问题。
无论如何，让我们先来看一下您如何解决这个问题。我不确定gen_rand_bits应该怎么做，因此我无法真正考虑到这一点。但是，您实际上仍在尝试变量分配的每种可能组合，并查看是否将单个变量的值翻转会改变公式结果的结果。“幸运的是”，这些只是布尔变量，因此您“只是”查看2^N可能的组合。这意味着您有指数的运行时间。现在，O(2^N)算法在理论上非常糟糕，而在实践中通常可以使用它们（因为大多数算法具有可接受的平均大小并且执行速度足够快）。但是，作为详尽的算法，您实际上必须查看每个组合，不能捷径。加上使用Python进行的编译和值评估eval显然不能很快使低效的算法接受。
因此，我们应该寻找不同的解决方案。在查看您的解决方案时，可能会说实际上不可能实现更高的效率，但是在查看原始问题时，我们可以反驳。
本质上，您想做的事情类似于编译器进行静态分析时所做的事情。您想查看源代码并从那里进行分析，而不必实际评估它。由于您要分析的语言受到严格限制（仅是带有很少运算符的布尔表达式），所以这实际上并不那么难。
代码分析通常在抽象语法树（或该语法的增强版本）上进行。Python使用ast模块提供代码分析和抽象语法树生成。我们可以使用它来解析表达式并获得AST。然后，基于树，我们可以分析表达式的每个部分与整体的相关性。
现在，评估每个变量的相关性可能会变得非常复杂，但是您可以通过分析语法树来完成所有工作。我将向您展示一个支持所有布尔运算符的简单评估，但不再进一步检查表达式的语义影响：
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方法只是将工作委派给以下类型特定的方法；它与ast.NodeVisitor的操作类似，除了我们从此处返回每个节点的分析结果。但是可以增加节点而不是返回节点。
在这种情况下，评估仅基于表达式中的出现。我没有明确检查语义效果。因此，对于一个表达式A | (A & B)，我明白了{'A': 0.75, 'B': 0.25}，尽管有人可以说语义B上与结果根本没有关联（{'A': 1}取而代之）。但是，这是我会留给您的东西。到目前为止，每个二进制运算都以相同的方式处理（每个运算数的相关性为50％），但是当然可以对其进行调整以引入一些语义规则。
无论如何，都不需要实际测试变量分配。