Friday, November 29, 2013

.Net Collections



    he .NET Base Class Library (BCL) has a wide array of collection classes at your disposal which make it easy to manage collections of objects. While it's great to have so many classes available, it can be daunting to choose the right collection to use for any given situation. As hard as it may be, choosing the right collection can be absolutely key to the performance and maintainability of your application!

    The Generic Collections: System.Collections.Generic namespace
    The generic collections were introduced in .NET 2.0 in the System.Collections.Generic namespace. This is the main body of collections you should tend to focus on first, as they will tend to suit 99% of your needs right up front.

    It is important to note that the generic collections are unsynchronized. This decision was made for performance reasons because depending on how you are using the collections its completely possible that synchronization may not be required or may be needed on a higher level than simple method-level synchronization. Furthermore, concurrent read access (all writes done at beginning and never again) is always safe, but for concurrent mixed access you should either synchronize the collection or use one of the concurrent collections.

    The Associative Collection Classes
    Associative collections store a value in the collection by providing a key that is used to add/remove/lookup the item. Hence, the container associates the value with the key. These collections are most useful when you need to lookup/manipulate a collection using a key value. For example, if you wanted to look up an order in a collection of orders by an order id, you might have an associative collection where they key is the order id and the value is the order.

    The Dictionary (hash table)  is probably the most used associative container class. The Dictionary is the fastest class for associative lookups/inserts/deletes because it uses a hash table under the covers. Because the keys are hashed, the key type should correctly implement GetHashCode() and Equals() appropriately or you should provide an external IEqualityComparer to the dictionary on construction. The insert/delete/lookup time of items in the dictionary is amortized constant time - O(1) - which means no matter how big the dictionary gets, the time it takes to find something remains relatively constant. This is highly desirable for high-speed lookups. The only downside is that the dictionary, by nature of using a hash table, is unordered, so you cannot easily traverse the items in a Dictionary in order.

    The SortedDictionary (binary tree) is similar to the Dictionary in usage but very different in implementation. The SortedDictionary uses a binary tree under the covers to maintain the items in order by the key. As a consequence of sorting, the type used for the key must correctly implement IComparable so that the keys can be correctly sorted. The sorted dictionary trades a little bit of lookup time for the ability to maintain the items in order, thus insert/delete/lookup times in a sorted dictionary are logarithmic - O(log n). Generally speaking, with logarithmic time, you can double the size of the collection and it only has to perform one extra comparison to find the item. Use the SortedDictionary when you want fast lookups but also want to be able to maintain the collection in order by the key.

    The SortedList (sorted array) is the other sorted associative container class in the generic containers. Once again SortedList, like SortedDictionary, uses a key to sort key-value pairs. Unlike SortedDictionary, however, items in a SortedList are stored as sorted array of items. This means that insertions and deletions are linear - O(n) - because deleting or adding an item may involve shifting all items up or down in the list. Lookup time, however is O(log n) because the SortedList can use a binary search to find any item in the list by its key. So why would you ever want to do this? Well, the answer is that if you are going to load the SortedList up-front, the insertions will be slower, but because array indexing is faster than following object links, lookups are marginally faster than a SortedDictionary. Once again I'd use this in situations where you want fast lookups and want to maintain the collection in order by the key, and where insertions and deletions are rare.

    The Non-Associative Containers
    The other container classes are non-associative. They don't use keys to manipulate the collection but rely on the object itself being stored or some other means (such as index) to manipulate the collection.

    The List (dynamic array) is a basic contiguous storage container. Some people may call this a vector or dynamic array. Essentially it is an array of items that grow once its current capacity is exceeded. Because the items are stored contiguously as an array, you can access items in the List by index very quickly. However inserting and removing in the beginning or middle of the List are very costly because you must shift all the items up or down as you delete or insert respectively. However, adding and removing at the end of a List is an amortized constant operation - O(1). Typically List is the standard go-to collection when you don't have any other constraints, and typically we favor a List even over arrays unless we are sure the size will remain absolutely fixed.

    The LinkedList (doubly-linked list) is a basic implementation of a doubly-linked list. This means that you can add or remove items in the middle of a linked list very quickly (because there's no items to move up or down in contiguous memory), but you also lose the ability to index items by position quickly. Most of the time we tend to favor List over LinkedList unless you are doing a lot of adding and removing from the collection, in which case a LinkedList may make more sense.

    The HashSet is an unordered collection of unique items. This means that the collection cannot have duplicates and no order is maintained. Logically, this is very similar to having a Dictionary where the TKey and TValue both refer to the same object. This collection is very useful for maintaining a collection of items you wish to check membership against. For example, if you receive an order for a given vendor code, you may want to check to make sure the vendor code belongs to the set of vendor codes you handle. In these cases a HashSet is useful for super-quick lookups where order is not important. Once again, like in Dictionary, the type T should have a valid implementation of GetHashCode()and Equals(), or you should provide an appropriate IEqualityComparer to the HashSet on construction.

    The SortedSet (binary tree) is to HashSet what the SortedDictionary is to Dictionary. That is, the SortedSetis a binary tree where the key and value are the same object. This once again means that adding/removing/lookups are logarithmic - O(log n) - but you gain the ability to iterate over the items in order. For this collection to be effective, type T must implement IComparable or you need to supply an external IComparer.

    Finally, the Stack and Queue are two very specific collections that allow you to handle a sequential collection of objects in very specific ways. The Stack is a last-in-first-out (LIFO) container where items are added and removed from the top of the stack. Typically this is useful in situations where you want to stack actions and then be able to undo those actions in reverse order as needed. The Queue on the other hand is a first-in-first-out container which adds items at the end of the queue and removes items from the front. This is useful for situations where you need to process items in the order in which they came, such as a print spooler or waiting lines.

    So that's the basic collections. Let's summarize what we've learned in a quick reference table.

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

    The Original Collections: System.Collections namespace
    The original collection classes are largely considered deprecated by developers and by Microsoft itself. In fact they indicate that for the most part you should always favor the generic or concurrent collections, and only use the original collections when you are dealing with legacy .NET code.
    Because these collections are out of vogue, let's just briefly mention the original collection and their generic equivalents:
    • ArrayList
      • A dynamic, contiguous collection of objects.
      • Favor the generic collection List instead.
    • Hashtable
      • Associative, unordered collection of key-value pairs of objects.
      • Favor the generic collection Dictionary instead.
    • Queue
      • First-in-first-out (FIFO) collection of objects.
      • Favor the generic collection Queue instead.
    • SortedList
      • Associative, ordered collection of key-value pairs of objects.
      • Favor the generic collection SortedList instead.
    • Stack
      • Last-in-first-out (LIFO) collection of objects.
      • Favor the generic collection Stack instead.
    In general, the older collections are non-type-safe and in some cases less performant than their generic counterparts. Once again, the only reason you should fall back on these older collections is for backward compatibility with legacy code and libraries only.

    The Concurrent Collections: System.Collections.Concurrent namespace
    The concurrent collections are new as of .NET 4.0 and are included in the System.Collections.Concurrent namespace. These collections are optimized for use in situations where multi-threaded read and write access of a collection is desired.
    The concurrent queue, stack, and dictionary work much as you'd expect. The bag and blocking collection are more unique. Below is the summary of each with a link to a blog post I did on each of them.
    Summary
    The .NET BCL has lots of collections built in to help you store and manipulate collections of data. Understanding how these collections work and knowing in which situations each container is best is one of the key skills necessary to build more performant code. Choosing the wrong collection for the job can make your code much slower or even harder to maintain if you choose one that doesn’t perform as well or otherwise doesn’t exactly fit the situation.
    Remember to avoid the original collections and stick with the generic collections.  If you need concurrent access, you can use the generic collections if the data is read-only, or consider the concurrent collections for mixed-access if you are running on .NET 4.0 or higher.


    -----
      (code for Class design for most of the adv collection classes)

    1. Analyzing the Performance of Data Structures

      2. The term "running time," despite its name, does not measure the absolute time it takes the program to run, but rather refers to the number of steps the program must perform to complete the given task at hand. When working with arrays, typically the steps considered are how many array accesses one needs to perform. 
      The time it takes to search an array is linearly proportional to the number of elements in the array.
      This sort of analysis described here is called asymptotic analysis, as it examines how the efficiency of a data structure changes as the data structure's size approaches infinity. The notation commonly used in asymptotic analysis is called big-Oh notation. The big-Oh notation to describe the performance of searching an unsorted array would be denoted as O(n). The large script O is where the terminology big-Oh notation comes from, and the n indicates that the number of steps required to search an array grows linearly as the size of the array grows.
      Steps : if any step is in loop and time it takes is n - it's in two loops  it's time taken is n*n.
      To search an array time taken is "n"  - Running time = o(n).
      lower the term  inside the parenthesis for large values of n, the better the data structure's operation's performance.  asymptotic running time should be analyzed in practical scenario, it might be possible that data is less so even if o(n) is small, actual performance is less.

      Array:
      Stores homogenous type or derived type. Memory is contiguous for array elements.
      The running time of an array access (array[7] ) is denoted O(1) , irrespective of the size.
      Search time for simple array: O(n),
      Look up time : O(1).
      search time for two dimension array : o(n*n)
      Homogenous and fixed size.
      Sorted search O(Log n)

      ArrayList :
      Built on top of Array with heterogeneous data type and resizing capabilities (through reallocation). Arraylist is an array of objects and all types derived from object so any data type can be saved. But has cost of casting. Specially with value type as in arraylist value types are stored as Boxed value type i.e array stores a reference and that point to actual value type. While in array the value type is stored as unboxed value type (so no redirection is required). So cost is of boxing/unboxing  as well as of redirection.
      Binary search required values to be in sorted order if arraylist is not sorted binary search will give wrong output.

      List
      List is also built on top of array and it's generic so performance is same and no overhead.
      The Queue and Stack differ from the List class in that there are limitations on how the Queue and Stack data can be accessed.
      Requirement is to buffer (queue) the jobs for further processing - class with list and nextjobindex is inefficient because processed job memory is not reclaimed and can't be done as list is linear structure and nextJobIndex wouldn't work if we store new jobs on free available space.
      Queue is like circular array, with start and end pointers,Enqueue() and Dequque() methods  and growth factor which increase the size of queue for growthfactor=2, size get double when there is new job and no space. Jobs can be assessed in FIFO order and can't be done randomly but it has contains method to find if there is element.
      Opposite is Stack - First in last out LIFO- it has push and pop methods. It can be visualized as vertical collection of items. (used in stack trace debugger)
      The asymptotic running time of the List's operations are the same as those of the standard array's. While the List does indeed have more overhead, the relationship between the number of elements in the List and the cost per operation is the same as the standard array.




      HashTable:
      Stores item against hashkey. To generate Hashkey .Net uses object's GetHashCode function.
      There is posibbility that two objects generates the same hashcode so there are approaches for conflict resolution. Resolution is costly so all care is taken to generate the unique hashcodes.
      Linear Probing - Technique where if generated hashcode already occupied use the next available slot.
      Rehashing or double hashing - .Net hashtable uses this approach, in this couple of hash functions are used which are differ just in some multiplication factor, so first H1 will be used incase it's duplicate H2 will be used.
      The Hashtable class contains a private member variable called loadFactor that specifies the maximum ratio of items in the Hashtable to the total number of slots. A loadFactor of, say, 0.5, indicates that at most the Hashtable can only have half of its slots filled with items and the other half must remain empty. Load factor of 1 translate to 0.72 in .Net (internal to hashtable).
      Finally, realize that expanding the Hashtable is not an inexpensive operation. Therefore, if you have an estimate as to how many items you're Hashtable will end up containing, you should set the Hashtable's initial capacity accordingly in the constructor so as to avoid unnecessary expansions.
      The asymptotic access time for a Hashtable is O(1), which beats the pants off of the O(n) search time for an array.

      The Dictionary class is a type-safe Hashtable implementation, and strongly types both the keys and values. Dictionary used different conflict resolution approach called Chaining. In these any conflicts are stored in chain which is a secondary data type and is lnked to hash key in the dictionary.

      Binary Trees:  [ only one root / only one parent / no cycles ]
      the various BinaryTreeNode instances that makeup a binary tree can be scattered throughout the CLR managed heap. They are not necessarily contiguous, as are the elements of an array.
      There's no direct access to a given node as with an array. Searching a binary tree can take linear time, as potentially all nodes will need to be examined. That is, as the number of nodes in the binary tree increases, the number of steps to find an arbitrary node will increase as well.
      So, if a binary tree's lookup time is linear, and its search time is linear, how is the binary tree any better than an array, whose search time is linear, but whose lookup time is constant? Well, a generic binary tree doesn't offer us any benefit over an array. However, by intelligently organizing the items in a binary tree, we can greatly improve the search time (and therefore the lookup time as well).
      Organized binary tree efficient for search are called - Binary Search Trees (BSTs) : The principle of data storage for BSTs is that - For each node data on the left is less than the node and data on the right is greater than the node.
      The important concept to understand here is that ideally at each step in the algorithm the number of nodes that have to be considered has been cut in half. Searching a binary tree is similar in analysis to searching a sorted array. Such algorithms that exhibit this property have an asymptotic running time of log2 n, commonly abbreviated lg n.
      The time it takes to search a BST is dependent upon its topology. In the best case, the time is on the order of log2 n, but in the worst case it requires linear time.
      Since newly inserted nodes into a BST are inserted as leaves, the order of insertion directly affects the topology of the BST itself. For example, imagine we insert the following nodes into a BST: 1, 2, 3, 4, 5, and 6. When 1 is inserted, it is insert as the root. Next, 2 is inserted as 1's right child. 3 is inserted as 2's right child, 4 as 3's right child, and so on. This result in linear BST with worst search time o(n)
      Deleting nodes from a BST is slightly more difficult than inserting a node because deleting a node that has children requires that some other node be chosen to replace the hole created by the deleted node.
      A balanced tree is a tree that maintains some predefined ratio between its height and breadth. Different data structures define their own ratios for balance, but all have it close to log2 n. A self-balancing BST, then, exhibits log2 n asymptotic running time. There are numerous self-balancing BST data structures in existence, such as AVL trees, red-black trees, 2-3 trees, 2-3-4 trees, splay trees, B-trees, and others. 

      LinkedList
      Recall that with a binary tree, each node in the tree contains some bit of data and a reference to its left and right children. A linked list can be thought of as a unary tree. That is, each element in a linked list has some data associated with it, and a single reference to its neighbor.
      Linked lists have the same linear running time for searches as arrays.
      The asymptotic time required to insert a new element into a linked list depends on whether or not the linked list is a sorted list. The primary benefit of linked lists is that adding or removing items does not involve messy and time-consuming resizing. Granted, the List class hides the code complexity of this, but resizing still carries with it a performance penalty. Generic linklist class implements a doubly-linked list, which is a linked list whose nodes have a reference to both their next neighbor and their previous neighbor. 
      Skip Lists: A Linked List with Self-Balancing BST-Like Properties

      almost always use Dictionary for lookups
      On the other hand, it is faster to loop through all the elements in a List than in a Dictionary.






Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)