Randomizing order of if ... else statements. What's the most efficient way?

Question

The purpose of doing this is so that the top of the if statements is not preferred over the bottom. I tried assigning enum values to each case. Then choose a random integer r from 0 to the size of the std::list myList containing those enum elements. The enum value is found using it = std::next (myList, r). Then if the if statement corresponding to that enum value is false, then myList.erase (it), and repeat the process with the newly reduce myList. It works, and everything seems nicely randomized. But it is disappointingly much slower than when I used the original if-else statements. Any suggestions to a faster method?
Here is a snippet of my code. There is a crowd of girls. Each guy will choose a girl, and then choose a facing direction to dance with his chosen girl. But not all facing directions are possible if someone is standing at the spot he wants to stand at to get his desired facing direction. Without randomizing the if-else statements, most of the guys will end up facing the same direction, which I don't like.

std::list<FacingDirection> guyFacingDirections = {Positive_x, Negative_x, Positive_y, Negative_y, Positive_xPositive_y, Positive_xNegative_y, Negative_xPositive_y, Negative_xNegative_y};
while (true)    {
    const int r = rand() % guyFacingDirections.size();
    std::list<FacingDirection>::iterator it = std::next(guyFacingDirections.begin(), r);        
    const FacingDirection facingDirectionChoice = *it;
    if (facingDirectionChoice == Positive_x)  // I decided that using switch (facingDirectionChoice) {case Positive_x: if (... was too clumsy in code and probably no more efficient.
    {  
        if (mainArea.locationAvailable (xChoice - 1, yChoice, zChoice))
            {guy->movesToNewLocation (xChoice - 1, yChoice, zChoice);  break;} 
        else
            guyFacingDirections.erase (it);  // more efficient than 'guyFacingDirections.remove (Positive_x);'
    }
    else if (facingDirectionChoice == Negative_x)
    {  
        if (mainArea.locationAvailable (xChoice + 1, yChoice, zChoice))
            {guy->movesToNewLocation (xChoice + 1, yChoice, zChoice);  break;} 
        else
            guyFacingDirections.erase (it);
    }
    else if (facingDirectionChoice == Positive_y)
    {  
        if (mainArea.locationAvailable (xChoice, yChoice - 1, zChoice))
            {guy->movesToNewLocation (xChoice, yChoice - 1, zChoice);  break;} 
        else
            guyFacingDirections.erase (it);
    }
    else if (facingDirectionChoice == Negative_y)
    {  
        if (mainArea.locationAvailable (xChoice, yChoice + 1, zChoice))
            {guy->movesToNewLocation (xChoice, yChoice + 1, zChoice);  break;} 
        else
            guyFacingDirections.erase (it);
    }
    else if (facingDirectionChoice == Positive_xPositive_y)
    {  
        if (mainArea.locationAvailable (xChoice - 1, yChoice - 1, zChoice))
            {guy->movesToNewLocation (xChoice - 1, yChoice - 1, zChoice);  break;} 
        else
            guyFacingDirections.erase (it);
    }
    else if (facingDirectionChoice == Positive_xNegative_y)
    {  
        if (mainArea.locationAvailable (xChoice - 1, yChoice + 1, zChoice))
            {guy->movesToNewLocation (xChoice - 1, yChoice + 1, zChoice);  break;} 
        else
            guyFacingDirections.erase (it);
    }
    else if (facingDirectionChoice == Negative_xPositive_y)
    {  
        if (mainArea.locationAvailable (xChoice + 1, yChoice - 1, zChoice))
            {guy->movesToNewLocation (xChoice + 1, yChoice - 1, zChoice);  break;} 
        else
            guyFacingDirections.erase (it);
    }
    else if (facingDirectionChoice == Negative_xNegative_y)
    {  
        if (mainArea.locationAvailable (xChoice + 1, yChoice + 1, zChoice))
            {guy->movesToNewLocation (xChoice + 1, yChoice + 1, zChoice);  break;} 
        else
            guyFacingDirections.erase (it);
    }
    } 

Answer 1

Yes, I did try the following:

