CODEWITHSUNDEEP
loopsdata-structuresnested-loops
Dom
Dom

Reputation: 83

Avoiding double for loop

I was wondering if there was a better way to do this.

I have a nested loop in an nbody gravity sim where by each ball in a list of balls checks all balls to get the distance/mass and apply gravitational force to the ball's vectors.

something like this:

for(int i = 0; i < balls.size(); i++){
    for(int j = 0; j < balls.size(); j++){
       balls.get(i).applyForce(balls.get(j));
    }
}

Is there a different data structure I could use that could help me avoid the double loop?

I know this is a very general question, I'm just after a hint in the right direction.

Upvotes: 1

Views: 2141

Answers (1)

Sobrique
Sobrique

Reputation: 53498

Given you're testing a list of elements, and it's relationship to every other element - you're talking an O(N^2) algorithm. So no, not really.

The best you might accomplish is to discard previously tested relationships (if relevant). If you're testing 'i' vs. 'j' then you don't need to re-iterate from zero necessarily.

You could therefore probably start the second loop at i+1 unless you really need to test i -> j and also j -> i.

Upvotes: 3

Related Questions