PLINQ O(n^2) при изменении базового списка

Question

Предположим, у меня есть эта последовательная функция:

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;
      }
}

Так, что это делает? Он проверяет, должны ли две частицы быть объединены или нет. Если необходимо, создается новая частица, оригиналы удаляются из списка, а новая частица добавляется в список.

Затем я сделал несколько ленивых вещей, установив i и j на ноль. В одном for петля, я могу просто Particles.RemoveAt(i--) и цикл продолжится там, где он остановился, но, поскольку здесь у нас есть i и j, все намного сложнее.

Тем не мение. Это еще один блок кода, который очень легко распараллелить. Единственная проблема заключается в том, что мне нужно изменить коллекцию, которую я перебираю, независимо от того, параллельная она или последовательная.

Если я использую foreach вместо forЯ получаю исключение, сказав, что размер коллекции изменился. Если я использую 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);
      }
    });
  });
}

Я получаю исключение LINQ.

Есть ли способ, которым я могу распараллелить эту операцию n^2 и иметь возможность изменить содержимое списка?

Answer 1

Попробуйте сделать это так:

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)

Где второй Particle.Merge действует в списке столкновений для генерации новой Частицы. Вам понадобится больше логики, чем эта, но это должно дать вам представление.

Основная идея заключается в том, что вы хотите неразрушающим образом создать новую копию списка. Затем внесите любые изменения и замените старый список.

Вот некоторые вещи, которые вы захотите сделать:

• изменять Particle.Merge оперировать списком: Particle.Merge(Particle p, IEnumerable<Particle> collisions),
• Добавьте логику, чтобы дубликаты не появлялись в этом списке дважды.