如何重新排序布爾邏輯以更快地短路？

我有一個問題，我有一堆需要很長時間才能執行的函數，每個函數都返回一個布爾值True/False。我將一個巨大的布爾表達式應用於所有函數以獲得總體True/False分數。目前我的代碼不是基於函數的，所以所有的函數都被執行，然後應用大的布爾表達式。我已經知道讓它們的功能可以允許短循環的子表達式來防止某些函數調用。我現在需要的是一種重新排列表達式的方法，使得我有最少的通話次數。如何重新排序布爾邏輯以更快地短路？

考慮下面的代碼（可怕的代碼示例，但你應該明白我的意思）：

def q(): 
    print "q" 
    return False 

def r(): 
    print "r" 
    return False 

def s(): 
    print "s" 
    return False 

def a(): 
    print "a" 
    return False 

def b(): 
    print "b" 
    return False 

def c(): 
    print "c" 
    return False 


def d(): 
    print "d" 
    return False 

def i(): 
    print "i" 
    return False 

def j(): 
    print "j" 
    return False 


(q() or r() or s()) and (a() and b() and c() and (i() or j()))

在這種情況下，你見問答[R印出來。全都是假的，所以它短路。在這種情況下，應該首先評估b或c，因爲如果其中任何一個爲False，則整個表達式爲False。假設最後的表達式是由用戶生成的，所以我無法對最佳可能順序進行硬編碼。我在想，我錯過了一個非常簡單的算法。其他

兩件事情：

1）如果我允許其他邏輯，例如「不」？ 2.）我可以根據運行需要多長時間來分配每個函數，然後計算它嗎？

來源

2012-03-27 mcot

你的公式與它在CNF（順便說一句，你不需要圍繞頂級or s的圓括號），這對於計算複雜性來說非常好，它的確很簡單。既然你目前還沒有not，我真的不知道是否有必要尋找某種複雜的算法，你的公式已經夠簡單了。但是你絕對可以嘗試一些啓發式的方法（比如從評估儘可能少的文字的條款開始，所以你儘可能快地失敗......問題是，即使你從一個只有一個字面的子句開始，計算函數可能比計算更大的子句更昂貴，所以是的，不按照大小對它們進行排序是有意義的，但是根據預期的計算複雜度）。

目前，您納入not，你可以找到一些額外的東西有用。特別是如何再次將這些轉換爲CNF以及resolution的想法可能對您有用。

來源

2012-03-27 22:42:04 tchap

爲了優化您的表情，您需要知道兩件事：每個功能的成本以及短路的可能性。一旦你有了，你可以評估每個子表達式產生相同的術語;嘗試參數順序的每個排列都會顯示哪種排列具有最低的成本。

def evaluate_or(argument_evaluation_list): 
    total_cost = 0.0 
    probability_of_reaching = 1.0 
    for cost, probability_of_true in argument_evaluation_list: 
     total_cost += probability_of_reaching * cost 
     probability_of_reaching *= 1.0 - probability_of_true 
    return total_cost, 1.0 - probability_of_reaching 

def evaluate_and(argument_evaluation_list): 
    total_cost = 0.0 
    probability_of_reaching = 1.0 
    for cost, probability_of_true in argument_evaluation_list: 
     total_cost += probability_of_reaching * cost 
     probability_of_reaching *= probability_of_true 
    return total_cost, probability_of_reaching 

def evaluate_not(argument_evaluation) 
    cost, probability_of_true = argument_evaluation 
    return cost, 1.0 - probability_of_true

來源

2012-03-27 23:35:29

如何重新排序布爾邏輯以更快地短路？

回答

相關問題