在Python中評估布爾表達式作爲字符串的更快方法

Question

我一直在爲這個項目工作了幾個月。該項目的最終目標是評估類似於功能測試的整個數字邏輯電路;只是爲了給出一個問題的範圍。我在這裏創建的主題處理我在分析布爾表達式時遇到的問題。對於數字電路內的任何門電路，其輸入表達式均以全局輸入表示。 EX：((A&B)|(C&D)^E)。然後，我想要用這個表達式來計算所有可能的結果，並確定每個輸入對結果的影響程度。

我發現的最快方法是通過構建一個真值表作爲矩陣並查看某些行（不會考慮該算法的細節，因爲它是不重要的），這個問題就是一次唯一的數量輸入高於26-27（大約在那個）內存使用遠遠超過16GB（我的電腦最大）。你可能會說「購買更多內存」，但隨着輸入每增加1，內存使用量就會增加一倍。我分析的一些表達式超過200個獨特的輸入...

我現在使用的方法現在使用編譯方法將表達式作爲字符串。然後我創建一個數組，其中包含從編譯方法中找到的所有輸入。然後，我從一個可能值的樣本中隨機選擇一行「True」和「False」生成列表行（如果樣本大小與範圍大小相同，它將相當於真值表中的行）將允許我限制樣本大小，當事情變得太長而無法計算時）。然後將這些值與輸入名稱一起壓縮並用於評估表達式。這會給出初始結果，然後我在隨機布爾列表中按列逐列，然後翻轉布爾值，然後再次用輸入壓縮並再次評估，以確定結果是否改變。

所以我的問題是這樣的：有沒有更快的方法？我已經包含了執行這項工作的代碼。我試過正則表達式來查找和替換，但它總是比較慢（從我所見過的）。考慮到內循環將運行N次N是唯一輸入的數量。 for循環外我限制運行2^15，如果ň> 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 

Answer 1

而是重新發明輪子和進入一樣的性能和安全性，你已經在危險的，最好是搜索行業準備好接受庫。

的sympyLogic Module會做，你要實現不訴諸evil確切的事喔我的意思eval。更重要的是，因爲布爾表達式是而不是字符串您不必關心解析通常是瓶頸的表達式。

Answer 2

你不需要準備一個靜態表來計算它。 Python是一種動態語言，因此它可以在運行時自行解釋和運行代碼。

在你的情況下，我會建議一個soluation說：

import random, re, time 

#Step 1: Input your expression as a string 
logic_exp = "A|B&(C|D)&E|(F|G|H&(I&J|K|(L&M|N&O|P|Q&R|S)&T)|U&V|W&X&Y)" 

#Step 2: Retrieve all the variable names. 
#  You can design a rule for naming, and use regex to retrieve them. 
#  Here for example, I consider all the single-cap-lettler are variables. 
name_regex = re.compile(r"[A-Z]") 

#Step 3: Replace each variable with its value. 
#  You could get the value with reading files or keyboard input. 
#  Here for example I just use random 0 or 1. 
for name in name_regex.findall(logic_exp): 
    logic_exp = logic_exp.replace(name, str(random.randrange(2))) 

#Step 4: Replace the operators. Python use 'and', 'or' instead of '&', '|' 
logic_exp = logic_exp.replace("&", " and ") 
logic_exp = logic_exp.replace("|", " or ")  


#Step 5: interpret the expression with eval(exp) and output its value. 
print "exporession =", logic_exp 
print "expression output =",eval(logic_exp) 

---

這將是非常快的，並採取很少的內存。對於一個測試，我跑上面25輸入變量的例子：

exporession = 1 or 1 and (1 or 1) and 0 or (0 or 0 or 1 and (1 and 0 or 0 or (0 and 0 or 0 and 0 or 1 or 0 and 0 or 0) and 1) or 0 and 1 or 0 and 1 and 0) 
expression output= 1 
computing time: 0.000158071517944 seconds  

---

根據您的意見，我看你是在給定的輸入值計算所有可能的組合而不是輸出。如果是這樣，它將成爲典型的NP-completeBoolean satisfiability problem。我不認爲有任何算法可以使其複雜度低於O(2^N)。我建議你用關鍵字fast algorithm to solve SAT problem進行搜索，你會發現很多有趣的事情。

Answer 3

我的問題：

只是爲了確保我正確地理解這一點：你的實際問題是要確定一個布爾表達式中每個變量的相對影響力上說，表達的結果？

OP回答：

這就是我計算，但我的問題是不是與我如何計算邏輯但我使用Python eval內置於進行評估。

---

所以，這似乎是一個經典XY problem。你有一個實際的問題是確定布爾表達式中每個變量的相對影響。您試圖以相當無效的方式解決這個問題，現在您實際上「感覺」了效率低下（無論是內存使用情況還是運行時間），您都在尋找改進解決方案的方法，而不是尋找更好的方法來解決原始問題問題。

無論如何，我們先來看看你是如何解決這個問題的。我不確定gen_rand_bits應該做什麼，所以我不能真正考慮到這一點。但是，您仍然基本上嘗試了各種可能的賦值組合，並查看是否翻轉單個變量的值會更改公式結果的結果。 「幸運地」，這些只是布爾變量，所以你是「只」看着2^N可能的組合。這意味着你有指數運行時間。現在，O(2^N)算法在理論上是非常糟糕的，但在實踐中，使用它們通常有些不錯（因爲大多數算法具有可接受的平均情況並且執行速度足夠快）。但是，作爲一個詳盡的算法，您實際上必須考慮每個組合的並且不能快捷。此外，使用Python的eval進行編譯和價值評估顯然不是那麼快，使得低效率的算法可以接受。

所以，我們應該尋找一個不同的解決方案。當你看到你的解決方案時，可能會說效率並不是真的可行，但當看到最初的問題時，我們可以辯論。

本質上你想做的事情與編譯器的做法相似，如static analysis。你想看看源代碼並從那裏分析它，而不必實際評估它。由於您正在分析的語言受到高度限制（僅作爲運算符很少的布爾表達式），這並不是那麼難。

代碼分析通常適用於abstract syntax tree（或其擴展版本）。 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％），但當然可以通過引入一些語義規則進行調整。

以任何方式，實際上不需要測試變量賦值。