472,347 Members | 1,682 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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

What is the data structure & algorithm that is fastest searching & sorting.

I need a fast data structure and algorithm like below condition.

(1) this data structure contain only 10,000 data entry.
(2) data structure's one entry is like below

typedef struct _DataEntry_
{
char szInput[4];
char szOutput[4];
int iSum;
} DataEntry;

(3) input data length is 100,000,000.
(4) if there is a same szInput & szOutput data in data structure when input
data, only sum iSum into found data.
(5) this data structure have only 10,000 data entry that has large number of
iSum.

if I insert one data to data structure, code like below is executed.

select data from list where szInput, szOutput;
if exist
update iSum of szInput, szOutput
sort
else
insert DataEntry
sort
end if

What is the data structure & algorithm that is fastest searching & sorting.

please~ help me~


Jul 23 '05 #1
2 6300
"yee young han" wrote
I need a fast data structure and algorithm like below condition.

(1) this data structure contain only 10,000 data entry.
(2) data structure's one entry is like below

typedef struct _DataEntry_
{
char szInput[4];
char szOutput[4];
int iSum;
} DataEntry;

(3) input data length is 100,000,000.
(4) if there is a same szInput & szOutput data in data structure when input
data, only sum iSum into found data.
(5) this data structure have only 10,000 data entry that has large number of
iSum.

if I insert one data to data structure, code like below is executed.

select data from list where szInput, szOutput;
if exist
update iSum of szInput, szOutput
sort
else
insert DataEntry
sort
end if

What is the data structure & algorithm that is fastest searching & sorting.


Your current method above is indeed very inefficient.
The slowest part therein is how often you make use of sort.
I would do the sorting only once after reading all items, or
add (or update) the items directly into a binary tree (for example
an STL unique sorted associative container like a set), in both
cases after checking/handling the duplicates.


Jul 23 '05 #2
yee young han wrote:
I need a fast data structure and algorithm like below condition.

(1) this data structure contain only 10,000 data entry.
(2) data structure's one entry is like below

typedef struct _DataEntry_
As an aside, names starting with an underscore, followed by a capital
letter are reserved for the implementation, so you really want to use a
different name. In C++ there's also no reason to use a typedef for this
situation anyway -- you can just use 'struct X' and be done with it.
{
char szInput[4];
char szOutput[4];
int iSum;
} DataEntry;

(3) input data length is 100,000,000.
(4) if there is a same szInput & szOutput data in data structure when
input data, only sum iSum into found data.
(5) this data structure have only 10,000 data entry that has large
number of iSum.


So far, what you're really describing is what you've done so far to
attempt to solve the problem -- but you haven't really told us what
problem you're trying to solve.

As such, I'm only taking a rather wild guess at the problem, but if I'm
right, I'd structure things a bit differently:

struct key {
std::string input,
output;

key(std::string in1, std::string in2) : input(in1), output(in2) {}
bool operator<(key const &other) {
if (input >= other.input)
return false;
return output < other.output;
}

friend std::ostream &operator<<(std::ostream &os, key const &k) {
os << k.input << " " << k.output;
}
};
std::map<key, int> values;

Now, let's assume (for example) that you have a file full of records,
one record per line, formatted like:

input output number

We can then process the data like:

std::string in1, in2;
int value;

while (stream >> in1) {
stream >> in2;
stream >> value;

values[key(in1, in2)] += value;
}

Since you describe keeping things sorted, it sounds like you probably
want to be able to print out the sums in order:

typedef std::pair<key, int> Vmap;

std::ostream &operator<<(std::ostream &os, Vmap const &v) {
return os << v.first << " " << v.second;
}

std::copy(values.begin(), values.end(),
std::ostream_iterator<Vmap>(std::cout, "\n"));

--
Later,
Jerry.

The universe is a figment of its own imagination.

Jul 23 '05 #3

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

Similar topics

0
by: timothy ma and constance lee | last post by:
sirs I got the data structure with repeating item like List*** name set no doc type other information
0
by: Julia Jin | last post by:
Hi, there, In my program, I use some data structure a lot, such as list, queue, prior queue, tree, etc. Right now, I chose some programs from...
3
by: Peter | last post by:
Hi All, I am looking for what may be a good data structure to use for a given problem. I have to randomly insert,delete and lookup some objects...
5
by: Alfonso Morra | last post by:
Hi, I am writing a messaging library which will allow me to send a generic message structure with custom "payloads". In many cases, a message...
1
by: New Devil | last post by:
How can i implement searching in knowledge base.What is the simplest algorithm for searching in knowledge base.and how can i implement it in C#? ...
7
by: Leszek Taratuta | last post by:
Hello, I need a kind of lightweight data structure known as "associative array". It will store a few values that I need to access using textual...
1
by: Bill Mill | last post by:
Hello all, What data structure would you use to implement something analogous to the iTunes search? I imagine that it must be a tree of some...
2
by: sprash | last post by:
I am writing a program to get the mode of a given set of numbers. As a refresher, mode is the number occuring most often in a list and 1. if 'n'...
1
by: Alan T | last post by:
I have pairs of data: peter - manager mary - secretary john - accountant alan - security What data structure is suitable for storing these...
0
better678
by: better678 | last post by:
Question: Discuss your understanding of the Java platform. Is the statement "Java is interpreted" correct? Answer: Java is an object-oriented...
0
by: teenabhardwaj | last post by:
How would one discover a valid source for learning news, comfort, and help for engineering designs? Covering through piles of books takes a lot of...
0
by: Kemmylinns12 | last post by:
Blockchain technology has emerged as a transformative force in the business world, offering unprecedented opportunities for innovation and...
0
by: Naresh1 | last post by:
What is WebLogic Admin Training? WebLogic Admin Training is a specialized program designed to equip individuals with the skills and knowledge...
0
jalbright99669
by: jalbright99669 | last post by:
Am having a bit of a time with URL Rewrite. I need to incorporate http to https redirect with a reverse proxy. I have the URL Rewrite rules made...
0
by: Matthew3360 | last post by:
Hi there. I have been struggling to find out how to use a variable as my location in my header redirect function. Here is my code. ...
2
by: Matthew3360 | last post by:
Hi, I have a python app that i want to be able to get variables from a php page on my webserver. My python app is on my computer. How would I make it...
0
hi
by: WisdomUfot | last post by:
It's an interesting question you've got about how Gmail hides the HTTP referrer when a link in an email is clicked. While I don't have the specific...
0
by: Matthew3360 | last post by:
Hi, I have been trying to connect to a local host using php curl. But I am finding it hard to do this. I am doing the curl get request from my web...

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.