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