Вопрос по list, .net, performance – Очередь против списка

42

Я в настоящее время используюList<T> как очередь (используйтеlst[0] затемlst.removeAt(0)) держать предметы. В данный момент может быть максимум 20 элементов. Я понял, что был фактическийQueue<T> учебный класс. Мне интересно, есть ли какая-либо выгода (производительность, память и т. Д.) В использованииQueue<T> черезList<T> действуя как очередь?

Вы не можете получить доступ к очереди по индексу. Вы должны использовать записи, которые вы удаляете, и вы не можете их вернуть. Peek не является решением, однако Count & gt; 0 может быть. Jay
Это зависит от вашего сценария использования, если это имеет значение. lst.RemoveAt (0) заставит список переместить все элементы, тогда как очередь умнее. Теоретически Queue лучше, но чтобы быть уверенным, вы должны измерить свой вариант использования. Alois Kraus
Probably нет, если вы не используете более 20 предметов. Но вы можете измерить это, используя класс StopWatch. alexn

Ваш Ответ

4   ответа
35

Short answer:
Queue<T> быстрее чемList<T> когда он используется как очередь.List<T> быстрее чемQueue<T> когда используется как список.

Long answer:
Queue<T> быстрее для операции удаления из очереди, которая является операцией O (1). Весь блок последующих элементов массива не перемещается вверх. Это возможно, потому чтоQueue<T> не нужно облегчать удаление со случайных позиций, а только сверху. Таким образом, он поддерживает голову (из которой предмет натягивается наDequeue) и положение хвоста (к которому добавляется элементEnqueue). С другой стороны, удаление из верхней частиList<T> требует от себя сдвигать позиции каждого последующего пункта на один. Это O (n) - наихудший случай, если вы удаляете сверху, что является операцией удаления очереди. Преимущество в скорости может быть заметно, если вы выключаете в цикле.

List<T> более производительный, если вам нужен индексированный доступ, случайный поиск и т. д. AQueue<T> придется полностью перечислить, чтобы найти подходящую позицию индекса (она не раскрываетIList<T>).

Тем не менее,Stack<T> противList<T> гораздо ближе, нет никакой разницы в производительности в операциях нажатия и выталкивания. Они оба выдвигаются в конец и удаляют из конца структуры массива (обе из которых O (1)).

Of course you should use the correct structure that reveals the intent. В большинстве случаев они будут работать лучше, так как они сделаны специально для этой цели. Я полагаю, что если бы не было разницы в производительности, Microsoft бы не включилаQueue<T> а такжеStack<T> в рамках просто другой семантики. Это было бы просто легко расширить, если бы это было так. Подумать оSortedDictionary<K, V> а такжеSortedList<K, V>оба из которых делают то же самое, но отличаются только характеристикой производительности; они находят место в BCL.

@AlexanderRyanBaggett Это не должно иметь никакого значения (моя лучшая догадка), но вы должны действительно использовать структуру, которая лучше раскрывает намерения. Они оба рассказывают разные истории разработчику.
Как насчет ситуации с адд-хэви?
0

Queue значительно быстрее, чемListгде доступ к памяти1 противn заList в этом случае использования. У меня есть похожий вариант использования, но у меня есть сотни значений, и я буду использоватьQueue потому что это на порядок быстрее.

Заметка оQueue реализуется поверхList: ключевое слово "реализовано". Он не копирует каждое значение в новую ячейку памяти после удаления из очереди, а использует циклический буфер. Это можно сделать в верхней частиList& Quot; без штрафных санкций за использование копийList влечет за собой.

Он не может использовать кольцевой буфер, если емкость не имеет фиксированного размера.
68

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

Я скажу это:Queue<T> выставит вашintent Более точно, люди знают, как работает очередь.

Список, используемый как очередь, не так ясен, особенно если у вас много ненужной индексации иRemoveAt(magicNumber) код.Dequeue это намного более потребимо с точки зрения обслуживания кода.

Если это приводит к измеримым проблемам с производительностью, вы можете решить их. Не обращайтесь к каждомуpotential вопрос производительности заранее.

@JohnIsaiahCarmona: Потому что использование алгоритма O (n ^ 2) вместо алгоритма O (n) на 10 элементов не является проблемой производительности.
Хорошо, достаточно справедливо.
Почему мы не должны заранее решать все потенциальные проблемы с производительностью?
@JohnIsaiahCarmona Потому что вы попадаете в ловушку микрооптимизации, когда вам это не нужно. Мое мнение обо всем этом заключается в том, что мы должны остерегаться очевидных кланов, но о тех нескольких миллисекундах между А и В не стоит беспокоиться, пока они не станут проблемой. Поддерживаемый, читаемый код в большинстве случаев важнее производительности.
@JohnIsaiahCarmona Кроме того, большинство потенциальных проблем с производительностью никогда по-настоящему не осознаются, поэтому они просто остаютсяpotential проблемы.
10

Queue<T> класс реализует очередь иList<T> Класс реализации списка есть разница в производительности.

Каждый раз, когда вы удаляете первый элемент изList<T> все элементы в очереди копируются. При наличии только 20 элементов в очереди это может быть незаметно. Однако, когда вы удаляете следующий элемент изQueue<T> такого копирования не происходит, и это всегда будет быстрее. Если очередь длинная, разница может быть значительной.

Похожие вопросы