Cola de calendario

Una cola de calendario (CQ) es una cola de prioridad (en la que cada elemento tiene una prioridad asociada y la operación de extracción elimina el elemento de mayor prioridad). Es análoga a un calendario de escritorio, que las personas utilizan para ordenar eventos futuros por fecha. Las simulaciones de eventos discretos requieren una estructura de lista de eventos futuros (FEL) que ordene los eventos pendientes según su tiempo. Dichos simuladores requieren una estructura de datos buena y eficiente , ya que el tiempo dedicado a la gestión de la cola puede ser significativo. La cola de calendario (con un tamaño de cubeta óptimo) puede alcanzar un rendimiento promedio cercano a O(1). Las colas de calendario están estrechamente relacionadas con las colas de cubeta , pero se diferencian de ellas en la forma en que se realizan las búsquedas y en que se redimensionan dinámicamente.

Teóricamente, al igual que una cola de cubetas, una cola de calendario consta de una matriz de listas enlazadas . A veces, cada índice de la matriz también se denomina cubeta. La cubeta tiene un ancho especificado y su lista enlazada contiene eventos cuya marca de tiempo se corresponde con esa cubeta. Un calendario de escritorio tiene 365 cubetas para cada día con un ancho de un día. Cada elemento de la matriz contiene un puntero que es la cabeza de la lista enlazada correspondiente. Si el nombre de la matriz es "mes", entonces mes[11] es un puntero a la lista de eventos programados para el duodécimo mes del año (el índice del vector comienza en 0). El calendario completo consta, por lo tanto, de una matriz de 12 punteros y una colección de hasta 12 listas enlazadas. En la cola de calendario, la encolada (adición a una cola ) y la desencolada (eliminación de una cola) de eventos en FEL se basan en el tiempo del evento.

Consideremos una cola de calendario con n cubetas de ancho w . Entonces, la inserción de un evento con tiempo t opera en la cubeta.${\displaystyle {\frac {t}{w}}\mod n}$Además, se programan más de dos eventos en el cubo según la marca de tiempo incrementada. Para extraer eventos de la cola del calendario, se realiza un seguimiento del año y el día actuales. Luego, se busca el evento más antiguo dentro de ese cubo y se extrae. (En cambio, una cola de cubos simplemente devolvería cualquier elemento del primer cubo no vacío, sin determinar cuál es el más antiguo).

Si el número de eventos en la cola es mucho menor o mucho mayor que el número de cubetas, no funcionará de manera eficiente. La solución es permitir que el número de cubetas crezca y se reduzca correspondientemente a medida que la cola crece y se reduce. Para simplificar la operación de redimensionamiento, el Nb (número de cubetas) en una CQ a menudo se elige como una potencia de dos, es decir,${\displaystyle Nb=2^{n}}$;↵

El número de cubetas se duplica o se reduce a la mitad cada vez que Ne (número de eventos) supera 2 Nb o disminuye por debajo de Nb /2, respectivamente. Al redimensionar Nb , también se debe calcular el nuevo ancho w . El nuevo valor de w se estima muestreando el intervalo de tiempo promedio entre eventos de los primeros cientos de eventos a partir de la posición actual de la cubeta. Posteriormente, se crea una nueva cola de calendario y se copian todos los eventos del calendario anterior.

• Brown, R. (octubre de 1988), "Colas de calendario: una rápida${\displaystyle O(1)}$Implementación de cola de prioridad para el problema del conjunto de eventos de simulación", 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. (octubre de 1990), "Simulación paralela de eventos discretos" , Communications of the ACM , 33 (10): 30–53 , doi : 10.1145/84537.84545 , S2CID 15054137 
• Tan, Kah Leong; Thng, Li-Jin (2000), "SNOOPy Calendar Queue", Actas de la Conferencia de Simulación de Invierno de 2000 , vol.  1, IEEE, pp. 487–495 , doi : 10.1109/wsc.2000.899756 , ISBN  0-7803-6579-8, S2CID 2982776