Calendar queue

A calendar queue (CQ) is a priority queue (queue in which every element has associated priority and the dequeue operation removes the highest priority element). It is analogous to desk calendar, which is used by humans for ordering future events by date. Discrete event simulations require a future event list (FEL) structure that sorts pending events according to their time. Such simulators require a good and efficient data structure as time spent on queue management can be significant. The calendar queue (with optimum bucket size) can approach O(1) average performance. Calendar queues are closely related to bucket queues but differ from them in how they are searched and in being dynamically resized.

Implementation

Theoretically, like a bucket queue, a calendar queue consists of an array of linked lists. Sometimes each index in the array is also referred to as a bucket. The bucket has specified width and its linked list holds events whose timestamp maps to that bucket. A desk calendar has 365 buckets for each day with a width of one day. Each array element contains one pointer that is the head of the corresponding linked list. If the array name is "month" then month[11] is a pointer to the list of events scheduled for the 12th month of the year (the vector index starts from 0). The complete calendar thus consists of an array of 12 pointers and a collection of up to 12 linked lists. In calendar queue, enqueue (addition in a queue) and dequeue (deleting from a queue) of events in FEL is based on event time.

Let the calendar queue with n buckets with w width. Then enqueue of an event with time t operates on bucket . And more than two events scheduled in the bucket according to the increased timestamp. To dequeue events from the calendar queue, it keeps track of current year and day. Then it searches for the earliest event within that bucket and dequeue it. (In contrast, a bucket queue would merely return any element from the first nonempty bucket, without determining which element in that bucket is earliest.)

Calendar queue resize operation

If the number of events in the queue is much smaller or much larger than the number of buckets, it will not function efficiently. The solution is to allow the number of buckets to correspondingly grow and shrink as the queue grows and shrinks. To simplify the resize operation, the Nb (number of buckets) in a CQ is often chosen to be the power of two, i.e., ;↵

The number of buckets is doubled or halved each time the Ne (number of events) exceeds 2Nb or decreases below Nb/2 respectively. When Nb is resized, the new width w has to be calculated as well. The new w that is adopted will be estimated by sampling the average inter-event time gap from the first few hundred events starting at the current bucket position. Thereafter, a new Calendar queue is created and all the events in the old calendar will be recopied over.

References

  • Brown, R. (October 1988), "Calendar queues: a fast priority queue implementation for the simulation event set problem", Communications of the ACM, 31 (10): 1220–1227, doi:10.1145/63039.63045, S2CID 32086497
  • Erickson, K. Bruce; Ladner, Richard E.; LaMarca, Anthony (2000), "Optimizing static calendar queues", ACM Transactions on Modeling and Computer Simulation, 10 (3): 179–214, doi:10.1145/361026.361028
  • Fujimoto, Richard M. (October 1990), "Parallel discrete event simulation", Communications of the ACM, 33 (10): 30–53, doi:10.1145/84537.84545, S2CID 15054137
  • Tan, Kah Leong; Thng, Li-Jin, "SNOOPy Calendar Queue", 2000 Winter Simulation Conference Proceedings, IEEE, doi:10.1109/wsc.2000.899756, S2CID 2982776

Read other articles:

Bulbophyllum elisae

Bulbophyllum elisae Klasifikasi ilmiah Kerajaan: Plantae (tanpa takson): Angiospermae (tanpa takson): Monocots Ordo: Asparagales Famili: Orchidaceae Genus: Bulbophyllum Spesies: Bulbophyllum elisae Nama binomial Bulbophyllum elisae(F.Muell.) Benth. 1871 Bulbophyllum elisae adalah spesies tumbuhan yang tergolong ke dalam famili Orchidaceae. Spesies ini juga merupakan bagian dari ordo Asparagales. Spesies Bulbophyllum elisae sendiri merupakan bagian dari genus Bulbophyllum.[1] Nama ilm...

 

Superior Air Parts

