.net - 队列与列表

Question

我目前正在使用 aList<T>作为队列（使用lst[0]then lst.removeAt(0)）来保存对象。在给定时间最多大约有 20 个项目。我意识到有一个真正的Queue<T>课程。我想知道使用类似于队列Queue<T>的行为是否有任何好处（性能、内存等）？List<T>

Answer 1

可以分析性能。尽管在这种项目很少的情况下，您可能需要运行代码数百万次才能真正获得有价值的差异。

我会这样说：Queue<T>会更明确地暴露你的意图，人们知道队列是如何工作的。

像队列一样使用的列表不是很清楚，特别是如果您有很多不必要的索引和RemoveAt(magicNumber)代码。Dequeue从代码维护的角度来看，它更具消耗性。

如果这会给您带来可衡量的性能问题，您可以解决它。不要预先解决所有潜在的性能问题。

Answer 2

简短的回答：
Queue<T>比List<T>像队列一样使用时更快。List<T>比Queue<T>像列表一样使用时更快。

长答案：
AQueue<T>对于出队操作更快，这是一个 O(1) 操作。数组后续项的整个块不会向上移动。这是可能的，因为Queue<T>不需要方便从随机位置移除，而只是从顶部移除。所以它保持了一个头部（项目被拉到的Dequeue位置）和尾部位置（项目被添加到的位置Enqueue）。另一方面，从 a 的顶部移除List<T>需要自己将每个后续项目的位置向上移动。这是 O(n) - 如果您从顶部移除，这是最坏的情况，这就是出队操作。如果您在循环中出队，则速度优势可能会很明显。

List<T>如果您需要索引访问、随机检索等，A 的性能会更高。 A必须Queue<T>完全枚举才能找到合适的索引位置（它不暴露IList<T>）。

也就是说，a Stack<T>vsList<T>更接近，推送和弹出操作没有性能差异。它们都推送到数组结构的末尾并从末尾删除（两者都是 O(1)）。

---

当然，您应该使用揭示意图的正确结构。在大多数情况下，它们的性能也会更好，因为它们是为此目的量身定制的。我相信，如果根本没有性能差异，微软就不会仅仅为了不同的语义而在框架中包含Queue<T>和。Stack<T>如果是这样的话，它会很容易扩展。想想SortedDictionary<K, V>和SortedList<K, V>，两者的作用完全相同，但仅通过性能特征来区分；他们在 BCL 中找到了一席之地。

Answer 3

Queue<T>除了类实现队列和类实现列表这一事实之外，List<T>还存在性能差异。

每次从List<T>队列中的所有元素中删除第一个元素时，都会被复制。队列中只有 20 个元素，它可能并不明显。但是，当您将下一个元素从Queue<T>没有发生此类复制的情况中出列时，这总是会更快。如果队列很长，则差异可能很大。

Answer 4

我想强调一下 HugoRune 已经指出的内容。 Queue明显快于，在此用例中List，内存访问1与nfor相比。List我有一个类似的用例，但我有数百个值，我会使用Queue它，因为它快一个数量级。

关于Queue在 之上实现的说明List：关键字是“已实现”。它不会在出队时将每个值都复制到新的内存位置，而是使用循环缓冲区。这可以在“顶部List”上完成，而不会受到直接使用的副本的惩罚List。