Granville Barnett : DSA

DSA 0.5 released!

gbarnett — Fri, 30 May 2008 17:09:50 GMT

It's been a while, I've had to work on other stuff for the last 2 or so months which has rendered me with no time. That's the excuses out of the way...

Not much added in this release I would simply point you to the release page for more details.

A friend of mine Luca (translated to english) has joined the project now and will be helping to shape 0.6 and beyond - welcome Luca!!

Download DSA 0.5

DSA Recap

gbarnett — Thu, 08 May 2008 22:42:40 GMT

Some of you will no doubt know that I started a project a while ago now that was intent on bringing implementations of various algorithms and data structures to .NET - but with a different take on things.

Well, after a recent detour with CPUSS (a project that analyses CPU scheduling algorithms - interesting project, give it a download!) in less than a week DSA will receive a lot of time again (next Thursday signals the end of a busy spell of work).

I wanted to thank the few hundred or so who have downloaded DSA 0.4 - you're participation itself is motivation. I have some news for DSA 0.6 that is interesting but I will save that for when DSA 0.5 is released.

I am looking for suggestions of things to add to DSA 1.0 (bare in mind that graphs are on the schedule) so if you can think of a pretty rare data structure or algorithm that you think would be nice to implement then please let me know as I can see whether or not (depending on time constraints) I can get it into DSA 1.0.

The plan is to hopefully release DSA 1.0 by the end of summer (think early September) so I am really expecting things to move quick from a weeks time.

Thank you to all those who have downloaded, there are some exciting things to come!

DSA 0.4 released!

gbarnett — Thu, 21 Feb 2008 13:33:50 GMT

The latest version of the Data Structures and Algorithms (DSA) library is out!

Download DSA 0.4

This latest release contains the following additions:

QuickSort<T>
UnorderedSet<T>
Heap<T>
ShellSort<T>
InsertionSort<T>
RepeatedWordCount
ToBaseN (Binary, Octal, Hex)

Download DSA 0.4

The documentation has also had a facelift.

DSA 0.5 features will be finalized in the next few days.

Thank you to everyone who has downloaded DSA so far and the feedback provided, so far DSA has been received very well by the community and I hope this latest release will build on that.

For more details on what is in DSA 0.4 please view this page.

Thanks

DSA 0.3 released!

gbarnett — Mon, 24 Dec 2007 22:28:00 GMT

Just before Christmas as well :-)

Download DSA 0.3

New features for this release include:

Probability Search
Power algorithm
Greatest common denominator algorithm
Reverse words algorithm
Set collection (will be renamed to OrderedSet in DSA 0.4 and an unordered Set will be introduced in DSA 0.4 as well)
Sequential search
Merge sort
Merge ordered

Some other not so major features include:

Pseudo code for around 75% of everything to enable easy language ports (100% of everything will be in DSA 0.4 - the paper to screen conversion is taking a while)
Queue and Stack have been dropped - DSA will only support collections not in the BCL

ArrayList is being dropped in DSA 0.4

Complete XML documentation for every public algorithm/data structure - also private methods are XML doc'd as well.

Also this is the first release to include offline documentation (or documentation of any kind excluding XML docs).

Download DSA 0.3

DSA 0.4

This release will be out mid February and will introduce some new key algorithms and collections. I am in the process of finalizing the features to be added in DSA 0.4 but you can expect more tree data structures as well as balancing algorithms to further optimise tree data structures. I will post something when this is finalized - will be the back end of December.

Download DSA 0.3

Thank you for your support and if there is anything you would like to suggest then it is not too late...also if you find any issues please let me know.

Profiling some data structures

gbarnett — Sat, 13 Oct 2007 17:27:00 GMT

I don't know why but I randomly decided to see how well my SinglyLinkedListCollection<T> fared against the LinkedList<T> collection in System.Collections.Generic.

First off, my implementation supports pretty much everything that the MS LinkedList<T> does, that includes full LINQ support and so on.

Anyway, I added 5000 items to each to see what that would do - I actually expected the BCL data structure to be superior to mine. I had done no real magic in my implementation, I had simply coded the thing after working out the various algorithms on paper.

