Un peu plus frais que DCR : un proto sur lequel je travaille en ce moment.

C'est une implémentation de queue avec priorité en .NET / C# 2.0. J'utilise ça pour un autre proto que je publierai probablement un de ces quatre. En gros, la queue avec priorité est une bête queue (basée sur une liste chaînée dans mon cas), pour laquelle l'insertion d'élément se fait avec une priorité. Si on insere un objet avec une priorité n, il passe devant tous les objets avec une priorité < n dans la queue. Derrière, j'utilise également un arbre AVL, donc il y a aussi une implémentation de l'AVL générique. Bon, je l'ai pas encore testée à fond, il y a quelques rotations que j'aimerais éprouver un peu plus, mais ça concerne surtout la suppression, qui n'est pas utilisée pour la queue. La queue, elle, me semble plutôt solide - je l'ai pas mal utilisée sans trop de problème. J'ai également mis une petite implémentation de l'ensembe (Set), vraiment minimaliste, et basée sur un Dictionary .NET. Je vais essayer de formaliser ça avec une interface et plusieurs implémentations (pourquoi pas une avec un AVL, ça me semble également bien adapté).

Niveau perfs, c'est pas mal en théorie. Pour l'AVL on a les complexités habituelles de ce genre de structure. Pour la queue, on est en O(1) pour Dequeue(), et O(log(nbprio)) pour Enqueue(), avec nbprio le nombre de priorités différentes utilisées. En pratique, je suis vachement déçu par l'AVL. J'ai essayé de lui mettre 1 000 000 d'éléments dans la tête, il met environ 1 seconde pour faire les insertions, mais ça reste bien plus important qu'un équivalent avec une Hashtable. Heureusement, il reprend de l'interêt sur certains algos de recherche spécifique du genre "Trouver le plus grand élément inférieur à n", où la Hashtable échoue lamentablement (je donne les résultats des tests de perf de tête, j'ai plus la classe de test sous la main - à vérifier donc).

Je pense publier des mises à jour rapidement. En particulier, les noeuds internes de l'AVL sont completement opaques à l'heure actuelle (tout en internal). Il pourrait être intéressant de publier une partie de ces noeuds (par exemple en lecture seule), un peu comme pour les LinkedList du framework .NET2, afin de laisser plus de marge de manoeuvre à l'implémentation d'algorithmes de parcours de l'arbre.

Au passage, je tiens à parler des numéros de version de mes programmes. Je vais essayer le plus souvent de mettre des numéros de type Revxxxxxx est en fait mon numéro de révision subversion. Donc faut pas vous inquiéter si je passe de la révision 10 à la révision 16, vous avez rien raté à part des build intermédiaires inutiles. Concernant l'utilisation de mes prototypes, j'ai rien contre, mais je préfère ne rien autoriser pour le moment. Demandez-moi juste avant d'utiliser, il y a pas de raison que je refuse, mais pour le moment je préfère contrôler un peu la distribution de mon code.

Télécharger PriorityQueue Rev10