¿Qué es una cola de calendario?

Question

Estoy trabajando en la construcción de un simulador de eventos discretos. Wikipedia mencionó que hay varias colas de prioridad de propósito general que son buenas para su uso en los DES. Específicamente, menciona que una cola de calendario es una buena estructura. Encontré un pdf (desde 1988) que menciona Calendar Queues, pero en su mayor parte no puedo encontrar nada más sobre ellos. ¿Le importaría a alguien explicar qué son las Calendar Queue, cómo se usan y dónde podría encontrar una implementación de muestra?

Answer 1

Una búsqueda en Google encuentra

Estudio de anchos de cubo optimizados en cola Calendario de eventos discretos Simulador

http://pioneer.netserv.chula.ac.th/~achaodit/paper5.pdf

que describe las colas del calendario en la sección 2.

Answer 2

definiciones de NIST:

Una rápida implementación cola de prioridad que tiene N cubos cada uno con anchura w, o cubriendo w tiempo. Un elemento con prioridad p más que la corriente entra en el cubo (p/p)% N. Elija N y w para tener pocos elementos en cada cubo. Mantenga los artículos clasificados dentro de cubos. Doble o reduzca a la mitad N y cambie w si la cantidad de elementos crece o se reduce mucho.

Paul E. Black, "cola de calendario", en el Diccionario de Algoritmos y Estructuras de Datos [en línea], Vreda Pieterse y Paul E. Black, eds. 24 de enero de 2005. (consultado el 10/03/2014) Disponible a partir de: http://www.nist.gov/dads/HTML/calendarQueue.html

Answer 3

Sí, Brown 1988 es el primer documento que conozco para describir las colas del calendario, aunque Brown me varios autores que le precedieron. A continuación hay una bibliografía relativamente completa de la literatura de la cola del calendario junto con mis notas en cada papel. Déjame un comentario si deseas copias de cualquiera de las publicaciones.

• Vaucher 1975 Comparación de los algoritmos de la lista de eventos. Presenta tres nuevos algoritmos también. Inspired Brown1988.
• Henricksen 1977 Lista de eventos algoritmo - se adapta a los tiempos de intervalo y se realiza bien con una serie de distribuciones, basado en Vaucher y Duval
• Ulrich 1978 Brown1988 afirma que esto es O (1), a excepción de la lista de desbordamiento
• Jones 1986 Compara prioridades colas, tiene una primera versión de una cola calendario
• Brown 1988 presenta el Calendario de colas [alias: disciplina Ordenado Calendario cola]
• Davison 1989 descubre el mismo, menciona algunas mejoras importantes, Brown reconoce las mejoras en el misma letra y tiene algunos pensamientos propios. Davison sugiere que Jones 1986 ha ofrecido algunas mecánicas de calendario valiosas
• Ronngren 1991 The Lazy Queue. Una cola de calendario que tiene un futuro cercano, lejano y muy lejano: esto permite la clasificación retrasada, lo que acelera considerablemente las pruebas.
• Steinman 1994 Event Horizon. Los eventos generados tienen una cierta distribución de probabilidad cuando ocurren. Usemos esto para determinar qué se debe ordenar. Permitir la simulación paralela
• Steinman 1996 Event Horizon Part 2. Aplica Steinman1994 a la gestión de listas de eventos. Modifica otras estructuras de datos para usar en CQ.
• Ronngren 1997 Comparación de muchas colas de calendario diferentes. Lazy Queue funciona bien, pero Brown1988 con frecuencia tiene un mejor rendimiento. LazyQ y SCQ tienen el peor rendimiento en el peor de los casos, Skew Heap y Sply Tree tienen el mejor peor de los casos.
• Oh 1997 Dynamic Lazy Calendar Queue. Mejora el rendimiento del CQ convencional en distribuciones de eventos desiguales
• Oh 1999 Dynamic Calendar Queue. Funciona bien con distribuciones desiguales
• Cazzolla 1998 Implementación en Java de Lazy Queue con análisis (no es un trabajo académico).
• Tan 2000 SNOOPy: Mejorado estadísticamente con el parámetro de funcionamiento óptimo CQ. Utiliza pruebas estadísticas para hacer un cubo de ebtter. Funciona hasta 100 veces más rápido que DCQ y CQ en ciertos escenarios
• Tesis Hui tesis de Licenciatura describir muchos más detalles del papel Hui 2002 junto con los pros y los contras de las implementaciones de cola de otro calendario
• Hui 2002 Eventos futuros no es necesario ser ordenado ahora mismo; en consecuencia, el tamaño de la cola de prioridad adecuada puede ser limitado, lo que reduce la sobrecarga de redimensionamiento.
• Goh 2003 MList. Las listas enlazadas de múltiples niveles eliminan las operaciones de cambio de tamaño. Se muestra experimentalmente que es al menos 100% más rápido que Calendar Queue, Dynamic CQ, SNOOPy CQ, Dynamic Lazy CQ de 2 niveles y Lazy Queue de 3 niveles
• Siangsukone 2003 Anchos optimizados de cubetas en CQ. Demuestra que el ancho del cucharón puede tener efectos significativos en el rendimiento.
• Goh 2004 DSplay. Elimine costosas operaciones de cambio de tamaño. Al menos 100% más rápido que otras colas de calendario.
• Tang 2005 Ladder Queue. Proporciona un rendimiento O (1) estable incluso bajo distribuciones de cola con varianza infinita. Similar a Lazy Queue, pero mejor.
• Yan 2006 Cola de calendario lenta. Cuando los eventos se insertan principalmente en orden, es posible utilizar algunas propiedades estadísticas para lograr una aceleración de 2 órdenes
• Himmelspach 2007 Los eventos tienen duraciones, fuera de la línea principal de investigación. Se necesita funcionalidad adicional, este algoritmo lo proporciona pero puede tener un trabajo de seguimiento limitado.

Además, hemos terminado de describir una variante del algoritmo de Brown que debería funcionar mejor. La descripción es, creo, bastante adecuada para construir una implementación y el código de muestra se proporciona en el documento. La publicación se titula Trading Space for Time: Constant-Speed Algorithms for Managing Future Events in Scientific Simulations por Lehman, Keene y Barnes, y debe indexarse ​​en algún momento de este otoño. Si desea una copia, deje un comentario y se lo enviaré.

Para responder a una parte diferente de su pregunta, puede pensar en una cola de calendario como una cola de prioridad que está optimizada para eventos que tendrán prioridades cada vez menores. Por lo general, las prioridades (tiempos) de los eventos se agrupan de alguna manera para evitar tener que tocar todos los eventos para insertar uno (como puede suceder en ciertas formas de administración de heap).