(code for Class design for most of the adv collection classes)
- Analyzing
the Performance of Data Structures
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.
