Showing posts with label Generics. Show all posts
Showing posts with label Generics. Show all posts
Sunday, 19 January 2014

Binomial heap

A binomial heap is a priority queue data structure similar to the binary heap only with a more strict structure, it supports quicker merging of two heaps in \(Θ(\log n)\) at the cost of a slower find minimum operation. A binomial heap is made up of a series of unique 'binomial trees' which are constructed from smaller binomial trees.

Just like a regular binary heap, the binomial heap can be either a min heap or a max heap. It also follows the properties of the heap data structure; all nodes must be smaller than their children for a min heap, or larger for a max heap.

The animations in this article will only work in certain browsers, it has been tested in the latest Chrome and Firefox.

Binomial heap
Saturday, 1 June 2013

Converting a type name into a readable string

Ever wanted to print a type name as text that the would be suitable for users? For example, converting the type name "SomeTypeName" to "Some type name".

I've come up with a pretty nice method to convert type names in to nice strings. The algorithm loops through each character in the string and determines whether to place the character as lower case or upper case and whether to insert a space based on the casing of the character and those surrounding it.

Examples

  • "TypeName" → "Type name"
  • "ABCTypeName" → "ABC type name"
  • "TypeABCName" → "Type ABC name"
  • "IMakeStuff" → "I make stuff"
Sunday, 24 February 2013

What backing data structures the .NET collections use

I've compiled some information about time complexity and underlying data structures of .NET simple collections and dictionaries. It was difficult to find some of this information on official sources like MSDN and non-official sources seemed to differ, so I used reflector and actually had a look at the .NET framework code to confirm these cases.

Simple collections

TypeData structureNotes
List<T>ArrayA regular list using a dynamic array
SortedSet<T>Red-black treeA list stored using a red-black tree

Time complexity

TypeGet ([i])FindAddInsertRemove
List\(O(1)\)\(O(n)\)\(O(1)\)*\(O(n)\)\(O(n)\)
SortedSetN/A\(O(\log n)\)\(O(\log n)\)\(O(\log n)\)\(O(\log n)\)
  • List.Add is O(n) when adding beyond the array's capacity.

Dictionaries

Dictionaries or hash tables are ideal when you either need to access the data via an arbitrary key or you need fast deletion and insertion. Note that this section doesn't the Lookup class which stores a collection of items against a key.

TypeData structureNotes
HashSet<T>Hash tableA hash table where the key is the object itself
Dictionary<TKey, TValue>Hash tableA hash table using a key not necessarily on the object being stored
SortedList<TKey, TValue>ArrayThe same as Dictionary only items and their keys are stored sorted arrays
SortedDictionary<TKey, TValue>Red-black treeThe same as Dictionary only items and their keys are stored in a red-black tree. Uses SortedSet behind the scenes

Time complexity

TypeFind by keyRemoveAdd
HashSet\(O(1)\)*\(O(1)\)*\(O(1)\)**
Dictionary\(O(1)\)*\(O(1)\)*\(O(1)\)**
SortedList\(O(\log n)\)\(O(n)\)\(O(n)\)
SortedDictionary\(O(\log n)\)\(O(\log n)\)\(O(\log n)\)
  • \(O(n)\) with collision** \(O(n)\) with collision or when adding beyond the array's capacity.

SortedList vs SortedDictionary

SortedList and SortedDictionary are best used when you need order to the items that you're storing. Here is a pretty detailed comparison from Microsoft:

The SortedList<TKey, TValue> generic class is an array of key/value pairs with \(O(\log n)\) retrieval, where \(n\) is the number of elements in the dictionary. In this, it is similar to the SortedDictionary<TKey, TValue> generic class. The two classes have similar object models, and both have \(O(\log n)\) retrieval. Where the two classes differ is in memory use and speed of insertion and removal:

  • SortedList<TKey, TValue> uses less memory than SortedDictionary<TKey, TValue>.
  • SortedDictionary<TKey, TValue> has faster insertion and removal operations for unsorted data, \(O(\log n)\) as opposed to \(O(n)\) for SortedList<TKey, TValue>.
  • If the list is populated all at once from sorted data, SortedList<TKey, TValue> is faster than SortedDictionary<TKey, TValue>.

Another difference between the SortedDictionary<TKey, TValue> and SortedList<TKey, TValue> classes is that SortedList<TKey, TValue> supports efficient indexed retrieval of keys and values through the collections returned by the Keys and Values properties. It is not necessary to regenerate the lists when the properties are accessed, because the lists are just wrappers for the internal arrays of keys and values.

MSDN - SortedList, Microsoft

References

Friday, 1 February 2013

Using enum as a generic type

Unfortunately if you want to use an enum as a generic type, the obvious way of doing it doesn't work.

private void Method<TEnum>()
    where TEnum : enum

enum is treated as a special type and Microsoft haven't implemented this (yet). However, it is possible to use enums in generics. The MSDN article for Enum gives the following type definition for the class Enum.

[SerializableAttribute]
[ComVisibleAttribute(true)]
public abstract class Enum : ValueType,
 IComparable, IFormattable, IConvertible

This definition can be used to get enums working as generic types by constraining the generic type to those of Enum. Note that we can not constrain to type ValueType due to a 'special class' rule in .NET, but we can use struct instead to get around this.

private void Method<TEnum>()
    where TEnum : struct, IConvertible, IComparable, IFormattable

The above still allows some errors to get through the compilation process, as we could specify the type of a struct that implements the IComparable, IFormattable and IConvertable interfaces. We can check the type of TEnum and confirm at runtime if it is an enum before doing any work.

private void Method<TEnum>()
    where TEnum : struct, IConvertible, IComparable, IFormattable
{
    if (!typeof(TEnum).IsEnum)
    {
        throw new ArgumentException("TEnum must be an enum.");
    }

    // ...
}

I'm not aware of a way around this that could guarantee 100% type-safety at runtime but it isn't really a big problem. After all, what are the chances that we are going to accidentally pass in a struct that implements the three interfaces.

Further reading

Saturday, 26 January 2013

Binary heap

A binary heap is binary tree structure that typically uses an array as its underlying data structure. Heaps are one of the fundamental data structures that all software developers should have in their toolkit due to the fast extraction of either a minimum or a maximum element.

Heaps come in two flavours, the min-heap which allows quick \(O(\log n)\) extraction of the minimum element, and the max-heap which allows the same for the maximum value. Before it is possible to extract values, the heap must first be constructed. This is done by going through the first half of the elements (in the array) starting from the middle and calling 'heapify' on each element, running in \(O(n)\) time.

It is typical to implement priority queues using heaps due to their \(O(\log n)\) extract min/max time.

Binary heap example
Sunday, 20 January 2013

A List<T>.BinarySearch extension that takes a lambda expression

I was thinking the other day how inconvenient it is to use List<T>.BinarySearch if you don't want to use the default comparer of T, needing to go and create a new class that implements IComparer<T>. Seems overly messy to require a whole new class just to do the binary search.

So I did a little research to see if there was a way around it and found this Jon Skeet answer (obviously) on StackOverflow. It gives a nice generic class that we can instantiate with a Comparison object and pass that into the BinarySearch method. I extended Jon's answer to take a lambda expression instead, much like you can do with List.Sort.
Sunday, 5 August 2012

Func<> and Action<> basics in C#

If you've been coding in C# for a while you may have noticed the Func<> parameter type presented in several places, particularly LINQ which uses it extensively. You may know how to use it but have you ever thought about what it is exactly and how to go about using it in your own functions?