PLINQ O(n^2) while modifying basis list

Question

Suppose I have this sequential function:

private void Process()
{
  for (int i = 0; i < Particles.Count; i++)
    for (int j = 0; j < Particles.Count; j++)
      if (check(Particles[i], Particles[j])
      {
        Particle newParticle = Particle.Merge(Particles[i], Particles[j]);
        Particle p1 = Particles[i];
        Particle p2 = Particles[j];

        Particles.Remove(p1);
        Particles.Remove(p2);
        Particles.Add(newParticle);

        i = j = 0;
      }
}

So what does this do? It checks to see if two particles should be merged or not. If they should, a new particle is created, the originals are removed from the list, and the new particle is added to the list.

Then I did some lazy stuff by setting i and j to zero. In a single for loop, I can just Particles.RemoveAt(i--) and the loop will continue where it left off, but since here we have i and j it's a lot more complicated.

Anyway. This is another block of code which should be very easy to parallelise. The only problem is that I need to modify the collection I'm iterating over, regardless whether it's parallel or sequential.

If I use foreach instead of for, I get an exception saying the size of the collection has changed. If I use PLINQ:

private void Process()
{
  Particles.AsParallel.ForAll(p1 =>
  {
    Particles.ForEach(p2 =>
    {
      if (check(p1, p2)
      {
        Particle newParticle = Particle.Merge(p1, p2);

        Particles.Remove(p1);
        Particles.Remove(p2);
        Particles.Add(newParticle);
      }
    });
  });
}

I get a LINQ exception.

Is there any way I can parallelise this n^2 operation and be able to change the contents of the list?

Answer 1

Try doing it this way:

from p1 in Particles.AsParallel()
    let collisions = from p2 in Particles
                     where p1 != p2
                     where check(p1, p2)
                     select p2
    select Particle.Merge(p1, collisions)

Where the second Particle.Merge acts on the list of collisions to generate a new Particle. You'll want some more logic in here than this, but that should give you an idea.

The basic idea is you want to non-destructively create a new copy of the list. Then do whatever modifications and replace the old list.

Some things you'll want to do are:

• Modify Particle.Merge to operate on a list: Particle.Merge(Particle p, IEnumerable<Particle> collisions).
• Add some logic to prevent duplicates showing up in that list twice.