Initializing a generic SortedList with sorted data

[Harold Howe]

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 SortedDictionar y."

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

[=?ISO-8859-1?Q?G=F6ran_Andersson?=]

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 SortedDictionar y."
>
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