c++ - C++ でのキューのパフォーマンス分析

Question

以下は、Robert Sedwick による C++ のアルゴリズムのキューに関するテキスト スニペットです。

保留中の作業のキューを含む多くのアプリケーションは、削除するために使用されるルールに関係なく正しく動作しますが、全体的な実行時間やその他のリソースの使用はルールに依存する場合があります。このようなアプリケーションで、多数のアイテムを含むデータ構造に対して多数の「挿入」および「削除」操作が行われる場合、パフォーマンスの違いが最も重要になります。

私の質問は、たとえば、LIFO キューを削除するためのルールがあり、キューの場合は FIFO ですが、上記の段落で述べたように、大量のアイテムの挿入にどのように関連するかです。明確な理解を得るために、上記の段落を言い換えることはできますか。

ありがとう！

Answer 1

著者が言いたいのは、単純に FIFO または LIFO キューを使用できるということですが、一部のシナリオでは、キュー内のリソースを大量に消費するアイテムに最初に取り組むアルゴリズムを使用することで、より優れたパフォーマンスを得ることができるということです。

空港を例にとってみましょう。チェックインカウンターに大量のスーツケースが入ってくる。入ってきたのと同じ順序で飛行機に保管することも (FIFO)、大きいものを最初に入れてから小さいものを保管することもできます。