Performance
Many collection classes offer the same
functionality as others; for example, SortedList offers nearly the same features as
SortedDictionary. However, often there’s
a big difference in performance. While one collection consumes less
memory, the other collection class is faster with retrieval of
elements. In the MSDN documentation, you often find performance
hints with methods of the collection giving you information about
the time the operation represents in big-O
notation:
O(1) means that the time this operation needs is
constant no matter how many items are in the collection. For
example, the ArrayList has an
Add() method with O(1) behavior. No
matter how many elements are in the list, it always takes the same
time when adding a new element to the end of the list. The
Count property gives the number of
items, so it is easy to find the end of the list.
O(n) means that for every element in the collection
the same amount of additional time is needed. The Add() method of ArrayList
can be an O(n) operation if a reallocation of the collection is
required. Changing the capacity causes the copying of the list, and
the time for the copy increases linear with every element.
O(log n) means that the time needed for the
operation increases with every element in the collection. But the
increase of time for every element is not linear but logarithmic.
SortedDictionary<TKey, TValue> has
O(log n) behavior for inserting operations inside the collection,
SortedList<TKey, TValue> has O(n)
behavior for the same functionality. Here, SortedDictionary<TKey, TValue> is a lot faster
because it is more efficient to insert elements into a tree
structure than into a list.
