Optimizing your code: Do you really need nested loops?

Good Code by XKCD

First comes the disclaimer, nested loops sometimes are necessary or even the best approach for your problems, but is important to understand that their implementation sometimes comes with a cost.

Nobody wants an app that freezes every time the user makes and input and you need to do some calculations, and, as in almost everything in life the "best" solution is always dependant on several factors, but the point of this is not to tackle all possible scenarios, the point of this is just to explain a simple case where, although nested loops gets the job done, another solution is actually more appropriate.

A random example using nested loops

Let's say we are creating the code that runs an ATM. Inside the ATM we have stacks of bills of several denominations, and when a person comes to take some cash, we need to figure out how much bills of each denomination we need to give to the person. The best approach might be some predictive behavior that drains each stack of bills relative to each other in a way that we don't run out of a particular denomination, it will be unpleasant if you want to cash out $120 but the ATM can only give you either $100 or \$150.

To make this simpler, we are programming the ATM to output as much of the bigger denomination as it can, and continue going one denomination down until the amount of cash asked for by the client is met, to put it in simple terms, if a person asks for $320, the ATM will give back 3 $100 bills, and 1 \$20.

We also have to take into account, that the ATM has a finite amount of each bill, in the last example, we might not be able to give back 3 $100 and 1 $20, we might have to give 2 $100 bills, 2 $50 and 1 \$20.

For this example I'm going to be using javascript, so let's define the ATM inside state as an object like this:

const ATM_STATE = {
  totalAmount: 628,
  hundred: 300,
  fifty: 150,
  twenty: 80,
  ten: 40,
  five: 25,
  one: 33,
};

Each value is the amount of dollars in that particular denomination (not the amount of bills in that denomination) and the totalAmount is the sum of all of the values for each denomination.

To calculate the amount of cash the ATM is going to return, we are going to create a function that takes the ATM state and the requested amount of cash as input, and we are going to output an object with the amounts in each denomination.

Knowing that the condition for this function is that the ATM will return as much of the higher denomination first, we might think that the simplest way to implement this is by using nested loops.

// If you have node.js installed you can copy
// this code and run it in the console
const ATM_STATE = {
  totalAmount: 628,
  hundred: 300,
  fifty: 150,
  twenty: 80,
  ten: 40,
  five: 25,
  one: 33,
};

function withdraw(amount, atmState) {
  // Making a copy of the ATM state that we are going to mutate, to make
  // this a pure function
  let copyOfState = {...atmState};

  // A variable to count the steps
  let steps = 0;
  // Initializing the object we are going to return
  let returnedCash = {
    totalAmount: 0,
    hundred: 0,
    fifty: 0,
    twenty: 0,
    ten: 0,
    five: 0,
    one: 0,
  };

  // An ordered array of bill denomination from higher to lowest
  const bills = [
    ['hundred', 100],
    ['fifty', 50],
    ['twenty', 20],
    ['ten', 10],
    ['five', 5],
    ['one', 1],
  ];

  if (amount < copyOfState.totalAmount) {
    // Making sure we have enough money for the transaction

    for (let eachBill of bills) {
      // Going from highest denomination to lower

      while (amount > returnedCash.totalAmount) {
        // While we haven't yet reached the amount of cash requested

        if (eachBill[1] <= amount - returnedCash.totalAmount) {
          // If the amount left to reach our goal is less than
          // The value of this bill we break out of the loop

          // Substracting the amount from the ATM state (the copy we made)
          copyOfState[eachBill[0]] -= eachBill[1];
          copyOfState.totalAmount -= eachBill[1];

          // Adding the amount to object to return
          returnedCash[eachBill[0]] += eachBill[1];
          returnedCash.totalAmount += eachBill[1];
          steps += 1;
        } else {
          break;
        }
      }
    }
  } else if (amount === atmState.totalAmount) {
    return atmState;
  } else {
    return 'The requested amount cannot be processed';
  }

  console.log(steps);
  return returnedCash;
}

