Comment faire une efficace mise à jour prioritaire dans la STL priority_queue?
J'ai un priority_queue de certains objets:
typedef priority_queue<Object> Queue;
Queue queue;
De temps en temps, la priorité de l'un des objets peut changer - j'ai besoin d'être en mesure de mettre à jour la priorité de l'objet dans la file d'attente de manière efficace. Actuellement, je suis en utilisant cette méthode qui fonctionne, mais semble inefficace:
Queue newQueue;
while (!queue.empty())
{
Object obj=queue.top();
queue.pop();
if (priorityHasChanged(obj))
newQueue.push_back(Object(new_priority));
else
newQueue.push_back(obj);
}
newQueue.swap(queue); //this only works because I actually subclassed the priority_queue
//class and exposed a swap method that swaps in the container
J'ai mis en place cette façon parce que j'étais dans une sorte de hâte à l'époque et c'était la chose la plus rapide que je pouvais faire ce que je pouvais être sûr qu'il allait travailler sur ok. Il y a une meilleure façon de faire que cela. Vraiment ce que je veux, c'est un moyen de soit:
- extrait de l'instance avec le changement de priorité et insérez-en une nouvelle avec la nouvelle valeur de priorité
- mise à jour de l'instance avec le changement de priorité et ensuite mettre à jour la file d'attente afin qu'il soit correctement triés
Quelle est la meilleure façon de le faire?
Vous devez vous connecter pour publier un commentaire.
Je pense que vous êtes hors de la chance avec la norme file d'attente de priorité parce que vous ne pouvez pas obtenir les sous-jacents deque/vecteur/liste ou quoi que ce soit. Vous devez mettre en place votre propre - il n'est pas difficile.
c
(voir référence). Vous pouvez bénéficier de la priorité de la file d'attente et l'accès du conteneur dans la classe dérivée.c
mais puisque vous ne pouvez pas trouver l'index de la clé en O(logn), vous ne pouvez pas faire une priorité de mise à jour en temps O(cgl) qui est vraiment la partie malheureuse.Je peux vous proposer 2 choix pour résoudre le problème, bien que ni effectue une mise à jour réelle.
Utiliser le
priority_queue
et pousser l'élément chaque fois que vous souhaitez mettre à jour. Accepter le fait que vous aurez inutiles les entrées dans la file d'attente. Quand sautant le haut de la valeur, vérifier si elle contient la valeur de date. Si non, de l'ignorer et de la pop à la prochaine.De cette façon, vous retarder le retrait de l'élément mis à jour jusqu'à ce qu'il vient vers le haut. J'ai remarqué que cette méthode est utilisée par les meilleurs programmeurs réalisation de Dijkstra algorithme.
Utilisation
set
. Il est également trié de sorte que vous êtes capable d'extraire le plus grand élément en temps logarithmique. Vous êtes également capable de supprimer les anciens de l'élément avant de l'insérer de nouveau. Donc toujours pas de mise à jour possible, mais le retrait et la réinsertion, c'est faisable.Semble que la complexité de ces deux approches est la même.
priority_queue
avec n éléments réels et m obsolètes les articles les prendre en O(log (n + m)) par rapport à O(log n).La façon la plus simple de le faire avec TSL (que je connais) est à retirer à l'entrée, la mise à jour de sa priorité et puis réinsérez-la. Faire cela est assez lent en utilisant std::priority_queue, cependant, vous pouvez faire la même chose avec std::set. Malheureusement, vous devez être prudent afin de ne pas modifier la priorité d'un objet lorsqu'il est dans le jeu.
J'ai mis en place un mutable_priority_queue classe de coller ensemble un std::multimap (par priorité à la valeur de la cartographie) et une std::map (pour la valeur de la priorité de la cartographie) qui vous permet d'insérer/supprimer des éléments ainsi que de mettre à jour les valeurs en temps logarithmique. Vous pouvez obtenir le code, et un exemple de comment l'utiliser ici
Appropriées de la structure de données est appelé "Tas de Fibonacci".
Mais vous devez le faire vous-même.
Insérer/Mises à jour sont en O(1)
ExtractMin est O(logn)
J'ai mis en place une haute performance pouvant être mis à jour file d'attente de priorité et mis à la disposition des sur github.
C'est comment vous pouvez généralement utiliser :
Pour compléter Jarekczek réponse, si en effet à la fois la
set
et "pure tas inutiles, les entrées de" méthodes ont la même complexité, lastl::set
version effectue généralement beaucoup plus lent que lastl::priority_queue
version en raison du fait qu'il est mis en œuvre avec des arbres rouge-noir que la seule garantie de leur profondeur de l'être inférieure à 2*log_2(n_elements) et nécessitent des mises à jour régulières, tandis questl::priority_queue
est une pure et rapide tas binaire que possible. C'est pourquoi il est généralement utilisé lors de la mise en œuvre de Dijkstra.L'approche peut toutefois être plus rapide lors de la prise de beaucoup de mises à jour sur la base peu de nœuds. C'est aussi là que l'aide de ma bibliothèque devrait vous apporter la plus grande amélioration.
Vous voudrez peut-être avoir un coup d'oeil à
replace_if
avec un exemple ici.Malheureusement vous ne pouvez pas mettre à jour la valeur dans priority_queue. priority_queue n'offre pas une telle interface.
Je pense que vous feriez mieux d'utiliser
set
comme Jarekczek dit ou utiliser cette solution(à l'aide de make_heap).