Data structure for sorted list

I'm looking for ideas on how to create a sorted list that executes in 
the shortest possible time.

Facts about the app:
* Presently, it builds a vector from external data, then quicksorts it
* Each data node has several (potentially long) strings to sort on, 
which makes makes comparisons quite slow
* The number of nodes can vary from several dozen to tens of thousands.
* It's compiled with VC6, though if needed, an upgrade to 2008 would be 
considered

Would a binary tree be the way to go?  stl::map?  Would another 
structure execute faster than a simple quicksort?

Any thoughts would be appreciated!
0
fractal1 (9)
4/25/2008 5:48:02 PM
vc.mfc 33608 articles. 0 followers. Follow

4 Replies
564 Views

Similar Articles

[PageSpeed] 6

fractal wrote:
> 
> I'm looking for ideas on how to create a sorted list that executes in 
> the shortest possible time.
> 
> Facts about the app:
> * Presently, it builds a vector from external data, then quicksorts it
> * Each data node has several (potentially long) strings to sort on, 
> which makes makes comparisons quite slow
> * The number of nodes can vary from several dozen to tens of thousands.
> * It's compiled with VC6, though if needed, an upgrade to 2008 would be 
> considered
> 
> Would a binary tree be the way to go?  stl::map?  Would another 
> structure execute faster than a simple quicksort?
> 
> Any thoughts would be appreciated!

I should probably mention that the existing list is vector of pointers 
and is discarded after one use.
0
fractal1 (9)
4/25/2008 6:21:33 PM
(a) choose a technique
(b) measure its performance

I used std::map with a very fancy sort predicate in the PowerPoint Indexer.  The problem
was that keeping a sorted list that is incrementally updated can be expensive because you
have to qsort it after each entry, in principle.  

I'd probably try map and then see how long it took.
					joe


On Fri, 25 Apr 2008 10:48:02 -0700, fractal <fractal@fractal.com> wrote:

>
>I'm looking for ideas on how to create a sorted list that executes in 
>the shortest possible time.
>
>Facts about the app:
>* Presently, it builds a vector from external data, then quicksorts it
>* Each data node has several (potentially long) strings to sort on, 
>which makes makes comparisons quite slow
>* The number of nodes can vary from several dozen to tens of thousands.
>* It's compiled with VC6, though if needed, an upgrade to 2008 would be 
>considered
>
>Would a binary tree be the way to go?  stl::map?  Would another 
>structure execute faster than a simple quicksort?
>
>Any thoughts would be appreciated!
Joseph M. Newcomer [MVP]
email: newcomer@flounder.com
Web: http://www.flounder.com
MVP Tips: http://www.flounder.com/mvp_tips.htm
0
newcomer (15975)
4/25/2008 7:29:23 PM
On Fri, 25 Apr 2008 11:21:33 -0700, fractal <fractal@fractal.com> wrote:

>fractal wrote:
>> 
>> I'm looking for ideas on how to create a sorted list that executes in 
>> the shortest possible time.
>> 
>> Facts about the app:
>> * Presently, it builds a vector from external data, then quicksorts it
>> * Each data node has several (potentially long) strings to sort on, 
>> which makes makes comparisons quite slow
>> * The number of nodes can vary from several dozen to tens of thousands.
>> * It's compiled with VC6, though if needed, an upgrade to 2008 would be 
>> considered
>> 
>> Would a binary tree be the way to go?  stl::map?  Would another 
>> structure execute faster than a simple quicksort?
>> 
>> Any thoughts would be appreciated!
>
>I should probably mention that the existing list is vector of pointers 
>and is discarded after one use.

If I understand you correctly, you fill the data structure with all the
data it will ever hold before using it, and you never update the data
structure after you begin using it. Using std::vector and one std::sort
call sounds ideal to me, though if you only look up a handful of items, it
might be worthwhile to investigate partial_sort. (If you sort it fully, use
lower_bound to find items and binary_search just to test if they're
present.)

