Initializing a generic SortedList with sorted data

  • Thread starter Thread starter Harold Howe
  • Start date Start date
H

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 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
 
Harold said:
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?
Click to expand...

You supply a list to the constructor.
The only constructors that populate the container take a IDictionary as
the source of the data.
Click to expand...

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).
Click to expand...

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
Click to expand...

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