a sorted by field1 then by field2 collection, speed critical, any advice?

[Dan H.]

Hello,
I have an application that requires a collection that is sorted by a double
field first, and then by a long field.

So, lets say I have an class that has 2 fields called time, priority. I
want to put a bunch of those classes into a collection and have that
collection always stay sorted by time first, then priority. The last object
in the list should be the lowest time, highest priority object, etc, for
easy picking.

Object Time Priority
4 105 56
5 105 98
6 105 100
1 100 98
2 100 99
3 100 100

Anyone have any advice on how they would design this? My current
implementation uses a single arraylist and when i insert an object, I divide
and conquer to find where I should insert. I need to find a faster solution
and was hoping someone has done some research into this already in the past.

I thank you in advance,
Dan

 

[DoRon Motter]

Hi Dan,

You have two separate issues here. The first is comparing objects by two
fields. The second is maintaining a list of objects in sorted order.

The first one is simple, the second gets a little more complicated. To
compare objects first by time, then by priority, you would implement
IComparable for your class. However in your case time is a double. It
becomes very likely then, that the times of your objects will be distinct,
and there will be no need to compare by priority. But if that happens in
your scenario, then you would do it by implementing IComparable, your
compare function might look something like this:

public int CompareTo(object obj)
{
TimePriority timePriority = obj as TimePriority;
if (timePriority != null)
{
if (this.time != timePriority.time)
{
return this.time < timePriority.time ? 1 : -1;
}
if (this.priority != timePriority.priority)
{
return this.priority < timePriority.priority ? -1 : 1;
}
}
return 0;
}

The second issue of maintaining a sorted array of objects really depends on
what you are doing with the objects. If it is a list in which you will
insert the members only once, and then take them off the back as you imply,
you can just add them in any order to the ArrayList and then call .Sort().
The sort function will use your IComaparable implementation. Remove from
the back of the ArrayList is constant time.

If you will be adding and removing these events over time, then its likely
that you want to use a balanced binary tree or a Heap. It might be more
trouble than its worth for you to implement either of these yourself, as it
can be kind of tricky to do performantly, but you will likely be able to
find a good library somewhere online. The balanced binary tree will offer
performance and allow you to maintain a collection in sorted order while
you insert and remove elements. If you only ever need to know the lowest
time/highest priority object though, you can get by with a Heap, which
doesn't keep the elements in sorted order, but can tell you the 'min'
quickly. This will be much better than your ArrayList insert.

Do a google search on 'Balanced Binary Tree' or 'Red-Black Tree'

HTH
-DoRon


This posting is provided "AS IS" with no warranties, and confers no rights.
Use of included script samples are subject to the terms specified at
http://www.microsoft.com/info/cpyright.htm

Note: For the benefit of the community-at-large, all responses to this
message are best directed to the newsgroup/thread from which they
originated.

--------------------