Initializing a generic SortedList with sorted data
in [Dot Net]
|
Prev: TFS 2008 Process Template: Default value tag for work item fields does not allow more than 255 characters to be entered into an HTML control
Next: alphabetizing
From: Harold Howe on 23 Jul 2008 12:22 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
From: Göran Andersson on 28 Jul 2008 03:26
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 |