-- 
Doug Harrison
Visual C++ MVP
0
dsh (2498)
4/25/2008 10:18:37 PM
If add and remove operations are supported to your sorted list then
you need to use map or set.
If the keys are not unique then you need to use multimap or multiset.

Following is an excerpt from MSDN describing what is best for which
conditions

<MSDN Excerpt>
The map should be the associative container of choice when the
conditions associating the values with their keys are satisfied by the
application. A model for this type of structure is an ordered list of
uniquely occurring key words with associated string values providing,
say, definitions. If, instead, the words had more than one correct
definition, so that keys were not unique, then a multimap would be the
container of choice. If, on the other hand, just the list of words
were being stored, then a set would be the correct container. If
multiple occurrences of the words were allowed, then a multiset would
be the appropriate container structure.
</MSDN Excerpt>

If the data never changes after you built the sorted list and only
find operation is what you intend to use then I second Doug's comment.
Using std::vector with lower_bound on sorted vector performs well, and
uses less memory compared to map variants.




On Apr 26, 3:18 am, "Doug Harrison [MVP]" <d...@mvps.org> wrote:
> On Fri, 25 Apr 2008 11:21:33 -0700, fractal <frac...@fractal.com> wrote:
> >fractal wrote:
>
> >> I'm looking for ideas on how to create a sorted list that executes in
> >> the shortest possible time.
>
> >> Facts about the app:
> >> * Presently, it builds a vector from external data, then quicksorts it
> >> * Each data node has several (potentially long) strings to sort on,
> >> which makes makes comparisons quite slow
> >> * The number of nodes can vary from several dozen to tens of thousands.
> >> * It's compiled with VC6, though if needed, an upgrade to 2008 would be
> >> considered
>
> >> Would a binary tree be the way to go?  stl::map?  Would another
> >> structure execute faster than a simple quicksort?
>
> >> Any thoughts would be appreciated!
>
> >I should probably mention that the existing list is vector of pointers
> >and is discarded after one use.
>
> If I understand you correctly, you fill the data structure with all the
> data it will ever hold before using it, and you never update the data
> structure after you begin using it. Using std::vector and one std::sort
> call sounds ideal to me, though if you only look up a handful of items, it
> might be worthwhile to investigate partial_sort. (If you sort it fully, use
> lower_bound to find items and binary_search just to test if they're
> present.)
>
> --
> Doug Harrison
> Visual C++ MVP

0
somefoobar (26)
4/26/2008 7:26:27 AM
Reply:

Similar Artilces:

How do I correctly sort a list of zip codes that has both 5-digit.
How do I correctly sort a list of zip codes that has both 5-digit zip codes and nine-digit zip+4 codes? Hi Vince, Assume the zip codes populate cells A1:A100. Use a helper column, say column B. In B1 enter the formula =len(A1) and copy down to B100. Then sort A1:B100 by Column B and then Column A. --- Regards, Norman "vince48@verizon.net" <vince48@verizon.net@discussions.microsoft.com> wrote in message news:B41E9C09-972F-443D-AF0A-64927EA797CB@microsoft.com... > How do I correctly sort a list of zip codes that has both 5-digit zip > codes > and nine...

How to print one header over several columns of data
I want to print one title over a span of columns - what is the command? Format>Cells>Aligment>Horizontal>Center across selection? Gord Dibben MS Excel MVP On Thu, 27 May 2010 14:19:00 -0700, column title print <column title print@discussions.microsoft.com> wrote: >I want to print one title over a span of columns - what is the command? ...

How to count rows with changing data
I have an imported list on sheet2 and it is maybe 100 rows. Each day the data is imported the dates change along with the type of record associated with each date. Say this week there are 25 rows with 11/13, 20 rows with 11/14 and 25 rows with 11/15 and 30 rows with 11/16. Mixed in with this each of these dates might have a different type of record (each type has 4 options.) I need to be able to do the following: 1.) I need to count the number of occurrences for each date and not only show the total count but also show the date that is counted as the label. 2.)count the...

