- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我现在已经在这个项目上工作了几个月。该项目的最终目标是评估类似于功能测试的整个数字逻辑电路;只是为了说明问题的范围。我在这里创建的主题涉及我在分析 boolean 表达式时遇到的问题。对于数字电路中的任何门,它都有一个根据全局输入的输出表达式。例如:((A&B)|(C&D)^E)
。我想用这个表达式做的是计算所有可能的结果,并确定每个输入对结果的影响有多大。
我发现最快的方法是将真值表构建为矩阵并查看某些行(不会详细介绍该算法,因为它是题外话),问题在于唯一输入的数量超过 26-27(大约)内存使用量远远超过 16GB(我的电脑最大)。您可能会说“购买更多 RAM”,但随着输入每增加 1,内存使用量就会翻倍。我分析的一些表达式有超过 200 个独特的输入...
我现在使用的方法是使用compile方法将表达式作为字符串。然后我创建一个数组,其中包含从编译方法中找到的所有输入。然后,我从可能值的样本中随机选择逐行生成“真”和“假”列表(这样,如果样本大小与范围大小相同,它将等同于真值表中的行,并且它当事情变得太长而无法计算时,将允许我限制样本量)。然后将这些值与输入名称一起压缩并用于计算表达式。这将给出初始结果,之后我逐列进入随机 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
最佳答案
我的问题:
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%),但当然可以对其进行调整以引入一些语义规则。
无论如何,都没有必要实际测试变量赋值。
关于python - 在 Python 中将 boolean 表达式评估为字符串的更快方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20739467/
这个问题在这里已经有了答案: How to initialize var? (11 个答案) 关闭 8 年前。 我想给一个变量赋初值 null,并在下一个 if-else block 中赋值,但是编
我正在使用 TypeScript 3.8 编写 JS 和 TS 混合的代码。我写了以下行: export * as Easing from './easing'; 应该是 fair game在 Typ
我需要将 R 代码中的“/”更改为“\”。我有这样的事情: tmp <- paste(getwd(),"tmp.xls",sep="/") 所以我的 tmp是 c:/Study/tmp.xls 我希望
我有个问题。例如我有这个: id truth count 1 1 1 2 1 2 3 0 0 4 1 1 5 1 2 6 1
我正在尝试使用“IN”和“=”来查找一些 bean。我目前正在使用此代码: $ids = array(1,2,3,4); $user = 1; $things = R::find( 'thing'
是否可以在 Xcode 中部署到其他人的手机上?我没有 iPhone,但我想测试我在 friend 手机上制作的应用程序。在我支付 99 美元之前,我想确保这不会造成麻烦。 谢谢。 最佳答案 不会有任
我试图得到一个非常大的数字(超过 unsigned long long int )。所以我把它作为一个字符串,然后一个数字一个数字地转换成整数并使用它。 #include #include int
我在 Rust 中有 C 语言库的绑定(bind),但它们并不完整。 在 C 代码中,我定义了一个简化的宏,如下所示: #define MY_MACROS1(PTR) (((my_struct1
我正在努力解决这个问题。 http://jsfiddle.net/yhcqfy44/ 动画应该自动相对于 滚动到顶部每次出现滚动条时的高度。 我已经写了这个,但没有运气: var hheight =
我正在处理一个将数字作为字符串返回的 JSON API。例如 "12" ,但是,该字段值也可以是非数字的,例如:"-" . 我已将 JSON 数据解析为映射,我想将此字段提取为 elixir 中的整数
我正在尝试编写一个类,将.wav文件转换为.aiff文件作为项目的一部分。 我遇到了几个库Alvas.Audio(http://alvas.net/alvas.audio,overview.aspx)
我想在 Lucene 中将像“New York”这样的“复合词”索引为单个术语,而不是像“new”、“york”那样。这样,如果有人搜索“new place”,则包含“new york”的文档将不会匹
我希望这个解释能让我更好地了解使用宏的优点。 最佳答案 在函数中,所有参数在调用之前都会被评估。 这意味着 or 作为函数不能是惰性的,而宏可以将 or 重写为 if 语句,该语句仅在以下情况下计算分
我有一些看起来像这样的 XML foo ]]> (注意 > 登录 "> foo")和 XSLT 样式表 当我运行xsltproc stylesheet.xs
当我尝试将 Any 转换为 List 时,如下面的示例所示,我得到“Unchecked cast: Any!”到列表'警告。有没有解决此类问题的方法? val x: List = objectOfTy
我正在使用 Python 开发一个简单的爬虫。目的是创建一个 sitemap.xml。(你可以在这里找到真正的 alpha 版本:http://code.google.com/p/sitemappy/
我想知道在 VBScript 中是否可以在多行中中断 If 语句。喜欢: If (UCase(Trim(objSheet.Cells(i, a).Value)) = "YES") Or _ (UCas
for (String item : someList) { System.out.println(item); } 使用“do while”是否等效? 谢谢。 最佳答案 如果列表为空,f
这个问题已经有答案了: 已关闭10 年前。 Possible Duplicate: Split string with delimiters in C 在 C 中将“,”分隔的列表拆分为数组的最佳方法
我有一个如下所示的字符数组: [0, 10, 20, 30, 670] 如何将此字符串转换为整数数组? 这是我的数组 int i=0; size_t dim = 1; char* array = (c
我是一名优秀的程序员,十分优秀!