dsa Forum Rss Feed

New Post: The base class is missing.

lukadt — Thu, 11 Sep 2008 12:51:00 GMT

Sorry for the inconvenience, it has been fixed...

New Post: The base class is missing.

yuren1978 — Sat, 30 Aug 2008 13:20:40 GMT

I downloaded the latest code, and it complains that the base class is missing.

New Post: It is already in .net?

gbarnett — Sun, 27 Jul 2008 20:58:48 GMT

Quicksort is used in Array.Sort but our quicksort can be used on anything that implements IList<T>.

As for doubly linked list, I think it does use a different implementation - it is there probably because it was one of the first data structures in there. I did some perf testing a while back and our doubly linked list was faster than LinkedList<T>.

For now it will stay, unless we find a reason to get rid of it.

New Post: It is already in .net?

genbox — Sun, 27 Jul 2008 19:16:13 GMT

According to the front page: "Data Structures and Algorithms (DSA) features implementations of data structures and algorithms that are not implemented in any version of .NET."

But DoublyLinkedList is already implemented in .net? Or is it because it has a different implementation that would cause one to use DoublyLinkedList instead of LinkedList<T>?

Also, the Quick sort algorithm is also already implemented in .net in the form of Array.Sort(). It uses a unstable quick sort if I remember correctly.

New Post: A question about Fibonacci's numbers generator

lukadt — Mon, 23 Jun 2008 14:27:37 GMT

Hi Gianluca, i'm glad you are giving us interesting feedback and focus on Fibonacci complexity. Binet's formula it's very surprising and interesting at the same time but in real world there are some built-in limits for the number of decimal places one can accurately compute (floating point limited precision). Sometimes these inaccuracies will make numbers round to the wrong values and carry to inappropriate result. The approach we adopted improves the classical algorithm definition using the memory during the computation in such a way that the values of two consecutive terms of the Fibonacci sequence are always stored in the memory thus avoiding unnecessary computing...
Hear you soon, Luca

New Post: A question about Fibonacci's numbers generator

GianlucaGhettini — Sun, 22 Jun 2008 13:19:28 GMT

I looked at the Fibonacci's generator and I would ask a question about it: why did you choose to implement the generator using the iterative formula instead of the closed form version? With the iterative formula f(n)=f(n-1)+f(n-2) one has to do 'n' passes to get the n-th fibonacci's number and in this case the complexity is obviously O(n). However, the iterative formula can be "rolled up" and rewritten in closed form (the so called Binet's formula), so it is required only the 'n' to get the n-th number and the complexity drops to O(1) (a constant time!).

Here is the Binet's closed formula of the Fibonacci's series:
f(n) = floor((1/2)+((g^n)/sqrt(5))); where 'g' is the golden ratio equal to g=(1+sqrt(5))/2;

Bye!
Gianluca

New Post: Stability of sorting algorithms...

gbarnett — Sun, 22 Jun 2008 11:29:37 GMT

GianlucaGhettini wrote:
Yes, IComparable interface allows deeper control over sorting. In fact I use to reimplement this interface to get the right behavior from my sorting algorithm (i.e. sorting again over equal key objects to break the tie). However, I think that the stability is a very basic property of a sorting algorithm and it should not be left to reimplement over and over again.

Gianluca

There is a fine line between giving the programmer more control, and providing generalised solutions - all I can say is that we will look at it.

Thanks for your feedback!

Granville

New Post: Stability of sorting algorithms...

GianlucaGhettini — Sun, 22 Jun 2008 08:52:55 GMT

Yes, IComparable interface allows deeper control over sorting. In fact I use to reimplement this interface to get the right behavior from my sorting algorithm (i.e. sorting again over equal key objects to break the tie). However, I think that the stability is a very basic property of a sorting algorithm and it should not be left to reimplement over and over again.

Gianluca

New Post: Stability of sorting algorithms...

gbarnett — Sat, 21 Jun 2008 16:29:53 GMT

Hi Gianluca,

For now what I will say is that we will look into it BUT you can actually take a more atomic approach over sorting by implementing the IComparable interface on the complex types, this is what DSA sorting algorithms use to verify who is larger than who, less than etc.

Thanks for the comment and I will add it to our unofficial to-look-at list.

Thanks,

Granville

New Post: Stability of sorting algorithms...

GianlucaGhettini — Fri, 20 Jun 2008 13:55:51 GMT

Hi, good job!!!
I'm a Luca's friend and I'm currently programming in .NET (sometimes with Luca, at university).

.NET is a very powerful and interesting framework, but IHMO I think it
lacks control over sorting algorithms. What I'm trying to point out is
about stability of a sorting algorithm.
A sorting algorithm is stable if maintains the relative order of records
with equal keys (i.e., values). That is, a sorting algorithm is stable
if whenever there are two records R and S with the same key and with R
appearing before S in the original list, R will appear before S in the
sorted list.
This property isn't critical when you are dealing with base types like
integers or strings, but can be very useful when you are sorting more
complex objects. I mean, suppose you have a simple array of integers,
like this:
[6 5 2 5 1 7 1]
sorting it is straigthforward, we always obtain:
[1 1 2 5 5 6 7]
The first two integers of the sorted array are 1 1. Reversing the order
of this two integers doesn't change the array. So, for example, when you
are sorting a random array that contains two 1's, the 1 1 sequence
appearing in the sorted array will always be the same, no matter if the
algorithm you are using is stable or not.
Now think you have an array of animals, and that you are sorting by
number of legs. Now stability makes the difference:
To figure out why, suppose you have this two arrays:

[cow, snake, dog, cat, chicken, ant]

and:

[dog, ant, chicken, cow, cat]

with an unstable algorithm you can obtain:

[snake, chicken, cow, dog, cat, ant]

and:

[chicken, dog, cow, cat, ant]

with a stable algorithm:

[snake, chicken, cow, dog, cat, ant]

and:

[chicken, cow, dog, cat, ant]

As you can see, the stable version of the algorithm always preserves the
order of the sequence [cow, dog, cat] (although this order is arbitrary)
in every array containings these animals, while the other MAY not.
.NET doesn't allow the programmer to know if the sorting algorithm
he/she's using is stable or not (some algorithms can be either stable or
unstable).
I'd like to deal with a stability-aware DSA framework!!! :)

