قائمة انتظار التقويم

قائمة انتظار التقويم (CQ) هي قائمة انتظار ذات أولوية (قائمة انتظار لكل عنصر فيها أولوية مرتبطة به، وتؤدي عملية الإزالة إلى حذف العنصر ذي الأولوية الأعلى). وهي تُشابه التقويم المكتبي الذي يستخدمه البشر لترتيب الأحداث المستقبلية حسب التاريخ. تتطلب محاكاة الأحداث المنفصلة بنية قائمة أحداث مستقبلية (FEL) تُرتّب الأحداث المُعلقة وفقًا لوقتها. تتطلب هذه المحاكيات بنية بيانات جيدة وفعّالة نظرًا لأن الوقت المُستغرق في إدارة قائمة الانتظار قد يكون كبيرًا. يمكن لقائمة انتظار التقويم (مع حجم الحاوية الأمثل) أن تقترب من أداء O(1) المتوسط. ترتبط قوائم انتظار التقويم ارتباطًا وثيقًا بقوائم انتظار الحاويات ، لكنها تختلف عنها في طريقة البحث فيها وفي إمكانية تغيير حجمها ديناميكيًا.

نظريًا، كما هو الحال في قائمة الانتظار ذات الدلو، تتكون قائمة انتظار التقويم من مصفوفة من القوائم المتصلة . يُشار أحيانًا إلى كل عنصر في المصفوفة باسم "دلو". لكل دلو عرض محدد، وتحتوي قائمته المتصلة على الأحداث التي يتوافق طابعها الزمني مع ذلك الدلو. يحتوي التقويم المكتبي على 365 دلوًا لكل يوم، بعرض يوم واحد. يحتوي كل عنصر في المصفوفة على مؤشر واحد يمثل رأس القائمة المتصلة المقابلة. إذا كان اسم المصفوفة "month"، فإن month[11] هو مؤشر إلى قائمة الأحداث المُجدولة للشهر الثاني عشر من السنة (يبدأ فهرس المتجه من 0). بالتالي، يتكون التقويم الكامل من مصفوفة من 12 مؤشرًا ومجموعة من 12 قائمة متصلة كحد أقصى. في قائمة انتظار التقويم، تعتمد عملية إضافة الأحداث إلى قائمة الانتظار (enqueue ) وحذفها منها (dequeue) في لغة FEL على وقت الحدث.

لنفترض أن لدينا قائمة انتظار تقويم تحتوي على n خانة بعرض w . عندئذٍ، تتم إضافة حدث في وقت t إلى قائمة الانتظار في الخانة w.${\displaystyle {\frac {t}{w}}\mod n}$ويتم جدولة أكثر من حدثين في المجموعة وفقًا لزيادة الطابع الزمني. ولإزالة الأحداث من قائمة انتظار التقويم، يتم تتبع السنة واليوم الحاليين. ثم يتم البحث عن أقدم حدث داخل تلك المجموعة وإزالته. (على النقيض من ذلك، فإن قائمة انتظار المجموعات تُعيد أي عنصر من أول مجموعة غير فارغة، دون تحديد أي عنصر هو الأقدم في تلك المجموعة).

إذا كان عدد الأحداث في قائمة الانتظار أصغر بكثير أو أكبر بكثير من عدد الحاويات، فلن تعمل بكفاءة. الحل هو السماح لعدد الحاويات بالنمو والانكماش تبعًا لنمو قائمة الانتظار وانكماشها. ولتبسيط عملية تغيير الحجم، غالبًا ما يُختار عدد الحاويات ( Nb ) في قائمة انتظار التحكم (CQ) ليكون قوة للعدد اثنين، أي:${\displaystyle Nb=2^{n}}$;↵

يتضاعف عدد الحاويات أو يُخفض إلى النصف كلما تجاوز عدد الأحداث ( Ne ) ضعف Nb أو انخفض إلى أقل من Nb /2 على التوالي. عند تغيير حجم Nb ، يجب حساب العرض الجديد (w) . يُقدّر العرض الجديد (w) بأخذ عينة من متوسط ​​الفاصل الزمني بين الأحداث من أول بضع مئات من الأحداث بدءًا من موضع الحاوية الحالي. بعد ذلك، تُنشأ قائمة انتظار تقويم جديدة، وتُنسخ جميع الأحداث من التقويم القديم.

• براون، ر. (أكتوبر 1988)، "طوابير التقويم: سريع${\displaystyle O(1)}$"تنفيذ قائمة انتظار ذات أولوية لمشكلة مجموعة أحداث المحاكاة"، مجلة اتصالات ACM ، 31 (10): 1220-1227 ، doi : 10.1145/63039.63045 ، S2CID 32086497 
• إريكسون، ك. بروس؛ لادنر، ريتشارد إي.؛ لاماركا، أنتوني (2000)، "تحسين قوائم انتظار التقويم الثابتة"، معاملات ACM في النمذجة ومحاكاة الحاسوب ، 10 (3): 179-214 ، doi : 10.1145/361026.361028
• فوجيموتو، ريتشارد م. (أكتوبر 1990)، "محاكاة الأحداث المنفصلة المتوازية" ، اتصالات رابطة مكائن ​​الحوسبة ، 33 (10): 30-53 ، doi : 10.1145/84537.84545 ، S2CID 15054137 
• تان، كاه ليونغ؛ ثنغ، لي-جين (2000)، "قائمة انتظار تقويم سنوبي"، وقائع مؤتمر محاكاة الشتاء لعام 2000 ، المجلد  1، IEEE، الصفحات 487-495 ، doi : 10.1109/wsc.2000.899756 ، ISBN  0-7803-6579-8، S2CID 2982776