Loading article…
カレンダーキュー(CQ) は優先度付きキュー(各要素に優先度が関連付けられ、デキュー操作で最も優先度の高い要素が削除されるキュー) です。これは、人間が将来のイベントを日付順に並べるために使用する卓上カレンダーに似ています。離散イベントシミュレーションでは、保留中のイベントを時間順に並べる将来イベントリスト (FEL) 構造が必要です。このようなシミュレータでは、キュー管理に費やす時間が大きくなる可能性があるため、優れた効率的なデータ構造が必要です。カレンダーキュー (最適なバケットサイズ) は、平均パフォーマンスが O(1) に近づく可能性があります。カレンダーキューはバケットキューと密接に関連していますが、検索方法と動的なサイズ変更の点で異なります。
理論的には、バケットキューと同様に、カレンダーキューはリンクリストの配列で構成されます。配列内の各インデックスはバケットとも呼ばれます。バケットには幅が指定されており、そのリンクリストにはタイムスタンプがそのバケットにマッピングされるイベントが格納されます。デスクカレンダーには、1 日の幅を持つ各日に対応する 365 個のバケットがあります。各配列要素には、対応するリンクリストの先頭となる 1 つのポインタが含まれています。配列名が「month」の場合、month[11] は、その年の 12 番目の月に予定されているイベントのリストへのポインタです (ベクトルのインデックスは 0 から始まります)。したがって、完全なカレンダーは、12 個のポインタの配列と最大 12 個のリンクリストのコレクションで構成されます。カレンダーキューでは、FEL のイベントのエンキュー (キューへの追加) とデキュー (キューからの削除) はイベント時間に基づいています。
幅wのn個のバケットを持つカレンダーキューを用意します。次に、時刻tのイベントをキューに追加すると、バケットに対して操作が行われます。タイムスタンプの増加に伴い、バケット内にスケジュールされたイベントが2つ以上ある場合、カレンダーキューは現在の年と日を追跡します。次に、そのバケット内で最も早いイベントを検索し、それを取り出します。（これに対し、バケットキューは、どの要素が最も早いかを判断することなく、空でない最初のバケットから任意の要素を返すだけです。）
キュー内のイベント数がバケット数よりはるかに少ないか、はるかに多い場合、効率的に機能しません。解決策は、キューの増減に合わせてバケット数も相応に増減できるようにすることです。サイズ変更操作を簡素化するために、 CQ のNb (バケット数) は、多くの場合 2 のべき乗、つまり 100 に設定されます。;↵
バケット数は、イベント数Neが 2 Nbを超えるかNb / 2を下回るかに応じて、それぞれ 2 倍または 半分になります。Nbのサイズを変更する際には、新しい幅wも計算する必要があります。採用される新しいwは、現在のバケット位置から始まる最初の数百のイベントの平均イベント間隔をサンプリングすることによって推定されます。その後、新しいカレンダー キューが作成され、古いカレンダー内のすべてのイベントがコピーされます。
