Qu'est-ce qu'une file d'attente de calendrier?

Définition par NIST :

Une mise en oeuvre de la file d'attente prioritaire rapide comportant des gaux avec une largeur W, ou couvrant W Time. Un article avec priorité p plus que courant va dans le seau (p / w)% n. Choisissez N et W pour avoir peu d'articles dans chaque godet. Gardez des objets triés dans les godets. Double ou réduire de moitié N et changer w si le nombre d'éléments augmente ou diminue beaucoup.

Paul E. Black, "Queue de calendrier", dans le dictionnaire des algorithmes et des structures de données [Online], Vreda Pieterse et Paul E. Black, EDS. 24 janvier 2005. (Accès 2014-03-10) Disponible à partir de: http: // www. nist.gov/dads/html/calendarqueue.html

Une recherche Google trouve

Étude des largeurs de godet optimisées dans la file d'attente de calendrier pour un événement discret Simulateur

http://pioneer.netserv.chula.ac.th/~ ACHAODIT / PAPER5.PDF

qui décrit les files d'attente de calendrier à la section 2.

Oui, Brown 1988 est le premier papier que je connaisse de décrire les files d'attente de calendrier, bien que marken Plusieurs auteurs qui l'ont précédé. Vous trouverez ci-dessous une bibliographie relativement complète de la littérature queue de calendrier avec mes notes sur chaque papier. Laissez-moi un commentaire si vous souhaitez copie de l'une des publications.

• Vaucher 1975 Comparaison des algorithmes de liste d'événements. Présente également trois nouveaux algorithmes. Inspiré brown1988.
• Henricksen 1977 Evénements List Algorithm - s'adapte à des temps intervalles et fonctionne bien avec un certain nombre de distributions, basées sur Vaucher et Duval
• Ulrich 1978 Brown1988 prétend ceci est O (1), à l'exception de la liste de débordement
• Jones 1986 compare les priorités files d'attente, a une version précoce d'une file d'attente de calendrier
• Brown 1988 introduit la file d'attente du calendrier [AKA: Queue de calendrier de discipline Triée]
• Davison 1989 découvre la même chose, mentionne certaines améliorations importantes, Brown reconnaît les améliorations de la même lettre et a des pensées de son propre. Davison suggère que Jones 1986 a offert une mécanique de calendrier de valeur
• Ronngren 1991 la file d'attente paresseuse. Une file d'attente de calendrier qui a un avenir proche, loin et très loin - cela permet un tri retardé, ce qui accélère considérablement les choses dans leurs tests
• Horizon d'événement Steinman 1994. Les événements générés ont une répartition de la probabilité lorsqu'elles se produisent, utilisons cela pour déterminer ce qui doit être trié. Autoriser la simulation parallèle
• Steinman 1996 Evénement Horizon Partie 2. Applique Steinman1994 à la gestion de la liste des événements. Modifie d'autres structures de données pour une utilisation dans CQS.
• Ronngren 1997 Comparaison de nombreuses files d'attente de calendrier. La file paresseuse fonctionne bien, mais Brown1988 fonctionne fréquemment mieux. Lazyq et la SCQ ont de mauvaises performances au pire des cas, un tas et un arbre Spers Spersp ont le meilleur cas.
• OH 1997 File d'attente de calendrier paresseux dynamique. Améliorer la performance de CQ conventionnelle sur les distributions d'événements inégaux
• OH 1999 Queue de calendrier dynamique. Fonctionne bien avec des distributions inégales
• Cazzolla 1998 Java Mise en œuvre de la file d'attente paresseuse avec analyse (pas un papier académique).
• TAN 2000 SNOOPY: Statistiquement amélioré avec le paramètre de fonctionnement optimal CQ. Utilise des tests statistiques pour créer un godet EBTER. Fonctionne jusqu'à 100 fois plus rapidement que le DCQ et CQ dans certains scénarios
• Thèse de baccalauréat de thèse Hui décrivant de nombreux détails du document HUI 2002 avec les avantages et les inconvénients d'autres implémentations de la file d'attente de calendrier
• HUI 2002 Les événements futurs n'ont pas besoin d'être triés en ce moment; Par conséquent, la taille de la file d'attente prioritaire peut être limitée, ce qui réduit le redimensionnement des frais généraux.
• goh 2003 mlist. Les listes liées à plusieurs niveaux éliminent les opérations de redimensionnement. Montré expérimentalement d'être d'au moins 100% plus rapide que la file d'attente du calendrier, CQ dynamique, Snoopy CQ, CQ dynamique dynamique de 2 niveaux et une file d'attente paresseuse 3 tier
• Seau optimisée de Siangsukone 2003 en CQ. Démontre que la largeur du seau peut avoir des effets importants sur la performance.
• goh 2004 dsplay. Éliminer les opérations de redimensionnement coûteux. Au moins 100% plus rapide que les autres files d'attente de calendrier.
• Tang 2005 File d'attente. Fournit une stable o (1) performance, même sous des distributions en file d'attente avec une variance infinie. Similaire à la file d'attente paresseuse, mais mieux.
• YAN 2006 File d'attente du calendrier lente. Lorsque les événements sont principalement insérés dans l'ordre, il est possible d'utiliser certaines propriétés statistiques pour obtenir une vitesse de 2 commandes
• HimmelsPach 2007 Les événements ont des durées - en dehors de la ligne de recherche principale. Une fonctionnalité supplémentaire était nécessaire, cet algorithme le fournit, mais peut avoir un travail de suivi limité.

  En outre, nous avons récemment fini de décrire une variante d'algorithme de Brown qui devrait fonctionner mieux. La description est que je pense que, assez adéquate de construire une mise en œuvre à partir de laquelle le code est fourni dans le document. La publication est intitulée Space de trading pour le temps: Algorithmes de vitesse constante pour la gestion des événements futurs dans les simulations scientifiques de Lehman, Keene et Barnes et devraient être indexées parfois cette chute. Si vous souhaitez une copie, laissez un commentaire et je vous l'enverrai.

  Pour répondre à une autre partie de votre question, vous pouvez penser à une file d'attente de calendrier comme une file d'attente prioritaire optimisée pour des événements qui auront des priorités en constante diminution. Habituellement, les priorités des événements sont cassées d'une certaine manière afin d'éviter de devoir toucher tous les événements afin d'insérer un (comme cela se produise dans certaines formes de gestion du tas).