generic SortedDictionary and generic SortedList

[Tony Johansson]

Hi!

If we have the text at the bottom as a base for answering the question at
the bottom which answer is most appropriate ?

The choice is between Generic SortedDictionary and Generic SortedList.
So the question is which one is fastest ?
Here is some docs from MSDN but according to this I can't find which one of
Generic SortedDictionary and
Generic SortedList is the best choice.
The SortedDictionary<(Of <(TKey, TValue>)>) generic class is a binary search
tree with O(log n) retrieval, where n is the number of elements in the
dictionary. In this respect, it is similar to the SortedList<(Of <(TKey,
TValue>)>) generic class. The two classes have similar object models, and
both have O(log n) retrieval. Where the two classes differ is in memory use
and speed of insertion and removal:

SortedList<(Of <(TKey, TValue>)>) uses less memory than SortedDictionary<(Of
<(TKey, TValue>)>).

SortedDictionary<(Of <(TKey, TValue>)>) has faster insertion and removal
operations for unsorted data: O(log n) as opposed to O(n) for SortedList<(Of
<(TKey, TValue>)>).

If the list is populated all at once from sorted data, SortedList<(Of
<(TKey, TValue>)>) is faster than SortedDictionary<(Of <(TKey, TValue>)>).I
have loker



"You are using Visual Studio 2005 to create a preferred customer management
application. On the customer selection screen, the user enters the customer's
unique customer ID to pull up that customer's information. The customer
information is stored in an XML file as a serialized XML representation of a
customer objects. It is important that the customer data be displayed as
rapidly as possible. Also there is a reporting page; the report generated
from this page is going to display all customers, sorted by customer ID in
ascending order. It is extremely important that this report be generated as
rapidly as possible. What type of collection will you use to implement this
logic?"

Generic SortedDictionary
Generic Dictionary
Generic SortedList
Non-generic StringDictionary

//Tony

 

[Peter Duniho]

Hi!

If we have the text at the bottom as a base for answering the question at
the bottom which answer is most appropriate ?

Who knows? You'll have to ask the person who wrote the question, as
it's a pretty awful question.

If speed were really of utmost importance, they probably wouldn't be
storing the data in an XML file in the first place. They'd use a proper
database, most likely on a computer fast enough to exceed the
performance available on the client computer.

Beyond that, there's not really any information in the question that
would distinguish between the use cases. Enumeration of the data in
sorted order would theoretically be faster in the case of SortedList.
But if the data in the XML file isn't known to already be in the desired
sort order, it could be slower in terms of initial population of the
collection and thus for loading the file contents and displaying an
individual customer.

Having to guess at what the author of the question is really trying to
get at, I'd say SortedList is probably the answer they want. But it's
not really a very good question. There's not enough information in the
question to definitively state that SortedList is _the_ right answer.

Pete

 

[Tony Johansson]

Who knows? You'll have to ask the person who wrote the question, as it's
a pretty awful question.

If speed were really of utmost importance, they probably wouldn't be
storing the data in an XML file in the first place. They'd use a proper
database, most likely on a computer fast enough to exceed the performance
available on the client computer.

Beyond that, there's not really any information in the question that would
distinguish between the use cases. Enumeration of the data in sorted
order would theoretically be faster in the case of SortedList. But if the
data in the XML file isn't known to already be in the desired sort order,
it could be slower in terms of initial population of the collection and
thus for loading the file contents and displaying an individual customer.

Having to guess at what the author of the question is really trying to get
at, I'd say SortedList is probably the answer they want. But it's not
really a very good question. There's not enough information in the
question to definitively state that SortedList is _the_ right answer.

Pete

The answer that the book that is used for the exam find to be the best
answer is
Generic SortedDictionary

Can you understand that ?
I can't see why Generic SortedDictionary is a better choice then generic
Sortedlist
If this question had been on a real exam I might have answered generic
Sortedlist instead of
Generic SortedDictionary.


//Tony

Generic SortedDictionary

 

[Peter Duniho]

The answer that the book that is used for the exam find to be the best
answer is
Generic SortedDictionary

Can you understand that ?

No. Like I said, it's a bad question. Assuming you posted the _entire_
question, there's simply not enough information in it to make a
determination as to which class would be best.

And unless the book provides not only the answer, but _their_
justification for the answer, it will remain a mystery as to why they
feel SortedDictionary is better than SortedList.

It's possible that they are assuming the original XML is unsorted, and
they decided to optimize for the operation of constructing the original
collection (SortedDictionary is faster if the data being added is unsorted).

But since the question isn't specific about the factors involved,
there's no way to know for sure. I would expect enumeration to be (very
slightly) faster with SortedList (thus optimizing the reporting
scenario), and of course with a lower memory footprint, SortedList can
potentially have better performance due to that.

Frankly, without a real-world scenario with which to do actual
performance measurements, the two classes are basically equivalent.
They both operate in a similar fashion, with a similar interface.

Pete

 

[Konrad Neitzel]

Hi Tony!

The questions are often not that good. But the important thing is
"SortedDictionary<(Of <(TKey, TValue>)>) has faster insertion and removal
operations for unsorted data: O(log n) as opposed to O(n) for SortedList<(Of
<(TKey, TValue>)>)."

So the creation of the list from the XML is faster than the SortedList.

I remember a question that was like that one, but the given szenario was
something else. There ir was said, that an already sorted listis read once
and no inserts / removals will be done. So the correct answer in that
question was the SortedList because it is using less memory.

So I just remembered for the exam the difference with insert/removals and
less memory and that I have to keep care what actions they want to do. If it
is said that they want to add / remove items, then I will have to choose the
SortedDictionary and if no adds/removals will be done (often), I should
choose the SortedList.

That is all, that I did with this issue. The given szenarios maybe don't
make much sense. But it is of course good to know the differences between
the collections so you can choose the one that is best for your application.

Konrad