2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – vonbrand Jul 23 '15 at 2:28
  • $\begingroup$ This is known as decision tree complexity. $\endgroup$ – Yuval Filmus Jul 23 '15 at 19:18
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Jul 24 '15 at 1:13
  • $\begingroup$ 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. $\endgroup$ – D.W. Oct 30 '15 at 22:01
  • $\begingroup$ @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. :) $\endgroup$ – Markus A. Oct 30 '15 at 22:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.