PRIORITY QUEUE
SharpMao
Messages postés
1024
Date d'inscription
mardi 4 février 2003
Statut
Membre
Dernière intervention
7 juin 2010
-
11 mai 2007 à 09:33
cs_Bidou Messages postés 5487 Date d'inscription dimanche 4 août 2002 Statut Membre Dernière intervention 20 juin 2013 - 13 mai 2007 à 11:14
cs_Bidou Messages postés 5487 Date d'inscription dimanche 4 août 2002 Statut Membre Dernière intervention 20 juin 2013 - 13 mai 2007 à 11:14
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/42654-priority-queue
https://codes-sources.commentcamarche.net/source/42654-priority-queue
13 mai 2007 à 11:14
11 mai 2007 à 15:59
11 mai 2007 à 15:34
11 mai 2007 à 15:16
et notamment le lien de visualisation d'un b-arbre pour te faire une idée. C'est la méthode utilisée pour insérer les élements dans une base de données.
11 mai 2007 à 15:03
Tu es obligé de vérifier si elle est existante ou pas, non? Donc tu dois itérer à travers toutes tes queues pour voir si elle existe? même chose quand tu en supprimes une?
11 mai 2007 à 14:34
De plus si je suis dans le cas que tu décris et que je dois vraiment optimiser le classement, j'utiliserai un algorithme B-TREE et je serais toujours plus efficace.
Pour l'instant le seul problème pour lequel je suis obligé d'utiliser un algo de classement, c'est quand je fais de la 3D et que je dois classer des polygones, parce que leur définition utilise plus d'une dimension.
Dans le cas où mes élements n'ont qu'une dimension, je peux les classer. Dans le cas d'une queue à priorité, mon élément de priorité a rarement plus d'une dimension et mon algo, éventuellement classé en arbre, est toujours plus rapide.
11 mai 2007 à 14:21
SharpMao> Oui, tu as raison ;-)
11 mai 2007 à 14:16
Pour les SortedList, tu as raison.
Par contre, corrige-moi si je me trompe, mais cette méthode ne donne pas de queue FIFO avec des éléments de même priorité.
11 mai 2007 à 14:07
Queue[0]
Queue[1]
Queue[2]
Queue[3]
Queue[4]
...
Eventuellement créées dynamiquement (c'est pas la peine de créer 65535 queues si tu a ce nombre de niveaux de priorités) et détruites dynamiquement quand elles sont vides.
Si tu as un niveau de priorité 4 à mettre, tu le mets dans la liste 4 soit O(1)
Tu ne peux lire dans la liste 4 que si les listes précédente sont vides. Si c'est le cas ta complexité est... O(1). Tu prends toujours le premier élement de la première liste.
Y a pas plus efficace.
La question est pourquoi trier quand on peut classer ?
11 mai 2007 à 13:37
Si tu insères sans trié, tu insères en O(1) mais il te faut O(n) pour faire sortir l'élément
IN : O(1)
OUT: O(n)
Si tu insères trié, tu insères en O(n) mais il te faut O(1) pour faire sortir l'élément
IN : O(n)
OUT: O(1)
Si tu utilises un Heap, tu insères en O(log n) et tu fais sortir l'élément en O(log n) également
IN : O(log n)
OUT: O(log n)
Il est évident que la dernière solution est de loin la meilleure, car même si tu insères (respectivement sort) en O(1) tu vas sortir (respectivement insérer) en O(n). C'est à dire que tu sera un tout petit peu meilleur avec ton O(1) mais largement largué ensuite par ton O(n) (plus n sera élevé, plus tu seras largué)
Exemple avec 1000 éléments:
Ma solution:
IN : ~O(10)
OUT: ~O(10)
la tienne:
IN : O(1) respectivement O(1000)
OUT: O(1000) respectivement O(1)
T'es un tout petit peu meilleur avec O(1) par rapport à O(10), mais clairement très loin derrière pour O(1000) comparé à un O(10).
Je ne sais pas si tu me suis ???
11 mai 2007 à 13:21
De la même façon, en moyenne en insertion pour 1 élement tu est en O(log(n)) ou n est le nombre d'éléments déjà présents dans ta queue. Si tu dois classer l'ensemble des éléments que tu insère, il faut compter au moins une fois chaque élément O(n) que tu classes O(log(n)). Soit au total O(n*log(n)).
Pour récapituler :
+ pour 1 élement :
- tri-insertion : O(log(n))
- classement-arbre : O(1)
+ pour n élements :
- tri-insertion : O(n*log(n))
- classement-arbre : O(n)
11 mai 2007 à 13:02
Tu peux faire une recherche sur le net, tu verras qu'effectivement je ne te raconte pas de bêtise et qu'un enqueue et dequeue se font bien en O(log n) si on implémente un Heap (ce qui est, encore une fois, bien plus rapide que ton O(n) que tu proposes...)
11 mai 2007 à 12:14
Comme tu fais un tri à bulle, tu compares tous les élements à l'ensemble des autres, ce qui te fait une complexité en O(n^2)
La méthode de tri la plus rapide est le tri-fusion qui approche le O(n*log(n)) - c'est une moyenne -
La méthode de classement (et plus de tri) la plus rapide et l'arbre de classement qui permet de ranger un élement dans un arbre en fonction de sa valeur et sa complexité est en O(n) et plus précisement x*n ou x est la longueur de la valeur à classer. C'est ce que j'utilise pour répondre à ce problème.
11 mai 2007 à 12:07
Mon arbre binaire est toujours beaucoup beaucoup plus rapide avec O(log n) que ton O(n)... (en fait, incomparablement plus rapide pour des listes avec beaucoup d'éléments).
11 mai 2007 à 12:04
Si un document en priorité 1 doit passer forcement avant un document en priorité 2, tu mets ton document dans la file d'attente de priorité 1 et tu lis cette file en premier. Quand elle est vide tu lis la file de priorité 2 et ainsi de suite.
L'écriture se fait toujours à la fin de la file et la lecture se fait toujours au début. Je ne classe donc jamais les élements.
11 mai 2007 à 11:58
Pour finir, si on utilise le tris automatique de la SortedList, on se retrouve certainement (pas vérifié) avec une complexité de l'ordre de O(n^2) voire O(n log n) alors que mon implémentation avec un arbre binaire (un heap en fait) travail en O(log n) ce qui est bien meilleur (on tend presque à avoir un temps constant pour une grosse quantité d'éléments).
Warny> En utilisant ta manière, non seulement on a une place utilisée en mémoire beaucoup plus grande, mais en plus on a une complexité à coucher dehors (au moins O(n^2) je dirais au premier abord).
J'espère ne pas m'être trompé dans mes calculs, mais ça devrait être correct.
11 mai 2007 à 10:31
Une priorityqueue est avant tout une liste de queue dont certaines doivent être traités avant les autres.
Tu peux dont faire une liste de queue et revoyer le premier élement de la première queue non vide.
11 mai 2007 à 09:33