Ways to simplify complicated logical expressions

Started by Blizzard, April 07, 2008, 11:46:50 am

Previous topic - Next topic

Blizzard

April 07, 2008, 11:46:50 am Last Edit: April 09, 2008, 12:11:20 pm by Blizzard
This is a blog I had to write for a class. I got 4/4 points, that means 100%. The limitation was 500 words without the header, etc. We could write it in any language, so I wrote it in english. := I thought it might be useful sharing if you are NOT coding in RGSS Ruby and don't need to sacrifice readability for maximum performance. The example is for C#, but it can apply to C++ as well if you have the correct classes implemented.

N-Joy! =D


Ways to simplify complicated logical expressions


Introduction


Have you ever encoutered a logical expression in an "if" statement like the following one?

if (currentNode.Edges[i].TargetNode.HeuristicValue -
        currentNode.Edges[i].Weight >
        bestPathEdge.TargetNode.HeuristicValue -
        bestPathEdge.Weight &&
        !Closed.Contains(currentNode.Edges[i].TargetNode) &&
        !Open.Contains(currentNode.Edges[i].TargetNode))
{
    bestPathEdge = currentNode.Edges[i];
}


Judging by the names of the variables and members (where "Open" and "Closed" are "most probably" lists) one would assume that this statement has something to do with graphs. It is indeed the conditional branching of a path finder for a weighted directional graph using the A* algorithm. This is a very good example of how naming variables correctly can easify things, but this is not the actual point of this text.


Solving the Mystery


Take another look at the statement above. Figuring out what the statement actually should evaluate isn't that easy. Why are the weight and the heuristic value subtracted? Why is this value being compared with another subtraction? The statement isn't clear at first sight, because of the implementation details. What did the programmer want to tell us? The programmer should have been more clear with that statement.
Let's first actually reveal the outer context. An instance of the "Node" class has a list of all instances of the "Edge" class that start from it. Each one contains a weight and a target node. A higher edge's weight means a higher cost to use that path while a high node's heuristic value is wanted instead.

Let's now analyze and simplify the statement from above. (Not so) obviously the subtraction of the current edge's weight and the edge's target node's heuristic value can be grouped together into a current value for later processing.

int currentValue = (currentNode.Edges[i].TargetNode.HeuristicValue -
    currentNode.Edges[i].Weight);


The same can be done for the currently best path's edge.

int bestValue = (bestPathEdge.TargetNode.HeuristicValue -
    bestPathEdge.Weight);


Those two values are being compared. If the current value is higher than the currently best value, in the original statement the other conditions can be evaluated. That means we could just say that we found a better path to our target.

bool betterPathFound = (currentValue > bestValue);


Finally let's shorten the evaluation of whether the node is pending to be tested or was already tested.

bool alreadyTested =
    Closed.Contains(currentNode.Edges[i].TargetNode);
bool pendingForTest =
    Open.Contains(currentNode.Edges[i].TargetNode);


What is left to do? The only thing left is to modify the original statement.

if (betterPathFound && !alreadyTested && !pendingForTest)
{
    bestPathEdge = currentNode.Edges[i];
}


Take a look at the original statement and the result. In the latter you can clearly see what is being evaluated. The additional evaluations above only serve for the actual processing, the "if" statement itself is clearly readable and one knows what it does at first sight. Also note how the correct naming of the temporary variables makes reading the statement much easier. The details are not as important as you can analyze them additionally if needed.


Conclusion


As final conclusion it is always better to split up conditions into meaningful pieces and evaluate them separately if the "if" statement gets too big. Create a structure that is built from many little pieces rather than one monolithic statement.


References


Check out Daygames and our games:

King of Booze 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


Quote from: winkioI do not speak to bricks, either as individuals or in wall form.

Quote from: Barney StinsonWhen I get sad, I stop being sad and be awesome instead. True story.

Zeriab


Vell


Blizzard

Which if-statement is easier "to read"?

if (currentNode.Edges[i].TargetNode.HeuristicValue -
        currentNode.Edges[i].Weight >
        bestPathEdge.TargetNode.HeuristicValue -
        bestPathEdge.Weight &&
        !Closed.Contains(currentNode.Edges[i].TargetNode) &&
        !Open.Contains(currentNode.Edges[i].TargetNode))
{
    bestPathEdge = currentNode.Edges[i];
}


int currentValue = (currentNode.Edges[i].TargetNode.HeuristicValue -
    currentNode.Edges[i].Weight);
int bestValue = (bestPathEdge.TargetNode.HeuristicValue -
    bestPathEdge.Weight);
bool betterPathFound = (currentValue > bestValue);
bool alreadyTested =
    Closed.Contains(currentNode.Edges[i].TargetNode);
bool pendingForTest =
    Open.Contains(currentNode.Edges[i].TargetNode);
if (betterPathFound && !alreadyTested && !pendingForTest)
{
    bestPathEdge = currentNode.Edges[i];
}


That's the point. xD
Check out Daygames and our games:

King of Booze 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


Quote from: winkioI do not speak to bricks, either as individuals or in wall form.

Quote from: Barney StinsonWhen I get sad, I stop being sad and be awesome instead. True story.