Indexing for IndexOf

Today, a short one. But it gave me some not-so-short trouble recently.

Do you happen to use or inherit Collection or any of its subclasses (e.g. ObservableCollection)? Make sure you don’t call its IndexOf method too much. As indicated on Microsoft docs, that is an O(n) operation, and it is therefore fast only if the collection is small.

A workaround that can highly improve the application’s performance in certain situations may be storing and maintaining the collection index values within the item objects themselves. With certain assumptions, though:

  • the collection rarely changes and it’s OK if it takes slightly larger setup and update time spans;
  • the collection would never need to hold null values;
  • item objects cannot be part of multiple collection instances at the same time;
  • items for which you need to call IndexOf are surely in the collection at the time of asking the question.

Some code is available here, with an extract below:

public class Item
{
    internal int Index { get; set; } = -1;
    public object Content { get; set; }
}

public class ItemCollection : ObservableCollection
{
    public new int IndexOf(Item item)
    {
        return item.Index;
    }

    protected override void OnCollectionChanged(NotifyCollectionChangedEventArgs e)
    {
        base.OnCollectionChanged(e);

        switch (e.Action)
        {
            case NotifyCollectionChangedAction.Add:
            {
                SetManagedItems(e.NewStartingIndex, e.NewItems);
                break;
            }
            case NotifyCollectionChangedAction.Remove:
            {
                RemoveManagedItems(e.OldStartingIndex, e.OldItems);
                break;
            }
            case NotifyCollectionChangedAction.Reset:
            case NotifyCollectionChangedAction.Move:
            case NotifyCollectionChangedAction.Replace:
            {
                SetManagedItems(0, this);
                break;
            }
        }
    }

    private void SetManagedItems(int index, IList items)
    {
        foreach (Item item in items)
            item.Index = index++;
        for (var i = index; i < Count; i++)
            this[i].Index = i;
    }

    private void RemoveManagedItems(int index, IList items)
    {
        var removedCount = items.Count;
        for (var i = index; i < Count; i++)
            this[i].Index -= removedCount;
    }
}

 

Advertisements

About Sorin Dolha

My passion is software development, but I also like physics.
This entry was posted in .NET and tagged , , , . Bookmark the permalink.

Add a reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s