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) O(log n) O(n)

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.




Professional C# 2005 with .NET 3.0
Professional C# 2005 with .NET 3.0
ISBN: 470124725
EAN: N/A
Year: 2007
Pages: 427

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net