473,699 Members | 2,281 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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

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

Nov 15 '05 #1
1 1761
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(objec t obj)
{
TimePriority timePriority = obj as TimePriority;
if (timePriority != null)
{
if (this.time != timePriority.ti me)
{
return this.time < timePriority.ti me ? 1 : -1;
}
if (this.priority != timePriority.pr iority)
{
return this.priority < timePriority.pr iority ? -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.

--------------------
From: "Dan H." <Da**@projectav atar.com>
Subject: a sorted by field1 then by field2 collection, speed critical, any advice?Date: Fri, 26 Sep 2003 18:27:03 -0400
Lines: 28
X-Priority: 3
X-MSMail-Priority: Normal
X-Newsreader: Microsoft Outlook Express 6.00.2800.1158
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1165
Message-ID: <OA************ **@TK2MSFTNGP09 .phx.gbl>
Newsgroups: microsoft.publi c.dotnet.langua ges.csharp
NNTP-Posting-Host: pcp01605659pcs. vnburn01.mi.com cast.net 68.42.241.171
Path: cpmsftngxa06.ph x.gbl!TK2MSFTNG P08.phx.gbl!TK2 MSFTNGP09.phx.g bl
Xref: cpmsftngxa06.ph x.gbl microsoft.publi c.dotnet.langua ges.csharp:1876 21
X-Tomcat-NG: microsoft.publi c.dotnet.langua ges.csharp

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 objectin 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
implementati on uses a single arraylist and when i insert an object, I divideand conquer to find where I should insert. I need to find a faster solutionand was hoping someone has done some research into this already in the past.
I thank you in advance,
Dan


Nov 15 '05 #2

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

5
1430
by: perryche | last post by:
Problem #1: I have a form, which says, has 2 fields: F1 & F2 (both Dates). I want to be able to change F1 and F2 will change to be the same as F1 in the codes. However, I will still be able to change F2 at anytime if needed and changes in F2 will not affect F1. Problem #2:
2
3173
by: Brian | last post by:
NOTE ALSO POSTED IN microsoft.public.dotnet.framework.aspnet.buildingcontrols I have solved most of my Server Control Collection property issues. I wrote an HTML page that describes all of the problems that I have encountered to date and the solutions (if any) that I found. http://users.adelphia.net/~brianpclab/ServerControlCollectionIssues.htm This page also has all of the source code in a compressed file that you are free to download...
16
2596
by: Ben Hannon | last post by:
Hi, I'm writting a COM Class in VB.NET to be used in a VB6 project (Tired of the VB6 hassles with cloning and serializing an object). All my classes I need cloneable/serializable are now in a VB.NET class that exposes those objects to COM perfectly. However I ran into a problem because some of these objects requires a Collection. When I compile this project with the VB.NET Collection exposed for a property, I get a compile time error...
4
2215
by: Dave | last post by:
Hi. I am learning PyOpenGL and I am working with a largish fixed scene composed of several thousand GLtriangles. I plan to store the coords and normals in a NumPy array. Is this the fastest solution in python? would i be significantly better off (timewise or otherwise) using some other data structure to hold this information? no other data structure appears as convenient, but am i loosing valuable time? I am new to 3d programming so...
9
2061
by: burningsunorama | last post by:
Hi guys! This is maybe a too 'academic problem', but I would like to hear your opinions, something like pros and cons for each approach.... ... Recently we've had at work a little talk about the way of providing const modifier for function parameters. From my point of view are, of course, design requirements always more important and thus one should always use const keyword with parameters whose values shouldn't get changed inside a...
9
1713
by: bonk | last post by:
Does anyone have a simple example on how to prohibit that any thread other than the current thread modifies a certain object (a collection) while we are in a certain section of the code? In other words: while we are inside this codeblock whoever might think of modified that particular collection has to wait until we have left that codeblock. As far as I understand it lock() {} only prohibits that other threads enter a certain block of...
5
2632
by: WebSnozz | last post by:
Some collections are such that efficient search algorithms work on them such as binary search if the collection is a type which is sorted. I'm wondering how LINQ searches these collections and if it takes advantage of the fact that some collections are sorted? We were speculating that the standard .net 2.0 collections might implement the IQueryable interface for those collections where there are more efficient search algorithms.
18
2944
by: Hunk | last post by:
Would like some advice on the fillowing I have a sorted list of items on which i require to search and retrieve the said item and also modify an item based on its identity. I think an Map stl container would be most suited. Am i correct in my assumptions Problem Reocrds are already stored with a unique identity in a binary format.The structure is roughly ----------------------
8
2588
by: Guy | last post by:
Is there a better way to search identical elements in a sorted array list than the following: iIndex = Array.BinarySearch( m_Array, 0, m_Array.Count, aSearchedObject ); aFoundObject= m_Array; m_ResultArray.Add ( aFoundObject);
0
8697
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
9184
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
9042
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
8929
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
8891
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
1
6538
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
4380
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
4634
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
2
2357
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.