La File à priorité (ou de priorité) n’existe pas dans .NET et pourtant elle peut rendre d’immenses services. Comment l’implémenter et s’en servir ?
Priority Queue
Cette structure de donnée est une “queue” ou plus élégamment en français un “file” (d’attente). C’est aussi une sorte de pile dont les deux représentantes les plus célèbres sont les types LIFO (Last In First Out) et FIFO (First in First Out).
L’enjeu étant de stocker de façon temporaire des objets et de les récupérer ultérieurement, mais pas n’importe comment.
Dans le cas des piles LIFO, c’est la dernière entrée et qui ressort en premier, comme une pile d’assiettes. Le plongeur lave une assiette et la pose sur la pile un fois séchée, le chef prend l’assiette du dessus pour la dresser. Il ne va pas soulever toute la pile pour prendre celle d’en dessous… Le chargeur d’un pistolet automatique (ou de mitraillette).marche de la même façon (la dernière balle insérée sera la première chargée).
La file FIFO offre un fonctionnement assez proche mais comme son nom le laisse supposer c’est l’assiette la plus ancienne posée sur la pile qui ressort en premier. Si cette situation ne convient pas à une pile d’assiettes elle s’adapte en revanche bien mieux à celle d’un file d’attente au cinéma. En dehors d’éventuels resquilleurs ce sont les premiers arrivés qui achèteront leur billet en premier et le dernier client en bout de file qui aura la surprise de savoir s’il reste ou non de la place…
Si je parle de resquilleurs c’est parce que cela existe… même en informatique.
Et si cela est fort mal vu dans une file d’attente nous savons tirer profit de ce principe en programmation. Le resquillage s’appelle alors plus joliment une “priorité”.
Par exemple les handicapés peuvent bénéficier d’un accès plus rapide à la caisse du cinéma même s’ils sont arrivés en dernier.
Bref resquiller c’est mal, mais prioriser ça peut être tout à fait légitime et ce sans remettre en cause le fonctionnement global de la file d’attente.
C’est exactement à cela que servent les files à priorité en programmation : ce sont avant tout des files LIFO comme les autres mais les objets stockés (plus généralement pointés que stockés d’ailleurs) peuvent se voir attribuer un niveau de priorité les faisant avancer plus vite dans la file. La majorité des implémentations fonctionnent un peu à l’inverse, plus le chiffre précisant la priorité est petit plus la priorité est grande (une priorité de 1 donne plus d’avantages dans la file qu’une priorité de de 2).
Beaucoup de problèmes peuvent être résolus avec une file à priorité. On peut supposer par exemple une pile de messages parmi lesquels certains doivent être traités très vite même s’ils ont été empilés plus tard.
.NET ne propose pas de file de ce genre ce qui est assez étonnant puisque les collections de tout genre sont plutôt bien représentées dans le Framework.
Il faudra donc l’implémenter soi-même.
Les tas binaires
Les tas binaires sont des structures de données parfaitement adaptées à la mise en œuvre des file à priorité (ou parle aussi de “file de priorité”) car l’accès à la valeur maximale s’effectue en temps constant.
Gérer une file de priorité pose en effet le problème des multiples insertions et suppressions qui impliquent une réorganisation des données pour gérer les priorités. On imagine bien une sorte de tri mais la mise en œuvre d’un tri à chaque opération serait très long. Les listes chainées peuvent offrir une autre voie mais elles sont délicates à maintenir. Les tas binaires sont plus simples et plus efficaces.
Au départ on peut voir un tas binaire comme un arbre binaire parfait, tous les nœuds de tous les niveaux sont remplis. Et c’est un tas, la valeur de priorité de chaque nœud est inférieure ou égale à celle de chacun de ses nœuds enfants (ou supérieure, tout dépend de l’algorithme retenu, on créé alors un “tas-max” ou un “tas-min”).
tas-max et tas-min
L’implémentation que vous choisirons utile un tas-min
Les tas-binaires qui sont des graphes ordonnés sont de précieux alliés du développeurs en de nombreuses situations car ils sont très efficaces, rechercher une valeur est proche du principe de la recherche dichotomique sur une liste triée et les temps d’accès sont parmi les meilleurs. Insérer une valeur est en revanche bien moins couteux que de trier une liste pour faire une recherche dichotomique puisqu’on ne fait qu’insérer un élément au bon emplacement ce qui ne concerne qu’un endroit très localisé de la structure de données et non celle-ci dans son ensemble.
Une liste pour support
Lorsqu’on parle d’arbre, de graphe ou de tas binaire on pense donc immédiatement à des pointeurs (ou des références managées ce qui revient un peu au même). Or l’informaticien rusé et soucieux de faire le moins de bogues a comme une résistance naturelle à utiliser ces structures de pointeurs. Elles sont difficiles à déboguer, un peu évanescentes, changeantes…
La paresse et la peur sont plutôt de bonnes conseillères dans notre métier si on sait en tirer parti de façon inventive…
C’est là que les listes font leur entrée.
On ne l’imagine pas tout de suite mais une liste peut parfaitement servir de support à un tas binaire. Cela permet d’exploiter une structure existante et bien testée dans le Framework, cela facilité le débogue (dumper une liste se fait avec un simple foreach), la libération de la mémoire de chaque item dans la liste est déjà pris en compte, bref il n’y a que des avantages.
Reste un détail… Comment transformer une simple liste en un tas binaire ?
L’astuce est algorithmique comme le plus souvent. Pour tout nœud parent qui se trouve à l’index PI (parent index) ses enfants seront stockés à (2 * PI + 1) et (2 * PI + 2). Ce qui permet aussi de savoir que pour tout nœud enfant à l’index CI (child index) le parent se trouve ((CI-1)/2).
La beauté algorithmique de cette solution n’a d’égale que sa simplicité de mise en œuvre … (mais ce qui est beau mathématiquement est souvent simple à formuler donc à coder).
Implémentation de démonstration
Ecrire un code de démonstration est une chose, s’en servir en production en est une autre. Il faudra ajouter des tests, lever des exceptions, s’assurer du bon fonctionnement en multithreading, etc. Mais chacun pourra ajouter ce qui lui semble indispensable.
Je n’ai pas trouvé beaucoup de librairies offrant une liste de priorité, il y a celle-ci (http://bit.ly/HSPQNET) que ne j’ai pas testée, si vous le faites ou si vous en connaissez d’autres n’hésitez pas à laisser un commentaire !
Les items
Pour tester notre code il nous faut des items à gérer dans la file d’attente. Pour les rendre plus facile à gérer ils implémentent IComparable<>.
public class Item : IComparable<Item>
{
public string Name { get; set; }
public int Priority {get; set;} = int.MaxValue; // plus petit = plus grande priorité
public Item(string name, int priority)
{
Name = name;
Priority = priority;
}
public override string ToString()
{
return $"({Name}, {Priority})";
}
public int CompareTo(Item other)
{
if (Priority < other.Priority) return -1;
else if (Priority > other.Priority) return 1;
else return 0;
}
}
Un nom, une priorité dont la valeur est la plus grande possible par défaut (puisque nous gérons ici un tas-min).
La file de priorité
Comme vous allez le voir le code de la file est très simple puisque toute la magie se trouve dans la conceptualisation, l’algorithme et non dans de nombreuses lignes de code complexe :
public class PriorityQueue<T> where T : IComparable<T>
{
private List<T> data;
public PriorityQueue()
{
this.data = new List<T>();
}
public int Count => data.Count;
public bool IsConsistent()
{
if (data.Count == 0) return true;
int li = data.Count - 1; // dernier index
for (int pi = 0; pi < data.Count; ++pi) // index parents
{
int lci = 2 * pi + 1; // index enfant gauche
int rci = 2 * pi + 2; // index enfant droit
if (lci <= li && data[pi].CompareTo(data[lci]) > 0) return false;
if (rci <= li && data[pi].CompareTo(data[rci]) > 0) return false;
}
return true;
}
public void Enqueue(T item)
{
data.Add(item);
int ci = data.Count - 1;
while (ci > 0)
{
int pi = (ci - 1) / 2;
if (data[ci].CompareTo(data[pi]) >= 0)
break;
T tmp = data[ci]; data[ci] = data[pi]; data[pi] = tmp;
ci = pi;
}
}
public T Dequeue()
{
if (data.Count==0) return default(T);
int li = data.Count - 1;
T frontItem = data[0];
data[0] = data[li];
data.RemoveAt(li);
--li;
int pi = 0;
while (true)
{
int ci = pi * 2 + 1;
if (ci > li) break;
int rc = ci + 1;
if (rc <= li && data[rc].CompareTo(data[ci]) < 0)
ci = rc;
if (data[pi].CompareTo(data[ci]) <= 0) break;
T tmp = data[pi]; data[pi] = data[ci]; data[ci] = tmp;
pi = ci;
}
return frontItem;
}
}
On pourrait partir de classes existantes dans le Framework ou suivre la façon dont les collections sont implémentées. Ce code n’est qu’une mise en œuvre minimaliste sans aucune dépendance.
Deux opérations sont essentielles : Enqueue et Dequeue. Toutes deux se fondent sur l’algorithme décrit plus haut.
La mise en file d’attente est plus simple à comprendre et reprend à la lettre le petit calcul évoqué dans la présentation de l’algorithme : l’item est d’abord ajouté (ce qui laisse la liste gérer sa taille et son extension si nécessaire, ce qui prépare un emplacement, etc, tout cela simplifie par force notre code). Puis on part de la fin de la liste (donc de l’item ajouté) et on calcule la place théorique de son parent selon sa priorité. Si on ne trouve pas on remontre l’arbre en suivant toujours le même parcours. Dès que l’on trouve un emplacement correct on y insère l’item par permutation.
L’ajout d’un nouvel élément à la file n’est pas instantané mais s’avère être très rapide car les opérations sont peu nombreuses. Le temps augmente en fonction de la taille de la liste mais d’une façon très légère puisque le parcours de la liste s’effectue par moitié à chaque fois (principe d’une recherche dichotomique). Le nombre maximum d’opération est ainsi de O(log n) ce qui est de très loin plus rapide que O(n log n) pour une implémentation plus simple qui n’utiliserait pas l’astuce du tas binaire…
Le code de test
Pour tester l’ensemble on ajoute une méthode à laquelle on passe le nombre d’opérations à réaliser. Elle tirera au sort l’empilage ou le dépilage des éléments. Avec une trace console on peut vérifier que les éléments ayant une plus grande priorité sorte de la file en premiers et que les éléments de même priorité sortent dans leur ordre d’entrée dans la file (ce qui est important pour conserver le sens global qui reste une gestion de file d’attente LIFO).
static void TestPriorityQueue(int numOperations)
{
var rand = new Random(0);
var pq = new PriorityQueue<Item>();
for (int op = 0; op < numOperations; ++op)
{
int opType = rand.Next(0, 2);
if (opType == 0) // enqueue
{
string lastName = op + "toto";
int priority = rand.Next(1,1000);
pq.Enqueue(new Item(lastName, priority));
Console.WriteLine($"Mise en file {lastName}, P={priority}");
if (pq.IsConsistent() == false)
{
Console.WriteLine($"Inconsistance après opération n° {op}");
}
}
else // Dequeue
{
if (pq.Count > 0)
{
var e = pq.Dequeue();
Console.WriteLine($"Dépile {e.Name}, P={e.Priority}");
if (pq.IsConsistent() == false)
{
Console.WriteLine($"Inconsistance après opération n° {op}");
}
}
}
}
Console.WriteLine("\nTests ok");
}
Le code de Main est forcément très simple :
void Main()
{
const int max = 30;
Console.WriteLine($"Test de {max} opérations");
TestPriorityQueue(max);
Console.WriteLine("Fin de test");
Console.ReadLine();
}
Conclusion
Les files de priorité sont des structures très intéressantes qui peuvent régler de nombreux problèmes dans des domaines très variés (gestion de ressources partagées, distribution de messages en réseau, etc). Il est étonnant et dommage que le Framework .NET si riche de collections en tout genre ne propose pas de telles files.
Toutefois on remarque qu’avec un minimum de ruse algorithmique on peut “vampiriser” une List<T> bien testée de .NET pour en faire un tas-binaire ultra efficace.
Je suis certain que vous y penserez maintenant que vous savez que cela existe et qu’il est facile d’en créer avec un peu d’astuce (ou par un copier / coller depuis Dot.Blog !).
Stay Tuned !