C# faster sorting than SortedList<>

Question

Hi

we have a

SortedList<Resource, Resource> resources =
    new SortedList<Resource, Resource>(new ResourceIdle());

that we use in our simulation. This list of resources is initialised in this way because we want to pass different comparers at any point in time. First problem we have is that the SortedList<> requires an extra comparison within the comparer so that we can add different instances of Resource with the same properties. For example if the Comparer looks like:

public int Compare(Resource x, Resource y)  
{  
    int priority1 = x.Priority;    
    int priority2 = y.Priority;    

    if (priority1 > priority2) { 
      return -1;  
    } else if (priority1 < priority2) {  
      return 1;  
    } else {  
      return (x.Id.CompareTo(y.Id));  
    }  
}  

then we have to make the extra comparison when priorities are the same otherwise we get back an exception for an entry with the same key. So my question is, is there another way of achieving this? And as a secondary question is there anything faster than the SortedList<> for ordering large number of objects?

Answer 1

Well, SortedDictionary<,> has different performance characteristics - it depends on what you're doing with it. MSDN has quite a lot of detail comparing the two:

The SortedDictionary<TKey, TValue> generic class is a binary search tree with O(log n) retrieval, where n is the number of elements in the dictionary. In this respect, it is similar to the SortedList<TKey, TValue> generic class. The two classes have similar object models, and both have O(log n) retrieval. Where the two classes differ is in memory use and speed of insertion and removal:

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

Answer 2

it is a requirement that the list is always sorted at any time? if not, it would definitely be faster to only sort on demand. another idea is to have the sorting be done by an "OrderPriority" which is a combination of the Priority and ID fields, therefore only one comparison needs to be made:

int OrderPriority { get { return Priority * MAX_ID + ID; } }

this assumes that the IDs do not get too large...

Answer 3

You can shorten the compare a little bit:

public int Compare(Resource x, Resource y)  
{  
    int priority1 = x.Priority;    
    int priority2 = y.Priority;    

    if (priority1 != priority2)  
        return priority2 - priority1;  

    return (x.Id.CompareTo(y.Id));  
}  

Answer 4

If you don't care about distinguishing between objects with the same priority, why not use a SortedList of buckets (implemented as a queue perhaps), with all items of equal priority in the same bucket?

Answer 5

When you create a SortedList from a dictionary, it will copy the keys and values into arrays, and then use the Array.Sort method to sort them, so that's pretty much as fast as you get, unless you have some special knowledge about the collection that could help you choose a different algorithm that is better suited for that special case.

However, it looks like you are creating a dictionary with the same key and value just to be able to use the SortedList. If that is the case, you should rather just put the items in an array or a list and sort them. The Array.Sort and List<T>.Sort methods can also use a custom comparer.

You comparer with a secondary comparison can be simplified as:

public int Compare(Resource x, Resource y) {  
  int result = x.Priority.CompareTo(y.Priority);
  if (result == 0) {
    result = x.Id.CompareTo(y.Id);  
  }
  return result;
}