针对不同评估成本条件优化短路评估的方法

Methods for optimizing short-circuit evaluation for conditions of varying evaluation-cost

提问人:Markus A. 提问时间:9/19/2014 最后编辑:Markus A. 更新时间:9/19/2014 访问量:57

问:

这是一个有点抽象的问题,我希望没关系(如果没有,请让我知道一个更好的地方来问它):

我有一堆布尔条件,我们称之为.A, B, C, D, ...

在我的代码中,我需要使用这些条件来区分几种不同的可能方案。例如,我可以有这样的东西(在伪代码中):

if ((A and B) or not (C or D)) then process case 1
if (A and (not B) and (C or D)) then process case 2
otherwise process case 3

现在,我可以开始组合这些 if 语句来优化所需的计算数量,例如:

if (A) then {
    if (B) then {
        process case 1
    } else {
        if (C or D) then process case 2
                    else process case 1
    }
} else {
    if (C or D) then process case 3
                else process case 1
}

但我同样可以以不同的方式“短路”(我松散地使用这个词)一些评估,例如:

if (C or D) then {
    if (A) then {
        if (B) then process case 1
               else process case 2
    } else {
        process case 3
    }
} else {
    process case 1
}

假设评估这些条件的成本存在显着差异,例如,有些需要数据库调用,有些是简单的变量空检查等。然后,对于如何分解代码,可能有一个最佳解决方案(假设所有情况的可能性都相等)。

例如,如果对 A 和 B 的评估很便宜,而对 C 或 D 的评估很昂贵,那么平均而言,上面的第一个版本可能更好,因为如果 A 和 B 被证明是真的,C 和 D 就永远不需要被评估。而如果 C 和 D 便宜而 A 或 B 贵,则平均而言,版本 2 更好。

是否有一些正式的框架或其他方法来弄清楚这种优化?

布尔逻辑 短路 成本的优化器

评论

0赞 kjhughes 9/19/2014
很好的问题,但如果你在这里问不成功,请尝试测试版计算机科学 StackExchange
0赞 Makoto 5/20/2016
我认为这个问题与网络中的节点非常相似。您可以想象为每种可能的情况绘制一个路径网络。您还可以为每个节点分配成本。这意味着你可以用网络图论来解决这个问题吗?

答: 暂无答案