473,320 Members | 1,848 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Whats the best data structure for storing and sorting 2 variables of different types?

Basically, I just need a general direction on where to go for this. Yes, this is for a school project, though it's strictly an optional one (and I have tried many solutions, one in-depth). We've only covered a few types of data struct (vectors, heaps, stacks, queues, deques, lists, linked lists, priority queues, trees, etc.). I need to be able to read in a file and keep track of the number of times a word appears and then print out based first on count then lexicographically.

So, here's the problem. Whats the best structure or combination of structures to do this? The printout will be BigOh(n), no matter what. My first instinct is to read in the words and put them in a binary search tree (or a red-black, map, or multimap we haven't covered those yet and I don't know what they are) that contains a field for the word, a string, and an int count. Then, using a comparison, if string.compare == 0, increase the node's count. Sounds semi-simple, with an average BigOh(log n). Now, the ugly part (which I got to)...

You have to go back and reorder the list based on count, the lexio. That will take forever...

Ultimately, all that work made me realize I started down the wrong path from the beginning. I just need some with more experience to suggest a path (and which data structs to use) to get started in a way that will lead to some kind of solution.

So, I don't want a "here's the solution..." (but I doubt anyone would do that). I really am just looking for a general idea of where to start. And if you have some ideas, please share. I'm not looking for someone to do the work for me (I actually enjoy programming and logic behind it, but for some reasons I feel like there's a big, giant, red, flashing arrow pointing to the right path or some crucial part I need but I just can't see it for whatever reason), but try and remember a time when you looked a problem, thought about it, worked hard on it, failed and then just hit a wall..... So, any advice, comments, or thoughts would be greatly appreciated.
Mar 26 '07 #1
4 3063
PLEASE READ - Sorry, kind of important....

The number of words in the file (the words to be counted) will be in the 2,000-3,000 range. The example was an Edgar Allen Poe poem. That's kinda why brute force simply won't work.
Mar 26 '07 #2
Banfa
9,065 Expert Mod 8TB
So you need some sort of structure that holds a list of words with a count for each word?

Have you considered using an STL container ((vectors, heaps, stacks, queues, deques, lists, linked lists, priority queues, trees, etc.) to manage the list (I think you have). They manage lists of any sort variable including a class or a structure.

So create a structure (or class) that contains the data you require and then select the most appropriate STL container for the job.
Mar 26 '07 #3
Banfa
9,065 Expert Mod 8TB
Oh yeah, and on only 2000-3000 brute force probably would work, this is a computer this is what it does. Now if it were 20,000,000 - 30,000,000 you would have a point.
Mar 26 '07 #4
Ganon11
3,652 Expert 2GB
Well, I'd suggest a binary tree to sort lexicographically. The way trees are designed, the words added will always be alphabetically sorted. The trouble you will have is when you need to sort by count. Maybe you could write your own mini-tree subclasses that will sort words either by count or by the word itself - the sort method will be specified by you when you create the trees.
Mar 26 '07 #5

Sign in to post your reply or Sign up for a free account.

Similar topics

8
by: Steve Jorgensen | last post by:
Hi folks, I'm posting this message because it's an issue I come up against relatively often, but I can't find any writings on the subject, and I haven't been able to figure out even what key...
14
by: SD | last post by:
I am thinking about writing a text editor in C for unix sometime soon. I am just doing this to learn more about C. I want to write something like ed.c, a simple line editor. What types of data...
11
by: hoopsho | last post by:
Hi Everyone, I am trying to write a program that does a few things very fast and with efficient use of memory... a) I need to parse a space-delimited file that is really large, upwards fo a...
0
by: Anonieko Ramos | last post by:
ASP.NET Forms Authentication Best Practices Dr. Dobb's Journal February 2004 Protecting user information is critical By Douglas Reilly Douglas is the author of Designing Microsoft ASP.NET...
4
by: Holger Marzen | last post by:
Hi all, AFAIK it is possible for columns to be very large, up to about 2 GB. Are there any hints or experiences about storing binary data (jpg-images, pdf-documents) in PostgrreSQL with or...
3
by: ArmsTom | last post by:
I was using structures to store information read from a file. That was working fine for me, but then I read that anything stored in a structure is added to the stack and not the heap. So, I made...
5
by: Sherry | last post by:
Is there a way to automatically, or by using say a function key, call/paste into a current table or query's field the same value entered for the same field in the immediately preceeding record,...
8
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;...
3
KevinADC
by: KevinADC | last post by:
If you are entirely unfamiliar with using Perl to sort data, read the "Sorting Data with Perl - Part One and Two" articles before reading this article. Beginning Perl coders may find this article...
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....

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.