.NET очередь ElementAt производительность

Question

У меня проблемы с частями моего кода:

    private void UpdateOutputBuffer()
    {
        T[] OutputField = new T[DisplayedLength];

        int temp = 0;
        int Count = HistoryQueue.Count;
        int Sample = 0;

        //Then fill the useful part with samples from the queue
        for (temp = DisplayStart; temp != DisplayStart + DisplayedLength && temp < Count; temp++)
        {
            OutputField[Sample++] = HistoryQueue.ElementAt(Count - temp - 1);
        }

        DisplayedHistory = OutputField;
    }

Это занимает большую часть времени в программе. Количество элементов в HistoryQueue составляет 200 000+. Может ли это быть из-за того, что очередь в .NET реализована внутри как связанный список?

Что может быть лучше для этого? По сути, класс должен действовать как FIFO, который начинает отбрасывать элементы с ~ 500k выборок, и я могу выбрать элементы DisplayedLength и поместить их в OutputField. Я думал о написании своей собственной очереди, которая будет использовать кольцевой буфер.

Код работал нормально для подсчета меньших значений. Отображаемая длина составляет 500.

Спасибо,

David

Answer 1

В очереди нет метода ElementAt.Я предполагаю, что вы получаете это через Linq, и он просто выполняет принудительную итерацию по n элементам, пока не достигнет желаемого индекса.Это, очевидно, будет замедляться, поскольку коллекция становится больше.Если ElementAt представляет общий шаблон доступа, выберите структуру данных, к которой можно получить доступ через индекс, например Array.

Answer 2

Да, проблема связанного списка почти наверняка является проблемой.Есть причина, по которой Queue<T> не реализует IList<T> :) (Сказав это, я считаю, Stack<T> реализован с использованием массива, и это все еще не реализует IList<T>. Он может обеспечить эффективный произвольный доступ, но это не так.)

Я не могу легко определить, какую часть очереди вы пытаетесь отобразить, но я сильно подозреваю, что вы могли бы упростить метод и сделайте его более эффективным, используя что-то вроде:

T[] outputField = HistoryQueue.Skip(...) /* adjust to suit requirements... */
                              .Take(DisplayedLength)
                              .Reverse()
                              .ToArray();

По-прежнему придется пропускать огромное количество предметов по отдельности, но, по крайней мере, это придется делать только один раз.

Думал ли ты об использовании LinkedList<T> напрямую?Это значительно упростило бы чтение элементов из конца списка.

Построение собственной ограниченной очереди с использованием кольцевого буфера, разумеется, не будет трудным и может быть лучшим решением.в долгосрочной перспективе.

Answer 3

Абсолютно неправильная структура данных для использования здесь. ElementAt - это O (n), что делает ваш цикл O (n ² ). Вы должны использовать что-то другое вместо очереди.

Answer 4

Если вам нужно иметь возможность выдвигать / выдвигать данные с любого конца и имеют индексированный доступ, вам действительно нужна реализация Deque (форма с несколькими массивами).Хотя в BCL нет реализации, есть много сторонних (для начала, при необходимости, вы можете реализовать свою позже).

Answer 5

Лично я не думаю, что вы ищете очередь, но ваша модель доступа еще хуже.Используйте итераторы, если вы хотите последовательный доступ:

foreach(var h in HistoryQueue.Skip(DisplayStart).Take(DisplayedLength).Reverse())
    // work with h