Memory allocation: both data structures are allocated 48 bytes total per instance, however I can only assume that the node used internally by the BCL collection has maybe another pointer i.e. it has a next and prev pointer, giving the ability to use it as a DoublyLinkedList? (I've not looked at it yet). This is where my implementation kind of wins, although I'm pretty sure at this moment that the BCL node supports doubly linked list style structures - in any case as my node is smaller than that of the BCL one my implementation after 5000 instances are created totals 160,000 bytes, the BCL one on the other hand stands at 240,000 bytes so quite a reduction there.

FYI: my node size is 32 bytes, the BCL one is 48 bytes.

Out of curiosity I also benchmarked my DoublyLinkedListCollection<T> against the LinkedList<T> of the BCL and my node size is still smaller, this time only by 8 bytes per instance but it still add's up. Same scenario, 5000 items added my implementation has been allocated 200,000 bytes where as the BCL one has been allocated 240,000 bytes - still a considerable saving, all be it slightly less.

Again, the actual data structures were allocated 48 bytes.

If you want to rip my implementations to bits then you can go ahead and download it from here: DSA 0.2.2 (you shouldn't notice any difference between these implementations and the BCL ones - both in terms of API and design time debugging experiences).

DSA 0.2 released

gbarnett — Fri, 14 Sep 2007 21:08:00 GMT

The 0.2 release of DSA has just been released, features for this release include:

ArrayListCollection(Of T)
DoublyLinkedListCollection(Of T)
SinglyLinkedListCollection(Of T)
StackCollection(Of T)
QueueCollection(Of T)

There are also a few algorithms that make there debut (very simple ones - time was consumed with the data structures):

Reverse
Any

More algorithms will be in the 0.2.1 release which is a minor release, probably with some bug fixes also :-)

All data structures are meant to be interacted with exactly (almost!) like those in the BCL, so if you find that something doesn't act the same was as the BCL equivalent then please tell me.

Download DSA 0.2.

DSA 0.1 released

gbarnett — Fri, 07 Sep 2007 10:37:00 GMT

Today, I pushed the release button on a little project I've been doing over on CodePlex entitled Data Structures and Algorithms (DSA).

The story of the project is to basically go ahead and without looking at the .NET source create custom implementations of some of the stuff in the System.Collections namespace (as well as some collections that aren't present), as well as providing algorithms for common problems - these will mainly be implemented as extension methods which were introduced in C# 3.0 to give that smooth integration with the .NET stack.

Data Structures and Algorithms (DSA) 0.1, includes:

SinglyLinkedListCollection(Of T)
QueueCollection(Of T)
StackCollection(Of T)

As well as those data structures, this release has:

VS debugging integration
LINQ support
Act like .NET collections (implement all major interfaces)
CLS compliant (C# and C++/CLI examples for download)
Full FxCop compliance

Go download it, tell me what you think and where I have gone wrong or right!

Debug proxies for custom collections to aide debugging in Visual Studio

gbarnett — Thu, 06 Sep 2007 10:24:00 GMT

I stumbled across this while working on a small project (Data Structures and Algorithms (DSA)). Creating a proxy for a type, or whatever really - in my case a collection is really simple and provides some really cool results in the locals window when debugging.

Raw View

The raw view is exactly what it implies, a no holds barred view of of type you are displaying in the locals window. The raw view by default is not expanded, instead you have a small amount of information about a particular object.

Building a Customized View

This is really simple, especially for my scenario. In the previous image you saw that Raw View was a child node of the myQueue node. The direct children of myQueue shows a simplified view of the collection in hand, i.e. it shows it's items in what appears to be an array based format - that is that it starts at 0 and goes from there. This is in fact an array.

The following is the type used for the proxy (this is actually the same as used for the collection in the BCL):

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace Dsa {

    internal sealed class CollectionDebugView<T> {

        private ICollection<T> _collection;

        public CollectionDebugView(ICollection<T> collection) {
            if (collection == null) {
                throw new ArgumentNullException("collection");
            }
            _collection = collection;
        }

        [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
        public T[] Items {
            get {
                T[] items = new T[_collection.Count];
                _collection.CopyTo(items, 0);
                return items;
            }
        }

    }

}

This debug proxy is designed to work on any collection that implements the ICollection(Of T) interface. The array like representation of the items in the collection I spoke about earlier are retrieved from the public property Items.

Note: any public properties that have getters will be visible in the locals window.

There are a few final steps that you need to go ahead and do if you want to provide this rich debug experience for your customers and that lies within the use of a few attributes.

[DebuggerDisplay("Count={Count}")]
[DebuggerTypeProxy(typeof(CollectionDebugView<>))]

The first attribute is what makes the count of the items appear level with the collection object name, Count is a property that is a member of the ICollection(Of T) interface.

The second DebuggerTypeProxyAttribute is what utilizes our debug proxy - when you expand the custom collection node we use the proxy to define what should be shown initially to the developer, the Raw View becomes a child of that simplified view. The type of the CollectionDebugView type is, like all generics determined at run time (unlike C++ which is compile time) - as we can't explicitly say what type the user will be creating a collection of we use the empty <>.