如何重新排序布尔逻辑以更快地短路？

我有一个问题，我有一堆需要很长时间才能执行的函数，每个函数都返回一个布尔值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

如何重新排序布尔逻辑以更快地短路？

回答

相关问题