Initializing a generic SortedList with sorted data   

Howdy all,

The msdn help says this about SorteList<k,v>:

"If the list is populated all at once from sorted data, SortedList is 
faster than SortedDictionary."

My question is this: how do I initialize a SortedList all at once from 
sorted data?

The only constructors that populate the container take a IDictionary as 
the source of the data. .NET Reflector shows that these constructors 
call Sort after they copy the data in, so this can't be what the help 
was referring to (never mind trying to figure out which concrete 
dictionary class can supply the sorted data).

After construction, the only way to supply values is one at a time with 
the Add method for the array indexer property. The Keys and Values 
properties are essentially read only. The Add method doesn't look like 
it will be any faster for a sequence of sorted data. Each call performs 
a full binary search to locate the insertion point. I don't see any 
optimizations for when the value is be greater that the last element.

My workaround is to do something hideously ugly involving reflection. It 
results in a nice speed improvement, but also a certain amount of shame.

H^2

date: Wed, 23 Jul 2008 11:22:30 -0500   author:   Harold Howe

Re: Initializing a generic SortedList with sorted data   

Harold Howe wrote:
> Howdy all,
> 
> The msdn help says this about SorteList<k,v>:
> 
> "If the list is populated all at once from sorted data, SortedList is 
> faster than SortedDictionary."
> 
> My question is this: how do I initialize a SortedList all at once from 
> sorted data?

You supply a list to the constructor.

> The only constructors that populate the container take a IDictionary as 
> the source of the data.

That's the one.

> .NET Reflector shows that these constructors 
> call Sort after they copy the data in, so this can't be what the help 
> was referring to (never mind trying to figure out which concrete 
> dictionary class can supply the sorted data).

Yes, it is. What the documentation means is that the sorting stage is 
fast if the data is already sorted. The constructor always sorts the 
data to verify that it is actually sorted, there is no special 
constructor for sorted data.

> After construction, the only way to supply values is one at a time with 
> the Add method for the array indexer property. The Keys and Values 
> properties are essentially read only. The Add method doesn't look like 
> it will be any faster for a sequence of sorted data. Each call performs 
> a full binary search to locate the insertion point. I don't see any 
> optimizations for when the value is be greater that the last element.
> 
> My workaround is to do something hideously ugly involving reflection. It 
> results in a nice speed improvement, but also a certain amount of shame.
> 
> H^2

If the data is already sorted, sorting it again should be so quick that 
it's hardly worth trying to circumvent it.

-- 
Göran Andersson
_____
http://www.guffa.com

date: Mon, 28 Jul 2008 09:26:24 +0200   author:   Göran Andersson