J'essaye d'utiliser queue.PriorityQueue dans Python 3 (.6).
Je voudrais stocker des objets avec une priorité donnée. Mais si deux objets ont la même priorité, cela ne me dérange pas PriorityQueue.get de retourner non plus. En d'autres termes, mes objets ne peuvent pas être comparés à des nombres entiers, cela n'a aucun sens de les autoriser, je me soucie juste de la priorité.
Dans Documentation de Python 3.7 , il existe une solution impliquant des dataclasses . Et je cite:
Si les éléments de données ne sont pas comparables, les données peuvent être enveloppées dans une classe qui ignore l'élément de données et ne compare que le numéro de priorité:
from dataclasses import dataclass, field
from typing import Any
@dataclass(order=True)
class PrioritizedItem:
priority: int
item: Any=field(compare=False)
Hélas, j'utilise Python 3.6. Dans la documentation de cette version de Python , il n'y a aucun commentaire sur l'utilisation de PriorityQueue pour les priorités, sans se soucier de la "valeur de l'objet" qui ne serait pas logique dans mon cas.
Y a-t-il un meilleur moyen que de définir __le __ code > et d'autres méthodes de comparaison sur ma classe personnalisée? Je trouve cette solution particulièrement laide et contre-intuitive, mais c'est peut-être moi.
4 Réponses :
Voir notes d'implémentation de la file d'attente prioritaire - juste avant la section que vous avez citée (concernant l'utilisation des dataclasses ), il vous indique comment le faire sans les:
... consiste à stocker les entrées sous forme de liste à 3 éléments comprenant la priorité, un nombre d'entrées et la tâche. Le décompte des entrées sert de bris d'égalité afin que deux tâches de même priorité soient renvoyées dans l'ordre où elles ont été ajoutées. Et comme il n'y a pas deux nombres d'entrées identiques, la comparaison de tuple ne tentera jamais de comparer directement deux tâches.
Ajoutez donc simplement vos éléments en tant que 3e élément dans un tuple (Prio, Count, YourElem) lors de l'ajout à votre file d'attente.
Exemple bidon:
(1, 2, write spec 3) (1, 3, write spec 2) (1, 4, write spec 1) (3, 5, create tests)
Utilisation de h.put ((1, O ('write spec 1'))) mène à
TypeError: '<' not supported between instances of 'O' and 'int'`
Utilisation de def add (prioqueue, prio, item): pousse les triplets comme des éléments qui ont garanti des 2ièmes valeurs distinctes donc notre Les instances O () ne sont jamais utilisées comme bris d'égalité.
Sortie:
from queue import PriorityQueue
class CompareError(ValueError): pass
class O:
def __init__(self,n):
self.n = n
def __lq__(self):
raise CompareError
def __repr__(self): return str(self)
def __str__(self): return self.n
def add(prioqueue,prio,item):
"""Adds the 'item' with 'prio' to the 'priorqueue' adding a unique value that
is stored as member of this method 'add.n' which is incremented on each usage."""
prioqueue.put( (prio, add.n, item))
add.n += 1
# no len() on PrioQueue - we ensure our unique integer via method-param
# if you forget to declare this, you get an AttributeError
add.n = 0
h = PriorityQueue()
add(h, 7, O('release product'))
add(h, 1, O('write spec 3'))
add(h, 1, O('write spec 2'))
add(h, 1, O('write spec 1'))
add(h, 3, O('create tests'))
for _ in range(4):
item = h.get()
print(item)
voir MartijnPieters répond @ici pour un deuxième élément unique plus agréable.
Pourquoi vous plonger dans heappush alors que cette question concerne spécifiquement l'utilisation de queue.PriorityQueue ?
@NickChapman je quoi? heappush? où? : o) merci d'avoir laissé entendre ma bévue
Merci beaucoup, je trouve cette solution beaucoup plus élégante et optimisée. Un objet Counter permet en fait de réduire encore plus le code de la chaudière. Cela prouve: je ne lis pas correctement la documentation!
@ vincent-lg bien, cette documentation fait partie du module heapq . Il se trouve que queue.PriorityQueue est implémenté sur le dessus de l'op heapq , mais il faut une lecture approfondie pour obtenir de la documentation de queue ce conseil dans la documentation du module heapq .
@MartijnPieters heapq est référencé en haut du site qu'il a cité: Avec une file d'attente prioritaire, les entrées sont conservées triées (en utilisant le module heapq) et l'entrée la plus basse est récupérée en premier c'est pourquoi j'ai atterri Là
@PatrickArtner oui, je n’ai pas dit le contraire! Mais s'attendre à ce que quelqu'un qui regarde la documentation du module de file d'attente lise la documentation du module heapq de manière suffisamment détaillée pour trouver cette section est une question assez importante.
Supposons que nous ne voulions pas écrire un décorateur avec des fonctionnalités équivalentes à dataclass . Le problème est que nous ne voulons pas avoir à définir tous les opérateurs de comparaison afin de rendre notre classe personnalisée comparable en fonction de la priorité. Le @ functools.total_ordering le décorateur peut vous aider. Extrait:
Étant donné une classe définissant une ou plusieurs méthodes de classement de comparaison riches, ce décorateur de classe fournit le reste. Cela simplifie l'effort impliqué dans la spécification de toutes les opérations de comparaison riches possibles:
La classe doit définir l'un des éléments suivants:
__lt __ (),__le __ (),__gt __ ()ou__ge __ () . De plus, la classe doit fournir une méthode__eq __ ().
En utilisant l'exemple fourni:
from functools import total_ordering
@total_ordering
class PrioritizedItem:
# ...
def __eq__(self, other):
return self.priority == other.priority
def __lt__(self, other):
return self.priority < other.priority
vous n'avez besoin que de __lt__ pour trier, vous n'avez même pas besoin de vous soucier de générer le reste des opérateurs de comparaison riches.
@NickChapman: list.sort promet de n'utiliser que <, mais le fait que heapq ou queue.PriorityQueue uniquement use < est un détail d'implémentation. De plus, se fier uniquement à des comparaisons < est une recette pour des surprises étranges de toute façon. Il est préférable de fournir toutes les opérations de comparaison.
De plus, vous devriez vraiment renvoyer NotImplemented lorsque other est d'un type non reconnu au lieu d'accéder de manière inconditionnelle à other.priority .
@ user2357112 pouvez-vous expliquer pourquoi il devrait en être ainsi? Une TypeError ne serait-elle pas non plus plus appropriée?
@ChrisHunt: Le TypeError n'est pas la responsabilité de __lt__ . Les méthodes de comparaison sont censées renvoyer NotImplemented si elles ne savent pas comment effectuer une comparaison, pour donner à l'autre partie une chance de l'implémenter. Si les deux côtés renvoient NotImplemented , la machine de comparaison déclenche une TypeError (ou renvoie False / True pour == /! =).
@ user2357112, merci. Le texte ici associé à la description de NotImplemented m'a aidé à comprendre. La convention consiste-t-elle à utiliser le typage canard et à attraper AttributeError en accédant aux propriétés pertinentes sur autre ou à vérifier explicitement le type comme dans les opérations arithmétiques et la réponse @MartijnPieters?
@ChrisHunt: vérification de type explicite. Dans ce genre de situation, vous vous souciez généralement du type réel, pas des attributs de l'argument.
Tout ce dont vous avez besoin est une classe wrapper qui implémente __lt__ pour que PriorityQueue fonctionne correctement. Ceci est noté ici :
Les routines de tri sont garanties d'utiliser
__lt __ ()lors des comparaisons entre deux objets. Ainsi, il est facile d'ajouter un ordre de tri standard à une classe en définissant une méthode__lt __ ()
C'est aussi simple que quelque chose comme ça
elem = queue.get().wrapped_elem
Si vos éléments n'ont pas de priorités, c'est aussi simple que:
queue = PriorityQueue() queue.put(PriorityElem(my_custom_class1, 10)) queue.put(PriorityElem(my_custom_class2, 10)) queue.put(PriorityElem(my_custom_class3, 30)) first_returned_elem = queue.get() # first_returned_elem is PriorityElem(my_custom_class1, 10) second_returned_elem = queue.get() # second_returned_elem is PriorityElem(my_custom_class2, 10) third_returned_elem = queue.get() # third_returned_elem is PriorityElem(my_custom_class3, 30)
Vous pouvez maintenant utiliser PriorityQueue comme ça
class PriorityElem:
def __init__(self, elem_to_wrap, priority):
self.wrapped_elem = elem_to_wrap
self.priority = other.priority
def __lt__(self, other):
return self.priority < other.priority
Obtenir vos éléments d'origine dans ce cas serait aussi simple que
class PriorityElem:
def __init__(self, elem_to_wrap):
self.wrapped_elem = elem_to_wrap
def __lt__(self, other):
return self.wrapped_elem.priority < other.wrapped_elem.priority
Comme vous ne vous souciez pas de la stabilité du tri, c'est tout ce dont vous avez besoin.
Modifier: comme indiqué dans les commentaires et confirmé ici , heappush n'est pas stable:
contrairement à sorted (), cette implémentation n'est pas stable.
list.sort et sorted peuvent être stables, mais queue.PriorityQueue est basé sur un tas, et l'implémentation du tas n'est pas stable.
L'implémentation actuelle de heapq n'utilise en effet que < pour faire des comparaisons, mais il s'agit d'un détail d'implémentation . Je ne me fierais pas à de tels détails et je fournirais plutôt plus de méthodes de comparaison.
@MartijnPieters s'il s'agit d'un détail d'implémentation, nous devrions créer un problème avec la documentation extraite dans l'article, ce qui garantit qu'elle n'utilisera que __lt __ () .
@ChrisHunt: une file d'attente prioritaire ne trie pas . Il est construit à l'aide du module heapq , c'est un arbre binaire stocké dans une liste.
Voir aussi Est-il sûr de simplement implémenter __lt__ pour une classe qui sera triée? , où Raymond Hettinger souligne que vous ne devriez pas vraiment seulement sur < code> __ lt__ . Je vais regarder pourquoi le HOWTO affirme toujours que __lt__ est suffisant, car aucune autre page de documentation Python ne fait la même déclaration.
@MartijnPieters mon erreur, je pensais que la documentation liée était pour PriorityQueue. La réponse que vous avez liée constitue un argument assez fort pour total_ordering plutôt que de définir simplement __lt__ .
Merci, cela fonctionne et est facile à lire. Un triplet avec un compteur au milieu pourrait en fait être plus optimisé, cela éviterait d'avoir à créer des instances juste pour alimenter la file d'attente prioritaire, mais c'est plus un détail.
J'ai déposé un problème de documentation pour voir si cette réclamation peut être supprimée. Il n'a aucune provenance que je puisse trouver. Voir bugs.python.org/issue35654
dataclasses est juste une méthode pratique pour éviter d'avoir à créer beaucoup de code standard.
En fait, vous n'avez pas besoin de créer une classe. Un tuple avec une valeur de compteur unique aussi:
from functools import total_ordering
@total_ordering
class PrioritizedItem:
def __init__(self, priority, item):
self.priority = priority
self.item = item
def __eq__(self, other):
if not isinstance(other, __class__):
return NotImplemented
return self.priority == other.priority
def __lt__(self, other):
if not isinstance(other, __class__):
return NotImplemented
return self.priority < other.priority
afin que les liens entre une priorité égale soient rompus par l'entier qui suit; car elle est toujours unique, la valeur de item n'est jamais consultée.
Vous pouvez également créer une classe en utilisant des méthodes de comparaison riches directes, simplifiées avec @ functools.total_ordering :
from itertools import count unique = count() q.put((priority, next(unique), item))
manière très élégante d'obtenir l'élément distinctif
J'aime beaucoup la solution counter () . Il a l'avantage d'éviter de créer une classe (quelques lignes de code, mais pas beaucoup) et l'avantage supplémentaire qu'il ne nécessite pas de créer des instances uniquement pour le compteur de priorité. C'est un problème de performance et probablement un problème très mineur, sauf lorsqu'il s'agit de millions d'objets, mais je trouve toujours cette solution plus élégante. Merci!
Notez que votre gestion du compteur n'est pas thread-safe; le module queue est explicitement thread-safe (j'utilise personnellement le module heapq directement lorsque thread-safety n'est pas requis), donc ce ne pas être thread-safe pourrait être un gros problème.
Vos objets lancent-ils réellement une exception si vous les comparez les uns aux autres? Sinon, il n'y a rien à craindre.
@jasonharper simplement parce que deux objets se comparent sans qu'une erreur ne soit générée ne signifie pas que les objets sont triés dans un ordre raisonnable. Regardez cette question: stackoverflow.com/questions/6252758/python-default-compariso n