Une file d'attente prioritaire qui permet une mise à jour efficace des priorités?
mise à JOUR : ma mise en œuvre de Haché Calendrier Roues . Veuillez me faire savoir si vous avez une idée pour améliorer la performance et la concurrence. (20-Jan-2009)
// Sample usage:
public static void main(String[] args) throws Exception {
Timer timer = new HashedWheelTimer();
for (int i = 0; i < 100000; i ++) {
timer.newTimeout(new TimerTask() {
public void run(Timeout timeout) throws Exception {
// Extend another second.
timeout.extend();
}
}, 1000, TimeUnit.MILLISECONDS);
}
}
UPDATE : j'ai résolu ce problème en utilisant les roues de chronométrage hiérarchisées et hachées . (19-Jan-2009)
j'essaie d'implémenter une minuterie spéciale en Java qui est optimisé pour la gestion des timeouts. Par exemple, un utilisateur peut enregistrer une tâche avec une ligne morte et le minuteur peut notifier la méthode de rappel d'un utilisateur lorsque la ligne morte est terminée. Dans la plupart des cas, une tâche enregistrée sera effectuée dans un délai très court, de sorte que la plupart des tâches seront annulées (par exemple tâche.annulez ()) ou reprogrammez dans le futur (par exemple tâche.replanuletolater(1, TimeUnit.DEUXIÈME.))
je veux utiliser cette minuterie pour détecter une connexion de socket inactif (par exemple fermer la connexion lorsqu'aucun message n'est reçu en 10 secondes) et temps d'attente en écriture (par exemple, soulever une exception lorsque l'opération en écriture n'est pas terminée en 30 secondes).) Dans la plupart des cas, le délai ne se produira pas, le client enverra un message et la réponse sera envoyée à moins qu'il n'y ait un problème de réseau bizarre..
Je ne peux pas utiliser java.util.Minuterie ou java.util.simultané.ScheduledThreadPoolExecutor parce qu'ils assument la plupart des tâches sont censés être chronométré. Si une tâche est annulée, l' la tâche annulée est stockée dans son tas interne jusqu'à L'Ordonnancedthreadpoolexecutor.purger() est appelée, et c'est une opération très coûteuse. (O(NlogN) peut-être?)
dans les tas traditionnels ou les files d'attente de priorité que j'ai appris dans mes classes CS, la mise à jour de la priorité d'un élément était une opération coûteuse (o(logN) dans de nombreux cas parce qu'elle ne peut être réalisée qu'en enlevant l'élément et en le ré-insérant avec une nouvelle valeur de priorité. Certains tas comme Fibonacci tas A O (1) Temps de decreaseKey() et min (), mais ce dont j'ai besoin au moins est rapide increaseKey() et min() (ou decreaseKey() et max()).
connaissez-vous une structure de données hautement optimisée pour ce cas particulier d'utilisation? Une stratégie à laquelle je pense est simplement de stocker toutes les tâches dans une table de hachage et d'itérer toutes les tâches chaque seconde environ, mais ce n'est pas si beau.
9 réponses
Que Diriez-vous d'essayer de séparer le traitement du cas normal où les choses se terminent rapidement des cas d'erreur?
utilisez à la fois une table de hachage et une file d'attente prioritaire. Quand une tâche est commencée elle est mise dans la table de hachage et si elle finit rapidement elle est retirée dans le temps O(1).
chaque seconde vous scannez la table de hachage et toutes les tâches qui ont été un long moment, disons .75 secondes, en file d'attente prioritaire. La file d'attente prioritaire devrait toujours être petit et facile à manipuler. Cela suppose qu'une seconde est beaucoup moins que les temps d'arrêt que vous recherchez.
si le balayage de la table de hachage est trop lent, vous pouvez utiliser deux tables de hachage, essentiellement une pour les secondes paires et une pour les secondes impaires. Lorsqu'une tâche commence, elle est placée dans la table de hachage actuelle. Chaque seconde déplace toutes les tâches de la table de hachage non-current dans la file d'attente prioritaire et échange les tables de hachage de sorte que le hachage courant la table est maintenant vide et la table non-current contient les tâches commencées il y a entre une et deux secondes.
il existe des options beaucoup plus compliquées que l'utilisation d'une file d'attente de priorité, mais sont assez facilement mis en œuvre devrait être stable.
à ma connaissance (j'ai écrit un article sur une nouvelle file d'attente prioritaire, qui a également passé en revue les résultats passés), aucune mise en œuvre de file d'attente prioritaire obtient les limites de Fibonacci tas, ainsi que l'augmentation de temps constant-clé.
il y a un petit problème à obtenir que littéralement. Si vous pouvez obtenir increase-key en O (1), alors vous pouvez obtenir delete en O(1) -- juste augmenter la clé à + infinity (vous pouvez gérer la file d'attente étant pleine de beaucoup de + infinitys en utilisant certains trucs d'amortissement standard). Mais si trouver-min est également en O(1), ce qui signifie supprimer-min = trouver-min + suppr devient O(1). C'est impossible dans une file d'attente de Priorité basée sur la comparaison parce que le tri lié implique (insérez tout, puis supprimez un par un) que
n * insérer + n * supprimer-min > n log N.
Le point ici est que si vous voulez une priorité de la file d'attente à soutenir les clés en O(1), puis vous devez accepter l'une des pénalités suivantes:
- ne Pas être basé sur des comparaisons. En fait, c'est une assez bonne façon de contourner les choses, par exemple arbres vEB .
- Accepter O(log n) pour les plaquettes et aussi O(n log n) pour faire de tas (étant donné n de valeurs de départ). Cette suce.
- Accepter O(log n) pour trouver min. C'est tout à fait acceptable si vous n'avez jamais réellement faire trouvez-min (sans un accompagnement supprimer).
mais, encore une fois, à ma connaissance, personne n'a fait la dernière option. J'ai toujours vu ça comme une opportunité pour de nouveaux résultats dans un domaine assez basique des structures de données.
Utiliser Haché Calendrier Roue - Google "Haché Hiérarchique Calendrier des Roues" pour plus d'informations. C'est une généralisation des réponses faites par des gens d'ici. Je préférerais une roue de chronométrage hachée avec une grande taille de roue à des roues de chronométrage hiérarchisées.
une certaine combinaison de hashes et de structures O(logN) devrait faire ce que vous demandez.
je suis tenté de discuter de la façon dont vous analysez le problème. Dans votre commentaire ci-dessus, vous dites
parce que la mise à jour se produira très fréquemment. Disons que nous envoyons des messages M par connexion alors le temps global devient O (MNlogN), ce qui est assez grand. - Trustin Lee (il y a 6 heures)
qui est absolument corriger comme il va. Mais la plupart des gens que je connais se concentrerait sur le coût par message , sur la théorie que comme vous app a de plus en plus de travail à faire, évidemment, il va falloir plus de ressources.
donc si votre application a un milliard de sockets ouverts simultanément (est-ce vraiment probable?) le coût d'insertion n'est que d'environ 60 comparaisons par message.
je parie de l'argent que ceci est l'optimisation prématurée: vous n'avez pas réellement mesuré les goulots d'étranglement dans votre système avec un outil d'analyse des performances comme CodeAnalyst ou VTune.
quoi qu'il en soit, il y a probablement un nombre infini de façons de faire ce que vous demandez, une fois que vous décidez qu'aucune structure ne fera ce que vous voulez, et que vous voulez une combinaison des forces et des faiblesses de différents algorithmes.
une possibilité est de diviser le domaine socket N en un certain nombre de seaux de la taille B, et puis hachez chaque prise dans un de ces (N/B) seaux. Dans ce seau est un tas (ou quoi que ce soit) avec O(log B) Temps de mise à jour. Si une limite supérieure sur N n'est pas fixée à l'avance, mais peut varier, alors vous pouvez créer plus de seaux dynamiquement, ce qui ajoute une petite complication, mais est certainement faisable.
dans le pire des cas, le chronométreur de chien de garde doit chercher (N/B) les files d'attente pour les expirations, mais je suppose que le chronométreur de chien de garde n'est pas requis pour tuer le ralenti prises dans un ordre particulier! C'est-à-dire que si 10 sockets sont devenus inactifs lors de la dernière tranche de temps, il n'a pas besoin de chercher dans ce domaine celui qui est sorti en premier, de s'en occuper, puis de trouver celui qui est sorti en second, etc. Il suffit de scanner l'ensemble de seaux (N/B) et d'énumérer tous les temps morts.
si vous n'êtes pas satisfait d'un tableau linéaire de seaux, vous pouvez utiliser une file d'attente prioritaire, mais vous voulez éviter de mettre à jour cette file d'attente sur chaque message, ou sinon tu es de retour là où tu as commencé. Au lieu de cela, définissez un temps qui est moins que le temps réel. (Disons, 3/4 ou 7/8 de cela) et vous mettez seulement la file d'attente de bas niveau dans la file d'attente de haut niveau si elle est plus longue que cela.
et au risque de dire l'évidence, vous ne voulez pas que vos Files d'attente soient tapées sur temps écoulé . Les clés doivent être démarrer du temps. Pour chaque enregistrement dans les files d'attente, le temps écoulé devrait être mis à jour constamment, mais l'heure de début de chaque enregistrement ne change pas.
il y a une façon très simple de faire toutes les insertions et les suppressions dans O(1), en profitant du fait que 1) la priorité est basée sur le temps et 2) vous avez probablement un petit nombre fixe de durées d'expiration.
- créer une file D'attente FIFO régulière pour contenir toutes les tâches qui timeout en 10 Secondes. Parce que toutes les tâches ont des durées de temps d'arrêt identiques, vous pouvez simplement insérer à la fin et supprimer du début pour garder la file d'attente triée.
- Créez une autre file D'attente FIFO pour les tâches avec une durée de timeout de 30 secondes. Créer plus de files d'attente pour d'autres durées d'attente.
- pour annuler, retirez l'article de la file d'attente. C'est O(1) si la file d'attente est implémentée en tant que liste liée.
- rééchelonnement peut être fait comme cancel-insert, que les deux opérations sont O(1). Notez que les tâches peuvent être reportées à des files d'attente différentes.
- enfin, regrouper toutes les files D'attente FIFO en une seule priorité globale file d'attente, demandez à la tête de chaque file D'attente FIFO de participer à un tas régulier. Le chef de ce tas sera la tâche avec le temps d'expiration le plus tôt expirant hors de toutes les tâches.
si vous avez m nombre de durées d'arrêt différentes, la complexité pour chaque opération de la structure globale est O(log m). L'Insertion est O (log m) en raison de la nécessité de rechercher la file d'attente à laquelle insérer. Remove-min est O (log m) pour restaurer le tas. L'annulation est O (1) mais dans le pire des cas O(log m) si vous annulez la tête d'une file d'attente. Parce que m est un petit nombre fixe, o (log m) est essentiellement O(1). Il n'est pas adapté au nombre de tâches.
votre scénario me suggère un tampon circulaire. Si le max. le temps mort est de 30 secondes et nous voulons récolter des sockets au moins tous les dixièmes de seconde, puis utiliser un tampon de 300 listes doublement liées, une pour chaque dixième de seconde dans cette période. Pour "increeztime" sur une entrée, retirez-la de la liste où elle est et ajoutez-la à celle de sa nouvelle dixième période (deux opérations en temps constant). Quand une période se termine, récolter tout ce qui reste dans la liste actuelle (peut-être par l'alimentation à un thread reaper) et avancer le pointeur de la liste courante.
vous avez une limite dure sur le nombre d'articles dans la file-il y a une limite aux sockets TCP.
par conséquent, le problème est limité. Je pense que toute structure de données intelligente sera plus lente que d'utiliser des types intégrés.
Est-il une bonne raison de ne pas utiliser java.lang.PriorityQueue? Est-ce que remove() ne gère pas vos opérations d'annulation dans log(N) time? Puis implémentez votre propre attente basée sur le temps jusqu'à l'élément sur le devant de la file d'attente.
je pense que stocker toutes les tâches dans une liste et les itérer à travers eux serait le mieux.
Vous devez être (va) lancer le serveur sur certains assez costaud machine à arriver à la limite où ce coût sera important?