IndexOf too slow on list. Faster solution?
Asked Answered
N

9

14

I have generic list which must be a preserved order so I can retrieve the index of an object in the list. The problem is IndexOf is way too slow. If I comment the IndexOf out, the code runs fast as can be. Is there a better way, such as a preserved ordered hash list for c#?

Thanks, Nate

  • Edit - The order in which the items are added/inserted is the order it needs to be. No sorting on them is necessary. Also this list has the potential to be updated often, add, remove, insert. Basically I need to translate the object to an index due to them being represented in a grid control so I can perform operations on the grid control based on index.
Nonmaterial answered 2/7, 2009 at 17:40 Comment(7)
Code? What are you storing in the list? does order matter?Holston
Are you trying to retrieve the object itself or just the index of the object?Torticollis
More details on what you doing?Castleman
Could you please be more specific? What operations are you doing that make indexOf so slow? Are you looking to optimize for lookups? What are your speed requirements for insertions/deletions? Do you need the collection of items to be contiguous? Can you use a HashSet instead?Road
Ordered means sorted, or means that the order must be preserved?Cilice
Sorry, went to meeting and then lunch. Need a few mins to go over answers. I need to maintain the order at which they were added into the list.Nonmaterial
In reply to DavidN, insert and removal are ok to be slower, obviously not dog slow. Getting the index of the item in the list is the most important part for performance since it is done often. Yes the items must maintain the order they were added to the list.Nonmaterial
C
14

If it's not sorted, but the order needs to be preserved, then you could have a separate Dictionary<YourClass, int> which would contain the index for each element.

If you want a sorted list, then check previous posts - you can use SortedList<Tkey, TValue> in .Net 3.5, or sort it and use BinarySearch in older .Net versions.

[Edit] You can find similar examples on the web, e.g.: OrderedList. This one internally uses an ArrayList and a HashTable, but you can easily make it generic.

[Edit2] Ooops.. the example I gave you doesn't implement IndexOf the way I described at the beginning... But you get the point - one list should be ordered, the other one used for quick lookup.

Cilice answered 2/7, 2009 at 17:53 Comment(4)
I have considered using the dictionary approach. The thing I don't like about it is have to update every entry in the dictionary that comes after the insert/delete. But I haven't ruled this out yet.Nonmaterial
You can't speed up IndexOf without compromising a bit of speed during insert/delete...Pinfish
What I ended up doing, and the performance gain was pretty good, was memoized the indexes of the objects in the list by adding the object to a dicionary as the key and the index as a value when IndexOf was called. That way if it was called again it could just look up the value in the dictionary. If the list changes at all, I just clear the dictionary. Another answer was similiar to this below, but I will mark this one as the answer because it has more votes.Nonmaterial
@NastyNateDoggy: that's sounds like the best solution - lazy caching will lower the memory usage.Cilice
W
9

Sort it using List<T>.Sort, then use the List<T>.BinarySearch method: "Searches the entire sorted List(T) for an element [...] This method is an O(log n) operation, where n is the number of elements in the range."

Wrand answered 2/7, 2009 at 17:45 Comment(0)
Y
6

See the bottom of this article here.

It appears that writing your own method to retrieve the index is much quicker than using the IndexOf method, due to the fact that it calls into a virtual method depending on the type.

Something like this may therefore improve your performance. I wrote a small unit test to verify that this improves the performance of the search, and it did, by about 15x in a list with 10,000 items.

static int GetIndex(IList<Item> list, Item value)
{
    for (int index = 0; index < list.Count; index++)
    {
        if (list[index] == value)
        {
             return index;
        } 
    }
    return -1;
}
Yearning answered 25/11, 2011 at 9:21 Comment(2)
How is that code to be used? I get "The type or namespace name 'Item' could not be found.Fonda
@Fonda you should replace "Item" with the type of item stored in your list. So if you have "IList<Contact>", then the you'd replace "Item" with "Contact" for example.Yearning
C
3

Perhaps you are looking for SortedList<TKey, TValue>?

Cosme answered 2/7, 2009 at 17:43 Comment(1)
I believe he only meant "with preserved order", not sorted.Cilice
C
3

If the order of the objects in the list has to be preserved then the only way I can think of where you're going to get the fastest possible access is to tell the object what its index position is when its added etc to the list. That way you can query the object to get its index in the list. The downside, and its a big downside in my view, is that the inserted objects now have a dependency on the list.

Coverley answered 2/7, 2009 at 19:55 Comment(1)
Thanks for the reply. I had considered this also, but choose to go with what I described in a comment under the accepted answer.Nonmaterial
U
2

I suggest to use the SortedList<TKey, TValue> or SortedDictionary<TKey, TValue> class if you need the items sorted. The differences are the following.

  • SortedList<TKey, TValue> uses less memory than SortedDictionary<TKey, TValue>.

  • SortedDictionary<TKey, TValue> has faster insertion and removal operations for unsorted data: O(log n) as opposed to O(n) for SortedList<TKey, TValue>.

  • If the list is populated all at once from sorted data,SortedList<TKey, TValue> is faster than SortedDictionary<TKey, TValue>.

If you just want to preserve the ordering, you can just use a Dictionary<TKey, TValue> and store the item as key and the index as value. The drawback is that reordering the items, insertions, or deletion are quite expensive to do.

Underage answered 2/7, 2009 at 17:51 Comment(1)
Yes the dictionary is an approach I have thought about, but adds a level of maintenance and performance penalty.Nonmaterial
P
1

Well there is no reason you should ever have to order a hash list...that's kind of the point. However, a hash list should do the trick quite readily.

Photon answered 2/7, 2009 at 17:43 Comment(0)
O
1

If you are using the List class then you could use the Sort method to sort it after is initially populated then use the BinarySearch Method to find the appropriate element.

Outsmart answered 2/7, 2009 at 17:46 Comment(0)
C
1

I'm not sure about specifics in C#, but you might be able to sort it (QuickSort?) and then use a binary search on it (BinarySearch performance is O(log2(N)), versus Sequential, such as indexOf, which is O(n)). (IMPORTANT: For a Binary Search, your structure must be sorted)

When you insert items to your data structure, you could try a modified binary search to find the insertion point as well, or if you are adding a large group, you would add them and then sort them.

The only issue is that insertion will be slower.

Chalcidice answered 2/7, 2009 at 17:53 Comment(0)

© 2022 - 2024 — McMap. All rights reserved.