NEW POST: Comments about Set implementation

gbarnett — Fri, 22 Feb 2008 12:07:50 GMT

I'll look into it

Thanks,

Granville

mstrobel wrote:
Hi there,

I have some observations about the Set<T> class. First, a Set<T> wraps some other CollectionBase<T>, which it takes as a constructor parameter. Since there is no guarantee that the wrapped collection is a set of unique entities (it may be populated with several duplicates), then there is no guarantee that any Set<T> is actually a unique set. However, since Set<T> already implements CollectionBase<T>, I don't see why it's necessary to wrap another collection at all. Since all of the collection manipulation methods (Add, Remove, etc.) operate directly on the wrapped set, then why not simply have Set<T> extend a fully-functional collection type (e.g. a BinarySearchTree<T> with an IComparer<T> implementation that compares hashcodes) and override the Add method to include a uniqueness check?

Cheers,
Mike

NEW POST: Comments about Set implementation

mstrobel — Fri, 22 Feb 2008 02:10:41 GMT

Hi there,

I have some observations about the Set<T> class. First, a Set<T> wraps some other CollectionBase<T>, which it takes as a constructor parameter. Since there is no guarantee that the wrapped collection is a set of unique entities (it may be populated with several duplicates), then there is no guarantee that any Set<T> is actually a unique set. However, since Set<T> already implements CollectionBase<T>, I don't see why it's necessary to wrap another collection at all. Since all of the collection manipulation methods (Add, Remove, etc.) operate directly on the wrapped set, then why not simply have Set<T> extend a fully-functional collection type (e.g. a BinarySearchTree<T> with an IComparer<T> implementation that compares hashcodes) and override the Add method to include a uniqueness check?

Cheers,
Mike

NEW POST: Extension methods or static methods?

gbarnett — Thu, 21 Feb 2008 19:47:12 GMT

True. I'll admit I didn't actually try the normal route until a week or so after starting this thread - but I would encourage the ext method way as it increases the synergy between the BCL and DSA.

Thanks Mike!

mstrobel wrote:
Hi Granville,

I fully embrace extension methods. Not only do they allow for the same invocation style as instance methods, but they can also be called in the same way as regular static methods, like so:

public static class Algorithms
{
public static IList<T> BubbleSort<T>(this IList<T> source) { ... }
}

var myList = new List<T> { 5, 2, 7, 1, 8 };
var sortedList1 = myList.BubbleSort();
var sortedList2 = Algorithms.BubbleSort(myList);

Since you get the best of both worlds, it makes little sense not to use extension methods :).

Cheers,
Mike

NEW POST: Efficiency of Heap.Remove

gbarnett — Thu, 21 Feb 2008 19:45:38 GMT

Good catch. I actually added all that stuff the other day off the top of my head so bare with me on that as its sort of a skim at the moment.

Thanks for the catch.

p.s. if you find any others that are inaccurate please let me know, like I said it was skim through the source but I think the addition of this is pretty decent.

mstrobel wrote:
Hi there,

Great work on the library, and I like the addition of the new extension methods :).

I noticed that the documentation for the Heap.Remove method claims an asymptotic upper bound of O(log n). However, the first line of the method is a call to Array.IndexOf, which I believe is O(n), which is faster growing than O(log n). I haven't analyzed the method in detail, but removing that call should improve the efficiency of the method so that it actually is O(log n). I haven't looked at the efficiency of any other methods--this just happened to catch my eye as I was perusing the source code :).

