Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'm having trouble formulating this problem as an algorithm:

I have a set of conditionals (combined with &&) and operations, for example:

if (A && B)
    execute C
else if (D && A)
    execute E

I want an algorithm to find the optimal "if-else" tree that minimizes the amount of duplicate code. The optimal branching for the example above would be:

if (A){
    if (B)
        execute C
    else if (D)
        execute E
}

The cost of duplicate conditionals will be different for each conditional, but it is at least 1. The cost for duplicate operations (e.g. execute C) is 3.

This smells like a minimum spanning tree problem, to me. Or maybe some other known graph theory problem. But I can't figure out how to represent the problem as a graph to begin with.

Here is a comparison of the two "if-else" trees from the example:

example graph

share|improve this question
    
In your first example, A may be evaluated twice when !B && D. The second is not necessarily identical if there are any side effects in A, B, or D. Could you display the graph and costs of the two examples and how the second one is better? –  MichaelT Dec 31 '13 at 0:35
    
Okay, I added a graph for the example. The conditionals are all independent of each other, so there will be no side effects. –  Azmisov Dec 31 '13 at 0:58
2  
are you asking a programming question or an algorithm question? –  Mathew Foscarini Dec 31 '13 at 1:03
    
This is an algorithm question. It would be an algorithm for a program that generates code. –  Azmisov Dec 31 '13 at 1:13

3 Answers 3

Avoid nesting logic into inner blocks as much as possible. It makes code harder to read.

if (!A)
   return

if (B)
   execute C

if (D)
   execute E

Exit if not A. Otherwise B or D, but if you know D is already true when B is false. You could drop the if (D) and just execute E.

In cases like this it's preferred to use a switch.

if (!A)
   return

switch R
    case B:
       execute C
       break
    case D:
       execute E
       breal
share|improve this answer
1  
I often use this technique to avoid "arrow-shaped" code, which I found hard to maintain. The downside is, that the additional returns are adding more exit paths, thus increasing complexity. At the end, it's a tradeoff. –  JensG Dec 31 '13 at 11:11

Assuming you don't optimize the conditionals away, you can use a Propositional Directed Acyclic Graph. It can also be considered as a Binary Decision Diagram.

Example of a PDAG:

Leaves are labeled with \top (true), \bot (false), or a Boolean variable.

Non-leaves are \bigtriangleup (logical and), \bigtriangledown (logical or) and \Diamond-nodes (logical not).

\bigtriangleup and \bigtriangledown-nodes have at least one child.

\Diamond-nodes have exactly one child.

http://upload.wikimedia.org/wikipedia/commons/f/f4/BDD2pdag.png

The PDAG allows you to use all the standard graph algorithms on it as appropriate. However, you're probably better off optimizing away any conditionals that you can.

share|improve this answer
    
I'm unclear as to what "optimizing away conditionals" entails. I also looked at the BDD wiki, and it appears my problem is very similar to finding the best variable ordering of a BDD. This is apparently NP, which is disheartening. –  Azmisov Dec 31 '13 at 17:48

In a comment you wrote that this is a code generation issue - essentially a factory or builder pattern.

I would argue that is is possible to optimize the conditionals away in a lot of practical scenarios like the example below shows. In addition i would clain that if the execution time to get a boolean information about A, B or C varies optimization can not be done by optimizing if/else statements. This couvers all scenarios that i am aware of.

The fastest way to evaluate would be to present all booleans in a common variable and only evaluate that single variable. Depending on the system this is meant to run on this may or may not be possible and may or may not already be the case.

The solution should scale up with constant execution to the point where the ammount of bool information excessed the ammount of bits in an integer.

This is meant as a preactical solution with a finite set of booleans where it is known at compiletime what set of booleans should result in what set of executions.

Here is some pseudocode:

func()
{
    unsigned currentSwitches = GetBooleanSet();
    executeable currentExEc = ExecFactory(currentSwitches);
    currentExEc();
}

executeable ExecFactory(unsigned allMySwitches)
{
    switch(allMySwitches)
    {
        case 0x....: return exeLib.HeaterOn; break;
        case 0x....: return exeLib.HeaterOff; break;
        case 0x....: return exeLib.BeepLikeCrazy; break;
        default : return exeLib.NotImplementedExecution; break;
    }
}

Edit:

Depending on how you are presented with your booleans you may or may not have to do anything at all. One scenario is that you read your booleans from some form of stream (TCP, File, etc) where they may already comacted. Another option may be that you are in a from of programmable logic environment where your bool options already share a register.

Suppose you are not in that position you may end up with custom bit fiddeling. Here is one expensive option to do that in the from of pseudocode:

enum {
bit_A, bit_B, bit C
}

GetBooleanset()
{
return (bool_A << bit_A) | (bool_B << bit_B) | (bool_C << bit_C);
}

This expression will be optimized by your build process and you can check if the speed fits your requirements. Depending on the ammount of options and their volatility you may for example optimize by tracking the changed options and rebuild only the parts that did change.

It really depends heavily on the environment you are working in.


EDIT:

I wrote a small Ansi C implementation of the pseudocode above.

#include <stdio.h>

typedef int (*t_logf)(const char * format, ...);

#define opt_A ( 1U << 0U )
#define opt_B ( 1U << 1U )
#define opt_C ( 1U << 2U )

typedef struct {
    unsigned options;
    t_logf logf;
}System;

typedef void (*execDelegate) (System * system);
void DelegateOne (System * system);
void DelegateTwo (System * system);
void DelegateThree (System * system);
void DelegateDefault (System * system);


void buildOptions(System * system);
execDelegate ExecFactory(System * system);

void main()
{
    System system;
    execDelegate execute;
    system.logf = printf;

    buildOptions(&system);
    execute = ExecFactory(&system);
    execute(&system);

    getchar();
}

void buildOptions(System * system)
{
    //this would obviousely 
    system->options = opt_A | opt_C;
}

execDelegate ExecFactory(System * system)
{
    system->logf("options: 0x%X\n", system->options);
    switch(system->options)
    {
        case opt_A | opt_B | opt_C : return DelegateOne; break;
        case opt_B | opt_C : return DelegateTwo; break;
        case opt_A | opt_C : return DelegateThree; break;
        default : return DelegateDefault; break;
    }
}

void DelegateOne (System * system)
{
    system->logf("one\n");
}

void DelegateTwo (System * system)
{
    system->logf("two\n");
}

void DelegateThree (System * system)
{
    system->logf("three\n");
}

void DelegateDefault (System * system)
{
    system->logf("default\n");
}
share|improve this answer
1  
How might I go about combining the booleans into one expression? Would I have to use a bitmask? Would this method have to compute all the boolean expressions in func()? –  Azmisov Dec 31 '13 at 17:37
    
@Azmisov I think you would approach it as a Karnaugh map and then solve that for the appropriate coverage that you want. –  MichaelT Dec 31 '13 at 18:09
    
@Azmisov you would implement only the executions to the known variations in the factory. For everything else you would return a default that does not crash. A blind variation if you will. depending on how critical this is that function could trigger a stop of the system or just log that something unexpecteded happened. –  Johannes Jan 1 at 15:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.