[Python] How to reduce time complexity in calculating effective force on a particle due to a...

I want to simulate the movement of particles of different charges in a space using coulomb's law of electrostatic force and Newton's laws of kinematics in an euclidean plane, in python using pygame for visualization.

PROBLEM
For a small sample set of particles, the simulation is working pretty good but as the sample set is becoming large the simulation speed is getting reduced due to time complexity.
For reference,at 100 particles the avg FPS of the simulation was 144, and dropping to only 40 at 300+ particles.
Upon tests I figured that most of the increase in time complexity is due to the brute-force computation of forces for each particle.

Below is the function used for the computation of forces:

def compute_forces(k,particles):
for i,p in enumerate(particles):
for q in particles[i+1:]:
dx = q.x - p.x
dy = q.y - p.y
distance = math.hypot(dx, dy)
if distance < 5:
continue
force = k * p.charge * q.charge / (distance ** 2)
if abs(force) < 0.0001:
continue
angle = math.atan2(dy,dx)
fx = force * math.cos(angle)
fy = force * math.sin(angle)

p.fx_total -= fx
p.fy_total -= fy

q.fx_total +=fx
q.fy_total +=fy



Here, the input particles is a list of all the particles currently in simulation, k is the constant of coulombs law.
The calculations are made in such a way that every pairs force is calculated only one time and then applied to the total force components of both the particle, as the order of the particles in the list doesn't change.

Example: [1,2,3] be 3 particles
Now the calculation should be done in the following order:
1---->2 | 1---->3 | 2---->3
​

As of my understanding the time complexity of the function is O(n2)

I know that python dictionaries are much more faster compared to lists as they have time complexities of O(1) and O(n) respectively, but during applying the particles as a dict instead of list, a problem was arising as the indexing cant be done in the dict for the starting of the second loop from the (n+1)th particle for the nth particle in the first loop and the keys will have to be retrieved from the dict as a list for indexing. Thus there is no net increase in efficiency(As of my understanding).

I am also aware of using Quadtrees for approximating effect of far-away particles instead of brute forcing every pairs force computation,but i am unable to come up with a solution.

For rendering efficiency of the particles, all the particles are only rendered when inside the screen window.

QUESTION
What should be the best/efficient approach to calculating the forces?

Continue reading...