c# - 并发收集以最快的速度添加、删除和查找最高的

Question

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

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

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

 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() 是 killer 。那是 O(N)。如果你这样做，就不需要字典。

您无法增量计算最大值，因为您要添加和删除。因此，您最好使用为此而设计的数据结构。树通常是。我相信 BCL 有 SortedList 和 SortedSet 和 SortedDictionary 。其中一个是基于一棵快树。它有最小和最大操作。

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

Bug:Add 很活泼。您可能会覆盖非空集合。