IndexOf too slow on list. Faster solution?

Question

Hello, 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.

Answer 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.

Answer 2

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

Answer 3

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."

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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.