/////////////////////////////////////////
//TESTING
////////////////////////////////////////
if (typeof require != 'undefined' && require.main == module) {
  console.log(withdraw(627, ATM_STATE));
}

Before you burn me at the stake, let me just say, yes you are right, this function is the worst implementation for this task, I was truly trying my hardest to come up with a solution that is just awful, but gets the job done nonetheless.

Anyone with a little experience can easily see why this is just bad code, but the thing is, that I remember writing this type of code (to be fair it wasn't that long ago either), this is the type of code that you write when you don't have a clear image of the problem that you need to solve, and you're just coding away, creating problems that doesn't need to be created and you're working your way around them.

But coming back to the main point, this is a case where using nested loops makes the code more complicated and inefficient.

It might be the case that you find the code easier to understand if you use nested loops, in this case, we are going from the highest denomination to the lowest (first loop) and subtracting one whole value of that denomination at a time (second loop).

We can refactor this function and remove the second loop by making one operation for each denomination.

// If you have node.js installed you can copy
// this code and run it in the console
const ATM_STATE = {
  totalAmount: 628,
  hundred: 300,
  fifty: 150,
  twenty: 80,
  ten: 40,
  five: 25,
  one: 33,
};

function withdraw(amount, atmState) {
  // Making a copy of the inputs that we are going to mutate, to make
  // sure this is a pure function
  let copyOfState = {...atmState};
  let copyOfAmount = amount;

  // A variable to count the steps
  let steps = 0;

  // Initializing the object we are going to return
  let returnedCash = {
    totalAmount: 0,
    hundred: 0,
    fifty: 0,
    twenty: 0,
    ten: 0,
    five: 0,
    one: 0,
  };

  // An ordered array of bill denomination from higher to lowest
  const bills = [
    ['hundred', 100],
    ['fifty', 50],
    ['twenty', 20],
    ['ten', 10],
    ['five', 5],
    ['one', 1],
  ];

  if (copyOfAmount < copyOfState.totalAmount) {
    // Making sure we have enough money for the transaction

    for (let eachBill of bills) {
      // Going from highest denomination to lower

      if (eachBill[1] <= copyOfAmount) {
        // If the current bill value is smaller than the cash amount to return

        let multiplier = Math.floor(copyOfAmount / eachBill[1]);
        let amountToAddAndSubstract =
          eachBill[1] * multiplier < copyOfState[eachBill[0]]
            ? eachBill[1] * multiplier
            : copyOfState[eachBill[0]];

        // Substracting the amount from the ATM state (the copy we made)
        copyOfState[eachBill[0]] -= amountToAddAndSubstract;
        copyOfState.totalAmount -= amountToAddAndSubstract;

        // Adding the amount to object to return
        returnedCash[eachBill[0]] += amountToAddAndSubstract;
        returnedCash.totalAmount += amountToAddAndSubstract;

        // Updating the amount
        copyOfAmount -= amountToAddAndSubstract;

        steps += 1;
      }
    }
  } else if (copyOfAmount === atmState.totalAmount) {
    return atmState;
  } else {
    return 'The requested amount cannot be procesed';
  }

  console.log(steps);
  return returnedCash;
}

/////////////////////////////////////////
//TESTING
////////////////////////////////////////
if (typeof require != 'undefined' && require.main == module) {
  console.log(withdraw(322, ATM_STATE));
}

As you can see by the steps counter I'm printing to the console, we went from doing 6 loops, one for subtracting one bill at a time, to 3 loops making one subtraction for an entire denomination at a time.

This might sound inconsequential, but the optimized function will always make at most 6 steps, one for each denomination, no matter the amount, while the first function with nested loops will make as many steps as necessary while subtracting one bill at a time.

The important thing to take into consideration is that for other cases that you might encounter, with bigger datasets, having nested loops can considerably slow down your app, so always take into account, do you really need those nested loops?.

Thanks for reading!.