python - 如何重新排序 bool 逻辑以更快地短路？

Question

我遇到了一个问题，我有一堆函数需要很长时间才能执行，并且每个函数都返回一个 bool 值 True/False。我对所有函数应用了一个巨大的 bool 表达式以获得整体真/假分数。目前我的代码不是基于函数的，所以所有函数都被执行，然后应用大 bool 表达式。我已经发现让它们成为函数将允许子表达式短路以防止某些函数调用。我现在需要的是一种重新排序表达式的方法，以便我有最少的调用次数。

考虑以下代码(可怕的代码示例，但您应该明白了):

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())) 

在这种情况下，您会看到打印了 q r s。都是假的所以它短路了。但在这种情况下，应首先评估 b 或 c，因为如果其中任何一个为 False，则整个表达式为 False。假设最后的表达式是由用户生成的，这样我就无法对最佳顺序进行硬编码。我想我缺少一个非常简单的算法。

另外两件事:

1.) 如果我允许“不”等其他逻辑怎么办？2.) 我可以根据运行时间为每个函数分配一个分数，然后计算该分数吗？

Answer 1

要优化你的表达式，你需要知道两件事:每个函数的成本，以及它短路的概率。一旦有了它，您就可以评估每个子表达式以产生相同的术语；尝试参数顺序的每个排列将显示哪种排列的成本最低。

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