SortedList vs Own sorted array

[saurabh]

I have a list of mytype objects which need to be stored as a sorted
collection. The mytype implements IComparable. For some reason someone else
has implemented it as a normal collection. but whenever an element is added,
it calculates the insertion point and then does Array.Copy to move all the
elemnts from the insertion point to the end and then insert the new mytype
object at the insertion point, similar things for removing the element.

As mytype already implements IComparable. I have been thinking of replacing
the current collection with a SortedList and add the same object as a Key as
well as Value. This will mean that the Keys collection of sorted list will
be equivalent to the existing collection which I've got.

My question is A) Is my thinking correct or am I missing something very
obvious and B) Will I be able to gain a speed improvement by doing this?

TIA

Saurabh

 

[Bruce Wood]

Your thinking is correct. If the class implements IComparable then you
can use it as a key in the SortedList, and you might just as well put
it in as the Value, too, although it really doesn't matter.

As far as gaining a speed improvement, insertion will certainly be
faster. The current implementation you have is an insertion sort, and
SortedList is faster than that... for insertions.

As for iterating through the list in order, you may see a speed
decrease. A sorted array is usually the fastest structure to read from;
I doubt that a SortedList will be as fast.

That said, if I were you I would make the change and test the
application to see if there is a noticeable improvement or a noticeable
delay. Most programmers I've known that got bent out of shape over
"efficiency" were stressing over aspects of their programs that made no
noticeable difference whatsoever.

My advice: never "code for efficiency." Design for efficiency (don't
use patently stupid data structures and strategies in your design),
write the program as clearly as you can using the most appropriate data
structures, then test it and profile it to see if there are any problem
spots, and fix those. Otherwise, you're just chasing ghosts.

 

[saurabh]

I absolutely agree with you. By using the sorted list, my code also has
become a lot cleaner.
I'll have to admit though that I am yet to see any major gain or loss by
doing it this way. I guess for huge data the difference might be aparent.

FYI, the mytype object are actually UK postcodes which have a different
sorting mechanism (neither alphabetical nor numerical) so there was no
escape from having IComparable implementation.

 

[Bruce Wood]

It just occurred to me that if you're going to build the list of
postcodes once and then iterate through it frequently, and you have a
lot of postcodes (I'd guess over 100,000), then you could always build
the postcodes into a SortedList and then use the ToArray() method of
SortedList to copy it to an array that would allow for faster
iteration.

Of course, if you're constantly adding new postcodes and then iterating
over the list then this isn't a good option.

As well, you do realize that if you're doing postcode lookup, Hashtable
is a far superior option, although it doesn't maintain order.

 

[saurabh]

That seems to be a good idea. I may add one or 2 postcodes but that can be
done with the original insertion sort routine to maintain the order. I am
now thinking of populating the sorted list and populate the old array from
this sorted list. Not sure of any performance improvements. I do need to
iterate through the list or at least add it to the combobox on the form.

 

[Bruce Wood]

Ahh, you're putting the postcodes in a combo box. That changes things a
bit.

If I were you, I would maintain the SortedList as my master list of
postcodes. According to the MSDN documentation, you can then add the
postcodes to the combo box like this:

this.myComboBox.DataSource = myPostcodeList.GetKeyList();
this.myComboBox.DisplayMember = "PostcodeAsString"; // or whatever the
property you want to display in the combo box

According to the doc'n, GetKeyList() gets you a permanent IList into
the SortedList, so whenever the original myPostcodeList changes, the
combo box will automatically be updated to include the new postcodes.

You should be able to get the postcode back from the combo box using

this.myComboBox.SelectedItem

As for anything else you need to do with the postcodes, I wouldn't
worry too much about the speed on the SortedList. If you're searching
for one particular postcode in the list, it won't matter whether it's a
SortedList or an array unless it's in a very tight loop. The fact that
you have to load the thing into a combo box to start with will probably
take up more time than anything else.

Give the DataSource = ...GetKeyList() thing a whirl and see how it
works out for you. Let me know.