Queue <T> vs List <T>

Ответ 1

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

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

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

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

Ответ 2

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

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

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

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

Конечно, вы должны использовать правильную структуру, которая раскрывает намерение. В большинстве случаев они будут работать лучше, так как они специально разработаны для этой цели. Я полагаю, что не было никакой разницы в производительности, Microsoft не включила бы Queue<T> и Stack<T> в рамки только для другой семантики. Это было бы просто легко расширяемо, если бы это было так. Подумайте о SortedDictionary<K, V> и SortedList<K, V>, оба из которых делают то же самое, но отличаются только характеристикой производительности; они находят место в BCL.

Ответ 3

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

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

Ответ 4

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

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