CODEWITHSUNDEEP
c#dictionarylinked-list
Richard Moss
Richard Moss

Reputation: 1620

Is there a LinkedList collection that supports dictionary type operations

I was recently profiling an application trying to work out why certain operations were extremely slow. One of the classes in my application is a collection based on LinkedList. Here's a basic outline, showing just a couple of methods and some fluff removed:

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

  }

The collection is used to store hyperlinks (represented by the LinkInfo class) in a single list. However, each hyperlink also has a list of hyperlinks which point to it, and a list of hyperlinks which it points to. Basically, it's a navigation map of a website. As this means you can having infinite recursion when links go back to each other, I implemented this as a linked list - as I understand it, it means for every hyperlink, no matter how many times it is referenced by another hyperlink, there is only ever one copy of the object.

The ID property in the above example is a GUID.

With that long winded description out the way, my problem is simple - according to the profiler, when constructing this map for a fairly small website, the indexer referred to above is called no less than 27906 times. Which is an extraordinary amount. I still need to work out if it's really necessary to be called that many times, but at the same time, I would like to know if there's a more efficient way of doing the indexer as this is the primary bottleneck identified by the profiler (also assuming it isn't lying!). I still needed the linked list behaviour as I certainly don't want more than one copy of these hyperlinks floating around killing my memory, but I also do need to be able to access them by a unique key.

Does anyone have any advice to offer on improving the performance of this indexer. I also have another indexer which uses a URI rather than a GUID, but this is less problematic as the building incoming/outgoing links is done by GUID.

Thanks; Richard Moss

Upvotes: 1

Views: 2171

Answers (2)

David Yaw
David Yaw

Reputation: 27864

You don't need to use LinkedList in order to have only one copy of each LinkInfo in memory. Remember that LinkInfo is a managed reference type, and so you can place it in any collection, and it'll just be a reference to the object that gets placed in the list, not a copy of the object itself.

That said, I'd implement the LinkInfo class as containing two lists of Guids: one for the things this links to, one for the things linking to this. I'd have just one Dictionary<Guid, LinkInfo> to store all the links. Dictionary is a very fast lookup, I think that'll help with your performance.

The fact that this[] is getting called 27,000 times doesn't seem like a big deal to me, but what's making it show up in your profiler is probably the SingleOrDefault call on the LinkedList. Linked lists are best for situations where you need fast insertions & removals, particularly in the middle of the list. For quick lookups, which is probably more important here, let the Dictionary do its work with hash tables.

Upvotes: 2

SLaks
SLaks

Reputation: 887767

You should use a Dictionary<Guid, LinkInfo>.

Upvotes: 5

Related Questions