移除元素后，使用C#并行For循环的索引异常问题

Question

我的算法中，我想要做的是以下几点。

while (R.Count > 0)
{
    //R is also  List<string>()   
    var N = new List<string>();
    var first = R[0];
    N.Add(first);
    R.Remove(first);
    //below commented code runs just fine but it takes a lot of time that is why i need to do multithreading to make it faster
    //for (int i = R.Count - 1; i >= 0; i--)
    //{
    //    if (hamming(first, R[i]))
    //    {   //hamming is a function just compare two strings and returns true or false.
    //        N.Add(R[i]);
    //        R.RemoveAt(i);
    //    }
    //}

    //Below is code of my attempt of multithreading the loop. I have tried it with foreach loop as well and it gives same error 'index out of range or argument exception'

    //ATTEMPT 1 :-
    Parallel.For(0,R.Count, i =>
    {

        if (hamming(first, R[i]))
        {
            N.Add(R[i]);
            R.RemoveAt(i);
        }
    });
    //ATTEMPT 2 :-
    Parallel.For(0,R.Count, i =>
    {

        if (hamming(first, R[i]))
        {
            N.Add(R[i]);
            R[i]="";
        }
    });
    var K = R.Where(a => a == "").ToList();
    var nc = cou - N.Count;
    //the value of 'K.Count' and 'nc' should be same here but I have checked in debugger its not the same.

    N_Total.Add(N);//this is just a List<List<string>>

这段代码很容易理解，但我仍然会在这里进一步解释。

基本上，我需要运行此算法并按代码中所示比较值。如果Hamming返回true，我必须将该值添加到“N”中并从“R”中删除它，我必须删除它，因为下次外部while循环运行时列表“R”应该更小，只有那些未满足上一个循环中Hamming条件的值才应该存在于R中。

如果有人需要更多理解，我可以进一步阐述。

我的目标是以某种多线程方式实现此目标，而不会出现“索引超出范围”或“参数异常”的异常。

提前感谢您的帮助。

- Muhammad Touseef

Answer 1

首先，List<string> 不是线程安全的，这意味着它不能用于并行操作。你可以使用 ConcurrentBag<string> 替代。 ConcurrentBag 存在于 System.Collections.Concurrent 命名空间中，其中还包含其他几个线程安全的集合类。

另外一件事是，在进行任何操作前，你需要确保该索引存在。

如果 ConcurrentBag 有一些限制，那么可能值得检查下来自同一命名空间的其他集合： System.Collections.Concurrent，因为这些都是线程安全的。 https://msdn.microsoft.com/en-us/library/system.collections.concurrent.aspx

- madoxdev

---

我尝试了并发队列，但它只能从开头删除项目（如果匹配），所以对我来说不起作用，因为我是并行的，所以我必须删除该循环在那个时间访问的任何随机项。 - Muhammad Touseef

你是如何从中移除项目的？在你的情况下，你想要使用 TryTake 方法，我假设它会返回（以便将其添加到另一个集合中）并从源集合中删除对象。 - madoxdev

Answer 2

使用Parallel.Foreach在R上。Parallel.Foreach会将列表拆分成较小的块并开始处理它们。因此来自不同线程的索引不会相互冲突。

对于N，您将使用ConcurrentBag而不是List，因为它是线程安全的。这意味着当两个线程恰好同时向您的包中添加项目时，奇怪的事情不会发生。

如果您在Parallel中删除项目，则应该通知所有线程有关新更改的信息，这将很难（而且相当丑陋）实现。

List<string> R = new List<string>();


while (R.Count > 0)
{
    var removing = new ConcurrentBag<long>();

    var N = new ConcurrentBag<string>();
    var first = R[0];
    N.Add(first);
    R.Remove(first);

    Parallel.ForEach(R, (item, state, index) =>
    {
        if(hamming(first, item))
        {
            N.Add(item);

            R[(int)index] = null; // mark as null and ignore. 
                                  // this is not thread safe for versioning of list but doesn't matter.
                                  // for R ConcurrentBag can be used too but it doesn't change results after all.
        }
    });

    // now we are safe to reorganize our collection.
    R = R.Where(str => str != null).ToList(); // parallel execution doesn't help. see comments below. 
                                              // for very large collection this will finish in few milliseconds.

    // get other stuff...
}

- M.kazem Akhgary

---

ConcurrentBag 'N'没有'Add'扩展方法，那我该如何向其中添加元素呢？ - Muhammad Touseef

我知道并行索引删除会导致相同的问题，但是我能否以并行方式删除项目，因为我已经知道要删除的项目都存储在“N”中。所以我必须删除所有属于N的项目。 - Muhammad Touseef

@touseef 我已经更新了我的答案以及删除项目的方式。现在请检查结果并告诉我是否还有其他需要知道的（还能告诉我你的方法需要多长时间完成吗？） - M.kazem Akhgary

如果 R = R.AsParallel().Where(str => str != null).ToList(); 比 R = R.Where(str => str != null).ToList(); 更高效，我会非常惊讶。 - Kris Vandermotten

@touseef 注意，hamming方法也会对性能产生影响。您应该详细说明列表的大小以及如何实现hamming。 - M.kazem Akhgary