Kolejka kalendarza
Kolejka kalendarza (CQ) to kolejka priorytetowa (kolejka, w której każdy element ma przypisany priorytet, a operacja usuwania z kolejki usuwa element o najwyższym priorytecie). Jest to analogiczne do kalendarza biurkowego, który jest używany przez ludzi do porządkowania przyszłych wydarzeń według dat. Dyskretne symulacje zdarzeń wymagają struktury listy przyszłych zdarzeń (FEL), która sortuje oczekujące zdarzenia według ich czasu. Takie symulatory wymagają dobrej i wydajnej struktury danych, ponieważ czas poświęcony na zarządzanie kolejką może być znaczny. Kolejka kalendarza (z optymalnym rozmiarem zasobnika) może zbliżyć się do średniej wydajności O(1). Kolejki kalendarza są blisko spokrewnione z kolejkami zasobników , ale różnią się od nich sposobem wyszukiwania i dynamiczną zmianą rozmiaru.
Realizacja
Teoretycznie, podobnie jak kolejka zasobnika, kolejka kalendarza składa się z tablicy połączonych list . Czasami każdy indeks w tablicy jest również nazywany zasobnikiem. Zasobnik ma określoną szerokość, a połączona lista zawiera zdarzenia, których sygnatura czasowa odpowiada temu zasobnikowi. Kalendarz biurkowy ma 365 kubeczków na każdy dzień o szerokości jednego dnia. Każdy element tablicy zawiera jeden wskaźnik , który jest nagłówkiem odpowiedniej połączonej listy. Jeśli nazwą tablicy jest „miesiąc”, to miesiąc [11] jest wskaźnikiem do listy wydarzeń zaplanowanych na 12. miesiąc roku (indeks wektora zaczyna się od 0). Kompletny kalendarz składa się zatem z tablicy 12 wskaźników i zbioru do 12 połączonych list. W kolejce kalendarza kolejkowanie (dodawanie do kolejki ) i usuwanie z kolejki (usuwanie z kolejki) wydarzeń w FEL odbywa się na podstawie czasu wydarzenia.
Niech kalendarz stanie w kolejce z n przedziałami o szerokości w . Następnie kolejkowanie zdarzenia z czasem t działa na wiadrze . I więcej niż dwa zdarzenia zaplanowane w zasobniku zgodnie ze zwiększonym znacznikiem czasu. Aby usunąć wydarzenia z kolejki kalendarza, śledzi bieżący rok i dzień. Następnie wyszukuje najwcześniejsze zdarzenie w tym segmencie i usuwa je z kolejki. (W przeciwieństwie do tego, kolejka kubełkowa zwróciłaby jedynie dowolny element z pierwszego niepustego zasobnika, bez określania, który element w tym zasobniku jest najwcześniejszy).
Operacja zmiany rozmiaru kolejki kalendarza
Jeśli liczba zdarzeń w kolejce jest znacznie mniejsza lub znacznie większa niż liczba zasobników, nie będzie działać wydajnie. Rozwiązaniem jest umożliwienie odpowiedniego zwiększania i zmniejszania liczby segmentów w miarę wzrostu i zmniejszania się kolejki. Aby uprościć operację zmiany rozmiaru, Nb (liczba kubełków) w CQ jest często wybierana jako potęga dwóch, tj. ; ↵
Liczba segmentów jest podwajana lub zmniejszana o połowę za każdym razem, gdy Ne (liczba zdarzeń) przekracza odpowiednio 2 Nb lub spada poniżej Nb /2. Po zmianie rozmiaru Nb należy również obliczyć nową szerokość w . Przyjęte nowe w zostanie oszacowane przez próbkowanie średniej przerwy między zdarzeniami z pierwszych kilkuset zdarzeń, począwszy od bieżącej pozycji przedziału. Następnie tworzona jest nowa kolejka kalendarza, a wszystkie wydarzenia ze starego kalendarza zostaną ponownie skopiowane.
- : szybka implementacja kolejki priorytetowej dla problemu z zestawem zdarzeń symulacji”, ACM , 31 10 ): 1220– 1227, doi : 10.1145/63039.63045 , S2CID 32086497
- Erickson, K. Bruce; Ladner, Richard E.; LaMarca, Anthony (2000), „Optymalizacja kolejek kalendarza statycznego”, ACM Transactions on Modeling and Computer Simulation , 10 (3): 179–214, doi : 10.1145/361026.361028
- Fujimoto, Richard M. (październik 1990), „Równoległa symulacja zdarzeń dyskretnych” , 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
