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

I have a bunch of boolean conditions, let's call them A, B, C, D, ....

In my code, I need to use these conditions to distinguish between several different possible scenarios. For example, I could have something like this (in pseudo code):

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


Now, I can start to combine these if-statements to optimize the number of evaluations needed, like:

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
}


But I could equally well "short-circuit" (I'm using the term loosely) the evaluations differently, like:

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
}


Let's say that there is a significant difference in the cost of evaluating these conditions, e.g. some require a database call, others are simple variable-null-checks, etc. Then, there is probably an optimal solution for how to break up the code (assuming all cases are somewhat equally likely).

For example, if the evaluation of A and B is cheap while the evaluation of C or D is expensive, the first version above is probably better on average as there is a chance that if A and B turn out true, C and D never need to get evaluated. Whereas if C and D are cheap while A or B are expensive, version two is better on average.

Is there some formal framework or other approach for figuring out this optimization?

• Unless this will be done many, many, many times and the costs are truly different, go with the easiest-to-understand version. Knuth sayeth "premature optimization is the root of all evil". A hard to read (and write) version is more often than not plain wrong, or will be after some changes. – vonbrand Jul 23 '15 at 2:28
• This is known as decision tree complexity. – Yuval Filmus Jul 23 '15 at 19:18
• The optimal solution depends upon both (a) the cost of each test, and (b) the probability distribution (the likelihood that each condition is true or false -- you actually need to know the joint distribution over all possible boolean conditionals). Do you have this information? If you do, it's just a matter of finding the optimal decision tree, and there will probably be techniques that are good enough in practice if the number of conditionals is not too large. – D.W. Jul 24 '15 at 1:13
• I see you edited the question recently. Thank you. Do you have any information about the question that I asked? If you can clarify the question and what you know about the probability distributions and/or costs of each conditional test (or, implicitly, what objective function/metric you want to use to evaluate candidate solutions), I will take a stab at outlining the approaches that I am aware of. – D.W. Oct 30 '15 at 22:01
• @D.W. This was meant as a general question to learn about the topic rather than one to solve a current problem I am facing. Many of these problems have specific names and often there is rich literature available about the standard algorithms/approaches used to tackle them. In a way this question was an attempt to find good keywords to stick into Google to learn more about this topic. Yuval Filmus mentioned decision tree complexity above and I started reading up on it, but it seems to assume equal cost for each evaluation and only binary outcomes. So, I guess I'm hoping for more keywords. :) – Markus A. Oct 30 '15 at 22:50