Artikel ini perlu diwikifikasi agar memenuhi standar kualitas Wikipedia. Anda dapat memberikan bantuan berupa penambahan pranala dalam, atau dengan merapikan tata letak dari artikel ini. Untuk keterangan lebih lanjut, klik [tampil] di bagian kanan. Mengganti markah HTML dengan markah wiki bila dimungkinkan. Tambahkan pranala wiki. Bila dirasa perlu, buatlah pautan ke artikel wiki lainnya dengan cara menambahkan [[ dan ]] pada kata yang bersangkutan (lihat WP:LINK untuk keterangan lebih lanjut...

 

Biggenden

Town in Queensland, AustraliaBiggendenQueenslandBiggenden's main streetBiggendenCoordinates25°30′41″S 152°02′46″E / 25.5113°S 152.0461°E / -25.5113; 152.0461 (Biggenden (town centre))Population657 (UCL 2021)[1]Established1889Postcode(s)4621Area218.6 km2 (84.4 sq mi)Time zoneAEST (UTC+10:00)Location 46.2 km (29 mi) SW of Childers 64.3 km (40 mi) ENE of Gayndah 84.7 km (53 mi) W of Maryborough 331&...

Guatemalan Revolution

Popular Political Revolution in Guatemala Guatemalan RevolutionDateOctober 1944 – June 1954LocationGuatemalaAlso known asThe Ten Years of SpringCause Authoritarianism and police state Dispossession of communal lands of indigenous people by the administrations of Manuel Estrada Cabrera and Jorge Ubico in favor of the United Fruit Company Large reduction in labor rights MotiveLiberal democracyLand reformOutcome Ruling junta resigns First largely free presidential and parliamentary elections h...

 

WMBW

Radio station in Chattanooga, TennesseeWMBWChattanooga, TennesseeBroadcast areaChattanooga, CrossvilleFrequency88.9 MHz (HD Radio)BrandingMoody Radio SoutheastProgrammingFormatReligious/Christian radioSubchannelsHD2: Radio Moody (Spanish Christian)HD3: Urban Praise (Urban gospel)AffiliationsMoody RadioOwnershipOwnerMoody Bible Institute(The Moody Bible Institute of Chicago)HistoryFirst air dateJuly 1, 1973[1]Former call signsWKESCall sign meaningW Moody Bible Institute WTechnical info...

 

Parco Giovanni Palatucci

Parco Giovanni PalatucciParco Tor Tre TesteL'acquedotto Alessandrino UbicazioneStato Italia LocalitàRoma IndirizzoVia di Tor Tre Teste Municipio Roma V CaratteristicheTipoParco urbano[1] Inaugurazione2003 IngressiVia Rolando Lanari, Via Davide Campari, Via Francesco Tovaglieri, Via delle Fragole Mappa di localizzazione Sito web Modifica dati su Wikidata · ManualeCoordinate: 41°52′46.47″N 12°35′05.45″E / 41.879574°N 12.584847°E41.879574; 12.58484...

Joseph McCabe

English writer and speaker on freethought For other people named Joseph McCabe, see Joseph McCabe (disambiguation). Joseph McCabeBorn12 November 1867Macclesfield, EnglandDied10 January 1955(1955-01-10) (aged 87)OccupationWriter, lecturer, priestAlma materCatholic University of Louvain Joseph Martin McCabe (12 November 1867 – 10 January 1955) was an English writer and speaker on freethought, after having been a Roman Catholic priest earlier in his life. He was one of the great mout...

 

大字 (数字)

この項目には、一部のコンピュータや閲覧ソフトで表示できない文字が含まれています（詳細）。 数字の大字（だいじ）は、漢数字の一種。通常用いる単純な字形の漢数字（小字）の代わりに同じ音の別の漢字を用いるものである。 概要 壱万円日本銀行券（「壱」が大字） 弐千円日本銀行券（「弐」が大字） 漢数字には「一」「二」「三」と続く小字と、「壱」「...

 

Lincroft, New Jersey

Lincroft redirects here. For the school in England, see Lincroft Middle School. For the Intel Atom microprocessor, see Lincroft (microprocessor). Populated place in Monmouth County, New Jersey, US Census-designated place in New Jersey, United StatesLincroft, New JerseyCensus-designated placeEntrance to Thompson Park in LincroftLocation of Lincroft in Monmouth County highlighted in red (left). Inset map: Location of Monmouth County in New Jersey highlighted in orange (right).LincroftLocation i...

KPEJ-TV

Fox affiliate in Odessa, Texas KPEJ-TVOdessa–Midland, TexasUnited StatesCityOdessa, TexasChannelsDigital: 23 (UHF)Virtual: 24BrandingFox 24; Fox 24 NewsProgrammingAffiliations24.1: Foxfor others, see § SubchannelsOwnershipOwnerMission Broadcasting, Inc.OperatorNexstar Media Group via SSASister stationsKMIDHistoryFoundedDecember 26, 1984First air dateJune 16, 1986 (37 years ago) (1986-06-16)Former call signsKPEJ (1986–2009)Former channel number(s)Analog: 24 (UHF, 1986...

 

Democrats for Andorra

Political party in Andorra Democrats for Andorra Demòcrates per AndorraAbbreviationDAPresidentXavier Espot Zamora[1]FounderAntoni MartíFounded22 February 2011[2]Preceded byReformist CoalitionHeadquartersC/Babot Camp, 13 Andorra la VellaIdeologyLiberal conservatism[3]Political positionCentre-right[4]European affiliationAlliance of Liberals and Democrats for Europe[5][6]ColoursOrangeGeneral Council14 / 28Websitehttp://www.democrate...

 

Toko Tio Tek Hong

Toko Tio Tek HongToko Tio Tek Hong pada tahun 2011Informasi umumJenisTokoGaya arsitekturArsitektur rasionalis, IndiesLokasiJakarta Pusat, DKI Jakarta, IndonesiaAlamatJl. Pintu Air RayaKoordinatKoordinat: 6°10′02″S 106°49′54″E / 6.167141°S 106.831749°E / -6.167141; 106.831749Ketinggian6 m (20 ft)[1]Diresmikan1902 Toko Tio Tek Hong adalah salah satu toserba modern pertama di Hindia Belanda (kini Indonesia). Toko ini didirikan pada tahun 1902...

Final Piala Dunia Antarklub FIFA 2013

Final Piala Dunia Antarklub FIFA 2013TurnamenPiala Dunia Antarklub FIFA 2013 Bayern München Raja Casablanca 2 0 Tanggal21 Desember 2013 (2013-12-21)StadionStade de Marrakech, MarrakeshPemain Terbaik Franck Ribéry (Bayern München)WasitSandro Ricci (Brasil)Penonton37.774CuacaMalam cerah13 °C (55 °F)Kelembapan 65%← 2012 2014 → Final Piala Dunia Antarklub FIFA 2013 adalah pertandingan babak final dari Piala Dunia Antarklub FIFA 2013, suatu turnamen sepak bola yang ...

 

Australian Championships 1959

Australian Championships 1959Sport Tennis Data16 gennaio - 26 gennaio Edizione47a CategoriaGrande Slam (ITF) LocalitàAdelaide, Australia CampioniSingolare maschile Alex Olmedo Singolare femminile Mary Carter Reitano Doppio maschile Rod Laver / Bob Mark Doppio femminile Renee Schuurman Haygarth / Sandra Reynolds Price Doppio misto Sandra Reynolds Price / Bob Mark 1958 1960 Gli Australian Championships 1959 (conosciuto oggi come Australian Open) sono stati la 47ª edizione degli Australian Cha...

 

Distretto di Bijapur

Questa voce sull'argomento distretti dell'India è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Distretto di BijapurdistrettoBijapur District LocalizzazioneStato India Stato federato Karnataka DivisioneBelgaum AmministrazioneCapoluogoBijapur TerritorioCoordinatedel capoluogo16°49′59.88″N 75°42′00″E16°49′59.88″N, 75°42′00″E (Distretto di Bijapur) Superficie10 517 km...

ブロンスキ・ビート

ブロンスキ・ビートBronski Beat スティーヴ・ブロンスキ、ジミー・ソマーヴィル、ラリー・スタインバチェク（1985年）基本情報出身地 イングランド ロンドンジャンル シンセポップ[1]、ニュー・ウェイヴ[2]、Hi-NRG[3]活動期間 1983年 - 1995年2016年 - 2018年レーベル ロンドンレコード共同作業者 コミュナーズ（英語版）旧メンバー スティーヴ・ブロンスキ ジ...

 

MS-DOS Editor

MS-DOS Editor MS-DOS Editorと類似したインターフェイスを持つFreeDOS Editの画面開発元 マイクロソフト初版 1991年6月 (33年前) (1991-06) 最新版 2.0.026 / 1995年 (29年前) (1995)対応OS MS-DOS, Windows種別 テキストエディタライセンス プロプライエタリ EULAテンプレートを表示 MS-DOS Editor (edit) はCUIベースのテキストエディタで、MS-DOS バージョン5以降および32ビット版Windowsに付属...

 

Voile aux Jeux olympiques de 1900

Voile aux Jeux olympiques de 1900 Généralités Sport Voile Éditions 1re Lieu(x) France Participants ? Épreuves 10 Navigation Londres 1908 modifier Voiles à Meulan, pour l'exposition universelle de 1900. Le bassin des courses de yachts de Meulan. Œuvre de Belloc, en argent dû à Linzerer, le trophée de la 2ème série de voile, pour Scotia (½ – 1 tonneau), de John Gretton et Lorne Currie. Crabe II, le yacht du comte Chabannes La Palice, médaille d'argent ½ – 1 tonneau (Baudrier...

Gluhareff Pressure Jet

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Gluhareff Pressure Jet – news · newspapers · books · scholar · JSTOR (December 2012) (Learn how and when to remove this message) The Gluhareff Pressure Jet (or tip jet) is a type of jet engine that, like a valveless pulse jet, has no moving parts. It was invent...

 

Curricle

Two-wheeled carriage drawn by two horses For the small, lightweight boat, see Coracle. Curricle Curricle, oil by John Cordrey (1806) A curricle is a light two-wheeled carriage drawn by two horses abreast. Usually open with a falling hood, it seats two people, plus a liveried groom on a seat or small platform between the rear springs—whose weight might be required to properly balance the carriage. Curricles are harnessed with a pole between the horses, and have an iron crossbar (the curricle...