populating tree view and list view
Hi, how do i populate a tree view to show all the drives on a system and how to display the corresponding files and folders in a list view (ex.: windows-explorer). Thanx in advance. "Kapil Patry" <kapilpatry@hotmail.com> wrote in message news:#v5OqNOnEHA.3992@TK2MSFTNGP15.phx.gbl... > Hi, how do i populate a tree view to show all the drives on a system and how > to display the corresponding files and folders in a list view (ex.: > windows-explorer). > Thanx in advance. > > This is some old code I have laying around. I was just learning C++ so it needs som...

sort #5
hi all I know how to use the sort feature in excel XP and have a macro to sort data but is there anyway I can sort the data using a button/hyperlink/cell on the sheet itself? As an aside, does anyone know why I can't see the posts I make to the group but I can see all the replies? MTIA (again!) elwyn Just drag a button from the forms toolbar onto the worksheet and assign your macro to it. Don't know the answer to the second I am afraid. -- HTH RP (remove nothere from the email address if mailing direct) "elwyn" <pro4x@btinternet.com> wrote in message n...

Reorganize list
Hello! I'm not sure if this is the right Excel group to post this question in, but I am hopeful that someone can point me in the right direction: I have a worksheet where all the rows represent tasks and the columns are named "Requirements", "Build", "Test", "Deploy". The intersection of the rows and columns have a numeric value (hours). I would like to move this data into a separate worksheet where there is a row for each task, but where the columns from the original worksheet ("Requirements", "Design", "Build&quo...

rotating email recipients in list
Is there a way to setup a distribution list or some other group that the users will be in a rotation to receive the email sent to the group?? We use exchange 5.5 on a 2k box...visitors to our website would fill out a form that is then emailed to a distrobution list name. In this distrobution list are three emails. Each time the form is filled out and sent it would send to one of the emails on the list (this would rotate or cycle each time the form is filled out)...is this possible?...thanks David There is not builtin functionality to do this. You would need to write a custom event sink. -- ...

show items with no data option in pivot tables
Can anyone help with some bizarre results I'm experiencing with the show items with no values check box in the field settings menu for pivot tables. It appears to be showing field headers that don't exist in my data???? I'm using Excel 2000. Debra Dalgleish has some techniques at: http://www.contextures.com/xlPivot04.html In fact, she has an addin that you may like: http://www.contextures.com/xlPivotAddIn02.html AHuntington wrote: > > Can anyone help with some bizarre results I'm experiencing with the show > items with no values check box in the field setting...

Changing lowercase to uppercase in the Contacts list index
I am a vision impaired user who has often thought that it would be helpful to be able to see the alphabet that is vertically placed at the right side of the address book display. I have never been able to find a way to change this display and have concluded that I am stuck with the lower case letters. Anyone know of a way to change this setting? Thanks. It can't be changed. There is at least one tool that adds an index - not sure if it would help you though - see http://alphabet.4team.biz/ -- Diane Poremsky [MVP - Outlook] Outlook Tips: http://www.outlook-tips.n...

Need 2 rows to display X axis data points for a line graph
X axis is 100 data points, and all must be displayed. They do display, but are all mushed up. In Corel, you have the option to display the X axis on up to 3 rows, with interspersed tick marks. In Excel, I seem to be able only to manipulate the number of categories between tick marks and tick mark labels, but can't stagger data onto multiple rows. Any ideas or add-ins I could try? Excel 2002. Thanks, Susan This web page gives a suggestion for staggering your labels: http://peltiertech.com/Excel/Charts/Staggered.html - Jon ------- Jon Peltier, Microsoft Excel MVP Peltier Technic...

