Y a-t-il une collection LinkedList qui supporte les opérations de type dictionnaire?

Question

J'ai récemment profilé une application essayant de comprendre pourquoi certaines opérations étaient extrêmement lentes. L'une des classes de mon application est une collection basée sur LinkedList. Voici un aperçu de base, montrant seulement quelques méthodes et quelques peluches enlevés:

public class LinkInfoCollection : PropertyNotificationObject, IEnumerable<LinkInfo> 
    { 

    private LinkedList<LinkInfo> _items; 

    public LinkInfoCollection() 
    { 
     _items = new LinkedList<LinkInfo>(); 
    } 

    public void Add(LinkInfo item) 
    { 
     _items.AddLast(item); 
    } 

    public LinkInfo this[Guid id] 
    { get { return _items.SingleOrDefault(i => i.Id == id); } } 

    } 

La collection est utilisée pour stocker des hyperliens (représenté par la classe LinkInfo) dans une seule liste. Cependant, chaque lien hypertexte a également une liste de liens hypertexte qui pointent vers lui, et une liste de liens hypertexte vers laquelle il pointe. Fondamentalement, c'est une carte de navigation d'un site Web. Comme cela signifie que vous pouvez avoir une récursion infinie lorsque les liens se renvoient les uns aux autres, j'ai implémenté ceci comme une liste chaînée - si je comprends bien, cela signifie pour chaque lien hypertexte, peu importe combien de fois il est référencé par un autre lien hypertexte. jamais une copie de l'objet.

La propriété ID dans l'exemple ci-dessus est un GUID. Avec cette longue description, mon problème est simple - selon le profileur, lors de la construction de cette carte pour un site Web relativement petit, l'indexeur mentionné ci-dessus est appelé au moins 27906 fois. Ce qui est un montant extraordinaire. Je dois encore m'entraîner s'il est vraiment nécessaire d'être appelé plusieurs fois, mais en même temps, j'aimerais savoir s'il y a une façon plus efficace de faire l'indexeur car c'est le goulot d'étranglement principal identifié par le profileur (aussi en supposant que ce n'est pas mentir!). J'avais toujours besoin du comportement de la liste chaînée car je ne veux certainement pas que plus d'une copie de ces hyperliens flotte autour de ma mémoire, mais je dois aussi pouvoir y accéder par une clé unique.

Quelqu'un a-t-il des conseils à donner pour améliorer les performances de cet indexeur? J'ai aussi un autre indexeur qui utilise un URI plutôt qu'un GUID, mais c'est moins problématique car la construction des liens entrants/sortants est faite par GUID.

Merci; Richard Moss

Answer 1

Vous devez utiliser un Dictionary<Guid, LinkInfo>.

Answer 2

Vous n'avez pas besoin d'utiliser LinkedList pour avoir une seule copie de chaque LinkInfo en mémoire. Rappelez-vous que LinkInfo est un type de référence géré, et que vous pouvez donc le placer dans n'importe quelle collection, et ce sera juste une référence à l'objet placé dans la liste, pas une copie de l'objet lui-même. Cela dit, j'implémenterais la classe LinkInfo comme contenant deux listes de Guids: une pour les choses auxquelles elle est liée, une pour les objets qui y sont liés. J'aurais juste un Dictionary<Guid, LinkInfo> pour stocker tous les liens. Le dictionnaire est une recherche très rapide, je pense que cela aidera votre performance. Le fait que ce [] soit appelé 27 000 fois ne me semble pas être un gros problème, mais ce qui le fait apparaître dans votre profileur est probablement l'appel SingleOrDefault sur le LinkedList. Les listes liées sont les mieux adaptées aux situations nécessitant des insertions rapides, en particulier au milieu de la liste. Pour des recherches rapides, ce qui est probablement plus important ici, laissez le dictionnaire faire son travail avec les tables de hachage.