Cheers,
Mike

NEW POST: Extension methods or static methods?

mstrobel — Thu, 21 Feb 2008 17:34:13 GMT

Hi Granville,

I fully embrace extension methods. Not only do they allow for the same invocation style as instance methods, but they can also be called in the same way as regular static methods, like so:

public static class Algorithms
{
public static IList<T> BubbleSort<T>(this IList<T> source) { ... }
}

var myList = new List<T> { 5, 2, 7, 1, 8 };
var sortedList1 = myList.BubbleSort();
var sortedList2 = Algorithms.BubbleSort(myList);

Since you get the best of both worlds, it makes little sense not to use extension methods :).

Cheers,
Mike

NEW POST: Efficiency of Heap.Remove

mstrobel — Thu, 21 Feb 2008 17:28:39 GMT

Hi there,

Great work on the library, and I like the addition of the new extension methods :).

I noticed that the documentation for the Heap.Remove method claims an asymptotic upper bound of O(log n). However, the first line of the method is a call to Array.IndexOf, which I believe is O(n), which is faster growing than O(log n). I haven't analyzed the method in detail, but removing that call should improve the efficiency of the method so that it actually is O(log n). I haven't looked at the efficiency of any other methods--this just happened to catch my eye as I was perusing the source code :).

Cheers,
Mike

NEW POST: Home page

gbarnett — Mon, 19 Nov 2007 18:30:45 GMT

1. Yep! You are right. But not in the way, when you are developing a library of collections. Just take a look at the PowerCollections.

I will look into this, the idea is good of the Collection suffix to differentiate the collections but if people think it is over zealous then I will modify all affected.

The PowerCollections project have either suppressed the warning altogether or just not runned code analysis - the first is more likely :-)

I have opened a work item for this for DSA 0.3, but if its what people want then its what they will get!!

The project can only get better with great feedback - thanks Ivan.

And about point 3 - yes, I don't mind the type inference but many are not ready to embrace it yet but maybe this would be a good thing to show them of its great use :-) making code more readable.

Thanks,

Granville.

NEW POST: Home page

ie — Mon, 19 Nov 2007 16:41:44 GMT

1. Yep! You are right. But not in the way, when you are developing a library of collections. Just take a look at the PowerCollections.
3. As for IEnumerable<int> I think you are right. .NET community is not ready infer types in a head yet. So, will be nice to use declarations when type of a variable is not an obvious.

Thank,
Ivan.

NEW POST: Home page

gbarnett — Mon, 19 Nov 2007 12:41:30 GMT

Hi Ivan,

1. Adding the sufficx Collection is a best practive when adding custom collections - this is an FxCop rule most tend to ignore but I chose not to as I wanted to distinguish between the DSA collections and those in the BCL.

2.
> Full support of the LINQ language extensions in .NET 3.5 for the C# 3.0 and VB 9.0 languages.
What are you doing to get full support? I think nothing. Please advice.

Actually in order to get LINQ support you need to have something that implements IEnumerable, this is old as I wanted to make claer that all collections in DSA implemented ALL standard interfaces that the BCL stuff does so you could switch in between the two without loss of functionality and I felt like LINQ was something to maybe emphasise given its coverage.

> Rich Visual Studio debugging support
It is should be by default. So, this is not an issue to take notice.

Actually if you don't specify a visualizer for a collection you get the raw view by default, with the DA stuff you get a simplified view like those in the BCL and araw view - again the point was to make it clear that DSA provides the same level of VS debugging support as the BCL stuff.

> Algorithms that solve common problems for common data structures, from linked lists to strings.
This is the most interesting! So this should be first in the list. Also, there are should be examples' list of problems, that can not be solved by .NET FLC collections and can be solved by your.

Point taken - I will work on that thank you for your feedback.

3. Ok, this is where it is offered purely out of curiosity. The fact is that implementing a Queue and Stack was easy given the other collections already done so I did them for completeleness - use whichever implementation you wish but I understand your point.

I used IEnumerable<int> because I have been using LINQ now for about a year and a half and I always used to be explicit but if people feel that var is more clearer then I would modify that.

I would also like to point out that the homepage info hasn't really been updated since DSA 0.1 which was released a while back so I will take all your points into consideration and wil revise the homepage in the next week.

Thanks,

Granville.

NEW POST: Extension methods or static methods?

gbarnett — Mon, 19 Nov 2007 12:29:01 GMT

Hi Ivan,

At the moment most of the algorithms are extension methods, however there are a few cases where they are static methods.

I have simply chosen the approach which provides most readability so if you spot something that you feel should be one or the other but isn't let me know and I will review the implementation to see if its clearer.

Thanks,

Granville.