Collections too slow? When to write your own basic types

RE: Collections too slow? When to write your own basic types

Joannes — Wed, 16 Feb 2005 13:24:00 GMT

Btw, is the SortedList implementation going to be fixed in .Net 2.0? In .Net 1.1, the implementation is such that all insertion/deletion operations cost O(n) instead of O(ln(n)) as anyone would expect for such a collection.

re: Collections too slow? When to write your own basic types

Rico Mariani — Wed, 16 Feb 2005 18:04:00 GMT

The thing about collections is they come in a lot of flavors. This particular flavor of SortedList offers this nice function:

public virtual Object GetByIndex(int index){}

But in order to offer that service (at constant time) you have to pay a price at insert time.

Of course there are other implementations of a sorted list that offer faster insertions but have no random access.

re: Collections too slow? When to write your own basic types

Steven Padfield — Wed, 16 Feb 2005 18:19:00 GMT

Thanks for the nice article, Rico. I really enjoy having resources to help make decisions, not necessarily just on what code to type.

re: Collections too slow? When to write your own basic types

Rico Mariani — Wed, 16 Feb 2005 19:53:00 GMT

It's funny that you should choose those words. I've been trying to explain what it is that an architect at Microsoft does and what I've taken to telling people is: "I'm in the decision improvement business"

Maybe I'm on to something :)

Thanks for the kind words

re: Collections too slow? When to write your own basic types

Yogesh Chhabra — Mon, 21 Feb 2005 12:06:00 GMT

How about Rule #7? Do if it improves the readability/usability of you API's.
We have an application where one of the input parameters is a Hashtable of Hashtables. So the inner Hashtable would be a collection like
Price["Widget"] = 1.01m
Price["ThingyBob"]=2.02m
and there would be a bossman collection that held these:
Store["Wallmart"] = Price1
Store["Tiffany"] = Price2

Now if we had a method like LoadData(System.Collections.IDictionary values) I would have little of no clue as to what this method actually took. What are the keys and what are the values?
If I defined a custom collection IDictionaryStringKeyDecimalValue and IDictionaryStringKeyIDictionaryStringKeyDecimalValueValue ( i.e. a fake IDictionary<String, IDictionary<String, Decimal> > ), at the risk of aggravating my RSI, I've given API consumers ( and myself! ) a pretty clear indication of what my method is expecting. They still probably need to read the docs to get a compete picture ( i.e. what are the valid string values? What exceptions does this thing throw etc) but they are in the right frame of mind before they hit F1. With code generators like CodeSmith, actually creating these things is not that painful anymore.

re: Collections too slow? When to write your own basic types

Ivan Stoev — Wed, 23 Feb 2005 12:14:00 GMT

We definitely prefer #1, but unfortunately forced to do #2. Which wasn't true with STL for instance. With the presense of generics, what was the problem BCL to expose a low level, highly customizable (via generic type parameters (traits)) collection types (preferable structs) and build current "full service" classes on top of them?
And if they are supposed to be used only for implementation (i.e. containment and delegation), why they are implemented as classes at all (instead of structs)?
The point is that in order to be able to follow Rule#1, we need much better BCL, in particular Collections.Generic - the current just brings me back to old VB6 days when we had a "great" choice between array, Collection and Dictionary - doesn't seem a big step forward?

Optimizacao de codigo Win32 e Managed

Programando .NET — Fri, 13 May 2005 14:05:14 GMT