VBA and researching data thru 20.000 records
Hi, I have 2 sheets with several fields. on sheet1, i have new data and on sheet2 i have old data. i would like to update 2 fields of sheet1 with data from sheet2. for that i want to compare 3 fields, let's say C, D, E. if C, D, E are equal on sheet1 and sheet2, so i want to copy data from fields A and B (from sheet2) to fields A and B of sheet1. for now i use selection.autofilter ..... on the 3 fields to compare, but with my 20,000 records, it's really slow (on 3.1 Ghz CPU and 1 Ghz ram). So i would like to know if exists another way how to do it and for sure faster ? thanka ...

Data validation 07-26-07
I am seeking to apply form level validation for two controls in the before update event of my form. My code looks like this: Private Sub Form_BeforeUpdate(Cancel As Integer) Dim strMsg As String ' An error that is special cased. Const conErrDoCmdCancelled = 2501 On Error GoTo Err_BeforeUpdate If IsNull(Me.cboMedium) Then Cancel = True strMsg = strMsg & "Medium required." & vbCrLf End If If IsNull(Me.cboSubject) Then Cancel = True strMsg = strMsg & "Subject required." & vbCrLf End If If Can...

Make a Macro Button Look the way I want it to, not from the list
I have just gotten 2007, in the past I have set up Macro buttons for printing to different trays, for Tray 1 I made the Macro button look like the number 1, Tray 2 Macro button looked like the number 2 and Stack Bypass Macro Button had SB on it. I have managed to set up the macro buttons but I can't figure out how to customize the bottons to look how I want them to look as in not from the range made available at the time of recording the macro. See http://www.gmayor.com/Toolbars_in_word_2007.htm or http://gregmaxey.mvps.org/Ribbon_Custom_Icons.htm or http://gregmaxey.mvps....

XP vs Win 7 Contact List
Is there a way to export from XP and import into Win 7 the contacts list? Win7 does not have a built-in e-mail client. Which one are you planning on using? -- Bruce Hagen MS-MVP [Mail] Imperial Beach, CA "John Hooton" <tooh@cox.net> wrote in message news:OkhlzoWuKHA.4636@TK2MSFTNGP06.phx.gbl... > Is there a way to export from XP and import into Win 7 the contacts > list? ...

Data Validation #3
Hi, How can i prevent duplicate of data in a coloumn using data validation Hi Mohamed See http://www.cpearson.com/excel/NoDupEntry.htm -- Regards Ron de Bruin http://www.rondebruin.nl "Mohamed" <Mohamed@discussions.microsoft.com> wrote in message news:3E0FD4D8-923D-4DBC-A1FC-D89792B5BFB8@microsoft.com... > Hi, How can i prevent duplicate of data in a coloumn using data validation Hi check out http://www.cpearson.com/excel/NoDupEntry.htm for full details on how to do this. Cheers JulieD "Mohamed" <Mohamed@discussions.microsoft.com> wrote in mes...

Display Data Table in chart but don't show plot area
I am using Excel 2003. I have created some charts/graphs with data tables, chart titles, etc. My customer only wants to see the data table and chart title for each graph. Is there a way to turn off the plot area and change the size of the chart so that the chart title is close to the data table? But the data table merely reflects what is in the cells used to make the chart! Why not just display that data in a new format? Or am I missing something? best wished -- Bernard V Liengme Microsoft Excel MVP http://people.stfx.ca/bliengme remove caps from email "RW" <RW@discussi...

Clearing recently used list?
Hi, I created a test money file just so I can play around with it. I deleted the file now but it still shows up in the recently used list under the File menu. How do I go about removing it? TIA. In microsoft.public.money, KcN wrote: > >I created a test money file just so I can play around with it. I deleted >the file now but it still shows up in the recently used list under the File >menu. How do I go about removing it? You would have to search it out in the registry. What am I looking for? I searched for "test" since that's what I named my file... also ...

To Do List
On the right of my screen is the to do Bar and at the bottom where my to do list is supposed to be it shows the following: 'The Operation failed. An object could not be found'..any idea what the problem is and how I can fix it...? BTW I'm using Vista (although it worked previously so that should not be the issue) Hope someone can help........ Simon :-) Sorted........ Corrupted mail profile now fixed. "SiG226" <sig226@tiscali.co.uk> wrote in message news:67388B9A-1F2E-4947-BE68-45D69361C2B5@microsoft.com... > On the right of m...

