Author Topic: Ways to simplify complicated logical expressions  (Read 2593 times)

Offline Blizzard

  • This sexy
  • Administrator
  • has over 9000 posts
  • *****
  • Posts: 19982
  • LV: 648
  • Gender: Male
  • Magic midgets.
    • View Profile
    • You're already on it. (-_-')
Ways to simplify complicated logical expressions
« on: April 07, 2008, 05:46:50 PM »
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?

Code: [Select]
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.

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

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

Code: [Select]
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.

Code: [Select]
bool betterPathFound = (currentValue > bestValue);
Finally let’s shorten the evaluation of whether the node is pending to be tested or was already tested.

Code: [Select]
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.

Code: [Select]
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

« Last Edit: April 09, 2008, 06:11:20 PM by Blizzard »
Check out Daygames and our games:

King of Booze      King of Booze: Never Ever      Pet Bots
Drinking Game for Android      Never have I ever for Android      Pet Bots for Android
Drinking Game for iOS      Never have I ever for iOS      Pet Bots for iOS
Drinking Game on Steam


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

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

Offline Zeriab

  • Ethereal Devastator
  • ****
  • Posts: 350
  • LV: 65
  • Mighty Scripter
    • View Profile
    • Zeriab's Junk
Re: Ways to simplify complicated logical expressions
« Reply #1 on: April 07, 2008, 06:43:15 PM »
*hugs Blizzard* <3

Offline Vell

  • Lexima Warrior
  • *******
  • Posts: 2915
  • LV: 49
  • Doubt for the dead.
    • View Profile
Re: Ways to simplify complicated logical expressions
« Reply #2 on: April 07, 2008, 10:07:48 PM »
???

IT STILL MAKES NO SENSE!

Offline Blizzard

  • This sexy
  • Administrator
  • has over 9000 posts
  • *****
  • Posts: 19982
  • LV: 648
  • Gender: Male
  • Magic midgets.
    • View Profile
    • You're already on it. (-_-')
Re: Ways to simplify complicated logical expressions
« Reply #3 on: April 08, 2008, 08:08:47 AM »
Which if-statement is easier "to read"?

Code: [Select]
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];
}

Code: [Select]
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      King of Booze: Never Ever      Pet Bots
Drinking Game for Android      Never have I ever for Android      Pet Bots for Android
Drinking Game for iOS      Never have I ever for iOS      Pet Bots for iOS
Drinking Game on Steam


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

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