Thoughts on avoiding nested loops

edited February 2017 in Off-Topic

Regarding nesting, here is a bad example of "too much looping/nesting"

foreach(people as person) {
 foreach(banks as bank) {
  if (bank.people[person] == true) {
   doSomething(person, bank)
  }
 }
}

Given enough memory, a better implementation of this would be:

bankLookup = array
foreach(banks as bank) {
 foreach(bank.people as customer) {
  bankLookup[customer][bank] = true
 }
}
foreach(people as person) {
 foreach(bankLookup[person] as bank)
  doSomething(person, bank)
 }
}
  1. Assume 10000 people, 50 banks.
  2. Assume each bank has 400 accounts (20000 total accounts, average of 2 accounts per person)

First Example:

  • 10000 loops * 50 loops = 500000 comparisons
  • 10000 loops * 50 loops * 2/50 = 20000 doSomething executions
  • 500000 total loops

Second Example:

  • 50 loops * 400 loops = 20000 assignments
  • 10000 loops * 2 loops = 20000 doSomething executions
  • 40000 total loops

That's a 92% reduction in total number of loops. Improved CPU at the expense of some memory.

Edit: Formatting.

Edit 2: There are even better ways to accomplish the exact task that is being tackled here. What I'm getting at is that there are ways to avoid exponentially nested loops.

Comments