Wednesday, June 29, 2011

Choosing the Right Collection Class

In .net we have number of collection classes that are very useful in managing collections of object. But the question is which one should we use to get the best performance. The answer is that what is the scenario and the output that one requires from the collection, depending on which the selection of the collection type should be made. The following table explains the basic parameters for collections that should be kept in mind while selection the type of collection.


Collection
Ordered?
Contiguous Storage?
Direct Access?
Lookup Efficiency
Notes
Dictionary
No
Yes
Via Key
Key:
O(1)
Best for high performance lookups.
Sorted
Dictionary
Yes No Via Key Key:
O(log n)
Compromise of Dictionary speed and ordering, uses binary search tree.
SortedList
Yes
Yes
Via Key
Key:
O(log n)
Very similar to SortedDictionary, except tree is implemented in an array, so has faster lookup on preloaded data, but slower loads.
List
No
Yes
Via Index
Index: O(1)
Value: O(n)
Best for smaller lists where direct access required and no ordering.
LinkedList
No
No
No
Value:
O(n)
Best for lists where inserting/deleting in middle is common and no direct access required.
HashSet
No
Yes
Via Key
Key:
O(1)
Unique unordered collection, like a Dictionary except key and value are same object.
SortedSet
Yes
No
Via Key
Key:
O(log n)
Unique ordered collection, like SortedDictionary except key and value are same object.
Stack
No
Yes
Only Top
Top: O(1)
Essentially same as List except only process as LIFO
Queue
No
Yes
Only Front
Front: O(1)
Essentially same as List except only process as FIFO

For more read this good article.

No comments:

Post a Comment

Comments to this post

LinkWithin

Related Posts with Thumbnails