struct Direction {
    int delta_x;
    int delta_y;
    // FacingDirection dir;  // if this information is also desired
};
static std::vector<Direction> directions = { {1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1} }; // static so that it only needs be initialized once
std::random_shuffle (std::begin (directions), std::end (directions));
//FacingDirection chosenDirection;  // use this if this information is needed (currently it is not)
for (const Direction& d: directions)  // Range-based for-loop MIGHT give faster performance.
{
    const int x = xChoice + d.delta_x;
    const int y = yChoice + d.delta_y;
    if (mainArea.locationAvailable (x, y, zChoice))
    {
        guy->movesToNewLocation (x, y, zChoice);
        //chosenDirection = d.dir;  // currently not needed for my program
        break;
    } 
}

Thanks to JLBorges for this suggestion. It turns out that it does NOT perform faster than my original method, but it does tackle the problem of handling arbitrary large number of cases.

It appears that there is currently no way to randomize the ordering of if-else statements while getting the performance to almost match that of an un-randomized set of if-else statements. It should be something for the C++14 committee to work on.

Answer 2

Good news, you can both make this run faster, make the code a lot shorter, a lot clearer and easier to move...not to mention give the behavior you want - all in one easy move :)

Define a list of facing directions:

class HandleFacingDirection {

   final int x;
   final int y;

   HandleFacingDirection(int x, int y) {
      this.x = x;
      this.y = y;
   }

   public boolean canFace(int xChoice, int yChoice, int zChoice) {
       if (mainArea.locationAvailable (xChoice + x, yChoice + y, zChoice)) {
            guy->movesToNewLocation (xChoice + 1, yChoice, zChoice);
            return true;
       } 
       return false;
   }
}

Then define an array:

HandleFacingDirection[] directionHandlers = new HandleFacingDirections[] {
     new HandleFacingDirection(1, 0),
     new HandleFacingDirection(-1, 0),
     new HandleFacingDirection(0, 1),
     new HandleFacingDirection(0, -1)
}

Define a random number generator somewhere:

Random random = new Random();

Now your code to process it just becomes:

int offset = random.nextRandomInt(directionHandlers.length);
for (int i=0;i<directionHandlers.length;i++) {
   int index = i+offset;
   if (index > directionHandlers.length)
     index -= directionHandlers.length;
   if (directionHandlers[index].canFace(xChoice, yChoice, zChoice)) {
        break;
   }
}

The general idea is that your define a Strategy pattern to determine if something is valid.

You then set up a list containing all the various permutations of that strategy pattern.

You then loop through the list starting from a random position.

The code above may need some tidying up as I just threw it together, it should give you something to build on though.

Answer 3

One final attempt combining the ideas of JLBorges and TimB:

struct Direction {
    int delta_x;
    int delta_y;
    // FacingDirection dir;  // if this information is also desired
    bool canFace (Guy* guy, int x, int y, int z) const {  
        if (guy->LocationSituated()->locationAvailable (x + delta_x, y + delta_y, z))
        {
            guy->movesToNewLocation (x + delta_x, y + delta_y, z);
            return true;  // return std::make_pair (true, dir); if FacingDirection information is needed (currently it is not)
        }
        return false;   
    }
};
static std::vector<Direction> directions = { {1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1} }; // static so initialization only once
std::random_shuffle (std::begin (directions), std::end (directions));
for (const Direction& d: directions)  // Range-based for-loop MIGHT give faster performance 
    if (d.canFace (guy, xChoice, yChoice, zChoice))  
        break;  // (xChoice, yChoice, zChoice) is the position of the girl he wants to dance with

But still no improvement in performance over my first method. But the code is now much more elegant and flexible.

Answer 4

You are using the wrong solution.

This is the problem.

most of the guys will end up facing the same direction, which I don't like.

The solution is to use random numbers to influence the direction. Don't use random numbers to influence the code generation.

Using random numbers to influence code generation has these problems:

• It will be slower (as you've already identified)
• The compiler can effectively reorder the statements anyway (compared to your source code). So you just end up fighting the compiler which isn't a good thing.
• Adds complexity, making the program harder to understand, maintain, debug, etc.

One idea fix your problem:

1. Generate a random facing direction.
2. If that direction is blocked, then pick a random rotation direction.
   • Then spin the character (in the picked direction) until it finds an unblocked orientation.