CODEWITHSUNDEEP
javaloopsfor-looplogic
yulai
yulai

Reputation: 761

Order of loops: how to choose the outer loop

This question has to do with programming logic, rather than programming itself. I am currently writing a program that holds two lists; one for people (with person objects) and another for gifts (books, movies, etc.)

In short terms, the program aims to deliver all the gifts to the list of people (includes code for whether or not a gift is accepted. If yes: gift disappears, if not: gift is saved for the next person).

My question is as follows: does it matter whether I go through the list of people (outer loop) and then iterate through the gifts (inner loop) to see if a person wants that particular gift? Or must I loop through the gifts first (outer) and then loop through each person (inner) to see if one gift is accepted by any person?

Hence, must I use the structure for alternative (A) or (B) (provided here in pseudocode), and how do I know which is best?

(A)

for (list of people) {
    for(list of gifts) {
        //Se if person wants gift
    }
}

(B)

for (list of gifts) {
    for(list of people) {
        //Se if gift is accepted by a person
    }
}

Upvotes: 1

Views: 1223

Answers (4)

MattClarke
MattClarke

Reputation: 1647

I have to disagree with the principle implied by most of the answers that the order does not affect performance. Of course in a very small case like this, with only 50 people and 200 gifts, the difference is negligible. But consider a more extreme case with 2 people and 1,000,000 gifts.

  • In Option A, the people variable changes value twice and the gifts variable changes value 2 million times. Total number of variable assignments 1,000,002.
  • In Option B, the gifts variable changes value 1 million times and the people variable changes value 2 million times. Total number of variable assignments 3,000,000.

It may be true that the same computational work is done inside the nested loops in both options, but the computational house-keeping to manage the nested loops differs. Even putting aside the optimisation that might be achieved by breaking out of the loop early depending on gift acceptance, performance will be improved by having the variable with fewer values as the outer loop.

Upvotes: 1

royal52
royal52

Reputation: 27

It doesn't matter which ever sequence you use, either no. of people are the outer loop or no. of gifts are the outer loop, the itterations and complexity will remains the same anyway.

Upvotes: 0

Smutje
Smutje

Reputation: 18153

Additional to the other answers, what exactly does "In short terms, the program aims to deliver all the gifts to the list of people (includes code for whether or not a gift is accepted. If yes: gift disappears, if not: gift is saved for the next person)." completely mean - does the gift-list gets modificated while traversing the users, according to a given condition? When this is true, I would traverse the gifts as the outer loop, because in the non-worst case, every removed gift reduces the list of traversions by the size of the user-list whilst when traversing the users first and in the inner loop deciding whether to apply a gift, the user list gets traversed regardless of the gifts or not.

Upvotes: 0

Avi
Avi

Reputation: 21858

It only matters if in some case you break one of the loops. In that case I'd put the break on the one that is expected to be longer. This longer list would be the inner one (because if you break the other one you break the whole thing).

Upvotes: 0

Related Questions