Есть ли коллекция LinkedList, которая поддерживает операции типа словаря

Question

Я недавно профилировал приложение, пытающееся выяснить, почему определенные операции выполнялись крайне медленно. Одним из классов моего приложения является коллекция на основе LinkedList. Вот основная схема, показывающая всего пару методов и некоторые пуха удалены:

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); } } 

    } 

Коллекция используется для хранения гиперссылок (представлен классом LinkInfo) в одном списке. Тем не менее, каждая гиперссылка также имеет список гиперссылок, которые указывают на нее, и список гиперссылок, на которые он указывает. В принципе, это навигационная карта веб-сайта. Поскольку это означает, что вы можете иметь бесконечную рекурсию, когда ссылки возвращаются друг к другу, я реализовал это как связанный список - как я понимаю, это означает, что для каждой гиперссылки, независимо от того, сколько раз на нее ссылается другая гиперссылка, существует только когда-либо одна копия объекта.

Свойство ID в приведенном выше примере - это идентификатор GUID.

С этим длинным изложением описания, моя проблема проста - согласно профилировщику при построении этой карты для довольно небольшого сайта упомянутый выше указатель называется не менее чем 27906 раз. Это необычайная сумма. Мне все же нужно разобраться, действительно ли нужно называть это много раз, но в то же время я хотел бы знать, есть ли более эффективный способ сделать индексатор, поскольку это основное узкое место, идентифицированное профилировщиком (также предполагая, что он не лжет!). Мне все еще нужно поведение связанного списка, поскольку я, конечно, не хочу больше, чем один экземпляр этих гиперссылок, плавающих вокруг убийства моей памяти, но я также должен иметь доступ к ним с помощью уникального ключа.

Есть ли у кого-нибудь советы по улучшению производительности этого индексатора. У меня также есть еще один индекс, который использует URI, а не GUID, но это менее проблематично, поскольку входящие/исходящие ссылки здания выполняются с помощью GUID.

Thanks; Richard Moss

Answer 1

Вы должны использовать Dictionary<Guid, LinkInfo>.

Answer 2

Вам не нужно использовать LinkedList, чтобы иметь только одну копию каждого LinkInfo в памяти. Помните, что LinkInfo является управляемым ссылочным типом, поэтому вы можете поместить его в любую коллекцию, и это будет просто ссылкой на объект, который помещается в список, а не на копию самого объекта.

Было сказано, что я бы применил класс LinkInfo, содержащий два списка гидов: один для вещей, к которым это относится, одно для вещей, связанных с этим. У меня будет только один Dictionary<Guid, LinkInfo>, чтобы сохранить все ссылки. Словарь очень быстрый поиск, я думаю, что это поможет с вашей работой.

Тот факт, что этот [] получил название 27 000 раз, не кажется для меня большой проблемой, но то, что делает его отображаемым в вашем профилировщике, вероятно, является вызовом SingleOrDefault на LinkedList. Связанные списки лучше всего подходят для ситуаций, когда вам нужны быстрые вставки & удаления, особенно в середине списка. Для быстрого поиска, который, вероятно, более важен здесь, пусть словарь выполняет свою работу с хэш-таблицами.