キュー<T>対リスト<T>

Question

私は現在、オブジェクトを保持するためにList<T>をキューとして使用しています（lst[0]からlst.removeAt(0)）。ある時点で最大約20個のアイテムがあります。実際のQueue<T>クラスがあることに気付きました。キューのように働いてList<T>の上にQueue<T>を使用する利点（パフォーマンス、メモリなど）があるのでしょうか？

Answer 1

パフォーマンスをプロファイリングすることができます。このような数少ないアイテムでは、価値のある違いを実際に得るために何百万回もコードを実行する必要があります。

私はこれを言うだろう：Queue<T>は、より明示的に意図を公開します、人々は、キューがどのように動作するかを知っています。

キューと同じように使用されているリストには、不要なインデックスとRemoveAt(magicNumber)コードの多くを持っている場合は特に、として明確ではありません。 Dequeueは、コード管理の観点からはるかに多くの消耗品です。

これは、あなたに測定可能なパフォーマンスの問題を与えた場合、あなたはそれに対処することができます。 の可能性があるすべてのパフォーマンス問題を解決しないでください。

Answer 2

Queue<T>クラスがキューを実装しており、List<T>クラスがリストを実装していることに加えて、パフォーマンスの違いがあります。

するたびに、キュー内のすべての要素がコピーされList<T>から最初の要素を削除します。キューには20個の要素しかなく、目立たないことがあります。しかし、次の要素をQueue<T>からデキューすると、そのようなコピーは行われず、常に高速になります。キューが長い場合は、その差が大きくなる可能性があります。

Answer 3

私はHugoRuneはすでに指摘したものを強調したかったです。キューは、Listよりもはるかに高速です。この場合、メモリアクセスは1対nです。私は同様のユースケースを持っていますが、何百もの値を持っています。

キューがリストの一番上に実装さについての注意：キー「が実現」されます。デキュー時に、循環バッファを使用する代わりに、すべての値を新しいメモリ位置にコピーしません。これは、Listの使用を指示するコピーのペナルティなしで、 "Top of List"で行うことができます。

Answer 4

短い答えは：それはキューのように使われているとき
Queue<T>List<T>よりも高速です。リストのように使用すると、List<T>はQueue<T>より高速です。

長い答え：
Queue<T>が速くO（1）操作される操作を、デキューするためのものです。配列の後続項目のブロック全体が上に移動しません。これは、Queue<T>がランダムな位置からの除去を容易にする必要はなく、上部からの除去のみを容易にする必要があるため可能です。したがって、頭部（アイテムはDequeueに引っ張られます）と末尾の位置（アイテムはEnqueueに追加されます）が維持されます。一方、List<T>の先頭から削除するには、それ以降のすべての項目の位置を1つ上にシフトする必要があります。これはO（n）です - 最悪の場合、デキュー操作である上から削除している場合です。あなたがループからデキューしているなら、速度の利点は目立つことがあります。

List<T>は、（それがIList<T>を公開していません）を使用すると、インデックス付きアクセス、ランダム検索などが必要な場合Queue<T>は、適切なインデックス位置を見つけるために、完全に列挙する必要がありますよりパフォーマンスです。

つまり、Stack<T>とList<T>の方がはるかに近く、プッシュ操作とポップ操作ではパフォーマンスの違いはありません。彼らは、配列構造（どちらもO（1）です）の終わりから終わりに移動し、配列構造の終わりから削除します。

---

もちろん、意図を明らかにする正しい構造を使用する必要があります。ほとんどの場合、彼らは目的に合わせて調整されているため、より良いパフォーマンスを発揮します。私はパフォーマンスの違いが全くないと考えていますが、MicrosoftはQueue<T>とStack<T>を単に異なるセマンティクスのためのフレームワークに含めなかったでしょう。そうであれば、簡単に拡張することができました。 SortedDictionary<K, V>とSortedList<K, V>については、どちらもまったく同じですが、パフォーマンス特性のみで区別されます。彼らはBCLに場所を見つける。