How to clear junk senders list???
How do I clear all the items in a junk email senders list? I recently changed emails and there are so many in the old file, it it totally unmanageable. Is there a .txt file somewhere? Thanks in advance. Remove the "FOUR YOU" in my email to reply. Yes, look for Junk Senders.txt on your hard drive. -- Aloha, -Ben- Ben M. Schorr, OneNote-MVP http://home.hawaii.rr.com/schorr **I apologize but I am unable to respond to direct requests for assistance. Please post questions and replies here in the newsgroup. Mahalo! "CR" <4Uwebhound2002@hotmail.com> wrote in message...

Application Data redirection
I have a policy set to redirect users desktop and application data folders to a share. The test computer is windows XP running Office 2003. The odd thing is the folders are different on the servers vs what's on the local desktop. The server and desktop also have different files in the \Application Data\Microsoft\Outlook folder, which stores the users archive.pst file.\ The server has the following 2 files in the redirected folder Default Outlook Profile.xml Default Outlook Profile.srs The desktop has these files archive.pst extended.pst Is this behavior by default? Is there a way...

VB.net
Hi, I am trying to update a field in a record of a Access Database (whose structure I can not modify). I got this error (translated from italian): "Data types do not match in the expression" = "Tipi di dati non corrispondenti nell'espressione criterio." The code is the following: (myField is a binary field as on Access 2007) 'determine new value Dim newValue() As Byte = ... (valid data) 'write new attributes Dim conn As OleDbConnection = myObj.getConnection Dim cmd As OleDbComman...

combining data from two columns into one
Column A Column B Column C FirstName MI LastName FirstName.LastName@XXX.com Need to combine data in column A and B to make C. Can anyone help me? Thanks! ei Use a formula like: =a2&" "&b2 Regards, Fred "eintpc5146" <eintpc5146@discussions.microsoft.com> wrote in message news:B7A68BE4-41DC-46F3-B20F-737A14A5A1B4@microsoft.com... > Column A Column B Column C > > FirstName MI LastName > FirstName.LastName@XX...

Cached Outlook address list to Contacts folder?
Is there an easy way to copy addresses from the Outlook address cache to a contacts folder? How to automatically add recipient email address to contacts folder when sending email? Thanks you mean the autocomplete cache? either an addin to add people you reply to (http://www.slipstick.com/addins/contacts.htm#data) to contacts, or use http://www.ingressor.com/ -- Diane Poremsky [MVP - Outlook] Author, Teach Yourself Outlook 2003 in 24 Hours Coauthor, OneNote 2003 for Windows (Visual QuickStart Guide) Author, Google and Other Search Engines (Visual QuickStart Guide) Outlook Tips: http:/...

Formulae extracting data from other spreadsheets
I would like to write a formula to extract data from a series of workbooks whose filenames vary by month ie datajan05.xls, datafeb05.xls, etc. I would like to write the formual so it copies the month from the top of the column to create the file name ie =data[a1].xls . This would enable me then to copy across the page rather than having to edit every cell formula. Can anyone help? Thanks. have a look in help index for INDIRECT -- Don Guillett SalesAid Software donaldb@281.com "David Clark" <DavidClark@discussions.microsoft.com> wrote in message news:5BF8D6C3-96E2-4B...

Unable to see new user accounts in Global Address List
We're running Exchange 2007 and Outlook 2003. I'm able to create a new user account and send mail to the new address. However, the Outlook clients do not see the new user listed under the Global Address List. Therefore, the "Check Names" button doesn't work, and neither does sending to just the alias (w/o @domain.com). Again, emailing to the full email address does work. Is there something that needs to be set on the Exchange or Outlook side? Thanks. running Outlook in cached mode? -- Susan Conkey [MVP] "Derek" <Derek@discussions.microsoft.com>...