以最快的速度添加，删除和查找最高的并发集合

Question

我正在c# . net中进行一些繁重的计算，并且在并行进行这些计算时。for循环我必须收集一些数据，但是由于有限的内存，我不能收集所有的结果，所以我只存储最好的。

这些计算必须尽可能快，因为它们已经花费了太多的时间。所以在优化了很多之后，我发现最慢的是我的ConcurrentDictionary集合。我想知道我是否应该切换到一些更快的添加，删除和找到最高的(也许是一个排序的集合)，只是使用锁为我的主要操作，或者我可以使用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属性，所以我不需要一个可调整大小的集合。

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

Answer 1

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

您不能增量计算最大值，因为您正在添加和删除。所以你最好使用专门为这个设计的数据结构。树通常是这样的。我相信BCL有SortedList和SortedSet和SortedDictionary。其中一个是基于快速树。它有最小和最大操作。

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

Bug: Add是不雅的。可以覆盖非空集合。

Answer 2

大型lock语句至少是可疑的。如果您说Keys.Max()很慢，那么更简单的改进是增量计算最大值。您只需要在删除键后刷新它:

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

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