Re: fastest sorted list type?
- From: "Peter Duniho" <NpOeStPeAdM@xxxxxxxxxxxxxxxx>
- Date: Sat, 12 Jan 2008 17:17:21 -0800
On Sat, 12 Jan 2008 16:43:37 -0800, colin <colin.rowe1@xxxxxxxxxxxxxxxxxx> wrote:
[...]
was I right in my first attempt or is there a better way ?
Do you need the data sorted before you're done collecting it? If not, then your first go at it was better. Maintaining data in sorted order is generally at least as expensive as sorting it once.
An exception to this would be a binary tree implementation, which if I recall correctly is what the non-generic SortedList class uses. A binary tree has a poor worst-case performance (but then so too can some implementations of quicksort), but for random data it's O(n log n) just like quicksort.
why is there two types of comparer functionality,
one of wich accepts a static member function,
the other a member function wich cant be static yet it still
takes two parameters, whats the this pointer used for in such cases ?
I'm not really sure which versions you're talking about, but it _sounds_ like you're asking about the difference between the one that takes a Comparison<T> and the one that takes an IComparer<T>.
The former is simply a delegate...it need not be in any class if you simply provide an anonymous method, and if it is in a class it can be a static method or an instance method (though if it's an instance method then of course you need to provide an instance from which to get the delegate reference).
The latter is an object that implements a specific interface, IComparer. IComparer defines a single method, Compare(). This method would be equivalent to the Comparison<T> delegate method.
In both cases, the comparison method compares the two parameters passed in. They basically do the same thing, the only difference being how the method is declared and then passed to the Sort() method.
sort uses either, but binary search uses the later, would this make it
slower ?
Not likely to produce a significant performance difference.
the list contains over 2 million entries, wich is why i used an array of
structs as a list of classes would require lots of allocations
Allocations in .NET are _extremely fast. In fact, I would guess that you could get a decent performance improvement using a class instead of a struct, especially if the struct is relatively large, because the data actually being moved during the sort would be smaller. It's difficult to anticipate exactly where the break-even point would be, since classes reduce your data locality which would hurt performance. But at some point they would definitely win out.
All that said, 2 million elements is a lot of data, and sorting that much data is going to be relatively slow no matter what you do. At least, until they perfect quantum computer technology and a sort can be accomplished in constant time. :)
Pete
.
- Follow-Ups:
- Re: fastest sorted list type?
- From: colin
- Re: fastest sorted list type?
- References:
- fastest sorted list type?
- From: colin
- fastest sorted list type?
- Prev by Date: fastest sorted list type?
- Next by Date: Re: modifying single frames in a multi frame tiff
- Previous by thread: fastest sorted list type?
- Next by thread: Re: fastest sorted list type?
- Index(es):
Relevant Pages
|
