并发 Collection 最快的添加、删除和查找最高

Question

我在 C# .NET 中进行一些繁重的计算，在 parallel.for 循环中进行这些计算时，我必须在 collection 中收集一些数据，但由于内存有限，我无法收集所有数据结果，所以我只存储最好的。

这些计算必须尽可能快，因为它们已经花费了太多时间。所以在优化了很多之后我发现最慢的是我的 ConcurrentDictionary collection。我想知道我是否应该切换到具有更快添加、删除和查找最高值的东西（可能是排序的 collection）并且只对我的主要操作使用锁，或者我可以使用 ConcurrentColletion 和速度做一些好的事情调高一点。

这是我的实际代码，我知道它很糟糕，因为这个巨大的锁，但没有它我似乎失去了一致性并且我的很多删除尝试都失败了。

 public class SignalsMultiValueConcurrentDictionary : ConcurrentDictionary<double, ConcurrentBag<Signal>>
{
    public  int Limit { get; set; }
    public double WorstError { get; private set; }

    public SignalsDictionaryState TryAddSignal(double key, Signal signal, out Signal removed)
    {
        SignalsDictionaryState state;
        removed = null;

        if (this.Count >= Limit && signal.AbsoluteError > WorstError)
            return SignalsDictionaryState.NoAddedNoRemoved;

        lock (this)
        {
            if (this.Count >= Limit)
            {
                ConcurrentBag<Signal> signals;
                if (TryRemove(WorstError, out signals))
                {
                    removed = signals.FirstOrDefault();
                    state = SignalsDictionaryState.AddedAndRemoved;
                }
                else
                    state = SignalsDictionaryState.AddedFailedRemoved;
            }
            else
                state = SignalsDictionaryState.AddedNoRemoved;

            this.Add(key, signal);
            WorstError = Keys.Max();
        }
        return state;
    }

    private void Add(double key, Signal value)
    {
        ConcurrentBag<Signal> values;
        if (!TryGetValue(key, out values))
        {
            values = new ConcurrentBag<Signal>();
            this[key] = values;
        }

        values.Add(value);
    }
}

另请注意，因为我使用信号的绝对误差，有时（应该很少见）我在一个键上存储多个值。

我的计算中使用的唯一操作是 TryAddSignal，因为它做我想做的事 -> 如果我有比限制更多的信号，那么它会删除错误最高的信号并添加新信号。

因为我在计算开始时设置了 Limit 属性，所以我不需要可调整大小的 collection。

这里的主要问题是即使没有那个巨大的锁，Keys.Max 也有点太慢了。所以也许我需要其他 collection?

Answer 1

大 lock 声明至少是可疑的。如果你说 Keys.Max() 很慢，一个更简单的改进是逐步计算最大值。只有在删除密钥后才需要刷新它：

//...
if (TryRemove(WorstError, out signals))
{
    WorstError = Keys.Max();

//...

WorstError = Math.Max(WorstError, key);

Answer 2

Keys.Max()是杀手。那是 O(N)。这样做就不需要字典了。

您无法增量计算最大值，因为您正在添加和删除。所以你最好使用为此制作的数据结构。树木通常是。我相信 BCL 有 SortedList、SortedSet 和 SortedDictionary。其中之一是基于快速树。它有最小和最大操作。

或者，使用带有优先级队列的 .NET 集合库。

错误：添加是活泼的。您可能会覆盖非空集合。

Answer 3

最后我按照@usr 的建议，实现了基于二叉树的Heap。我的最终集合不是并发的而是同步的（我使用了锁）。我检查了性能思想，它完成工作的速度足够快。这是伪代码：

public class SynchronizedCollectionWithMaxOnTop
{
    double Max => _items[0].AbsoluteError;

    public ItemChangeState TryAdd(Item item, out Item removed)
    {
        ItemChangeState state;
        removed = null;

        if (_items.Count >= Limit && signal.AbsoluteError > Max)
            return ItemChangeState.NoAddedNoRemoved;

        lock (this)
        {
            if (_items.Count >= Limit)
            {
                removed = Remove();
                state = ItemChangeState.AddedAndRemoved;
            }
            else
                state = ItemChangeState.AddedNoRemoved;

            Insert(item);
        }
        return state;
    }

    private void Insert(Item item)
    {
        _items.Add(item);
        HeapifyUp(_items.Count - 1);
    }

    private void Remove()
    {
        var result = new Item(_items[0]);

        var lastIndex = _items.Count - 1;

        _items[0] = _items[lastIndex];
        _items.RemoveAt(lastIndex);

        HeapifyDown(0);

        return result;
    }
}

并发 Collection 最快的添加、删除和查找最高

Concurrent Collection with fastest possible Add, Remove and Find the highest

c#

.net

concurrency

concurrent-programming

concurrentdictionary