Коллекция Concurrent с максимально быстрой возможностью добавления, удаления и поиска

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() убийца Это О (Н). Нет необходимости в словаре, если вы делаете это.

Вы не можете постепенно вычислить максимальное значение, потому что вы добавляете и удаляете. Поэтому вам лучше использовать структуру данных, которая предназначена для этого. Деревья обычно бывают. BCL имеет SortedList а также SortedSet а также SortedDictionary Я верю. Один из них был основан на быстром дереве. Он имеет минимальные и максимальные операции.

Или используйте библиотеку.NET с приоритетной очередью.

Ошибка: добавить это очень Вы можете перезаписать непустую коллекцию.

Answer 2

Большой lock Заявление по крайней мере сомнительно. Более легкое улучшение, если вы скажете, что Keys.Max() медленно, это для расчета максимального значения в порядке приращения. Вам нужно будет обновить его только после удаления ключа:

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

//...

WorstError = Math.Max(WorstError, key);

Answer 3

В итоге я решил реализовать Heap на основе двоичного дерева, как это было предложено @usr. Моя последняя коллекция была не параллельной, а синхронизированной (я использовал блокировки). Я проверил производительность мысли, и она делает работу достаточно быстро. Вот псевдокод:

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