473,836 Members | 1,477 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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 6471
"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(value s.begin(), values.end(),
std::ostream_it erator<Vmap>(st d::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
1336
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
1630
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 "Mastering Algorithms With C " by Kyle Loudon. But I do not like the way that it manage the memory. So I want to find another better C library that has the implementation of those basic data structure and algorithm so that I can reuse. Can somebody give me some good examples?
3
2253
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 - all three being equally probable. The number of objects is in the thousands. The keys are non integers ( but I can probably hash them to integers if need be). To start with I have used a hash based approach. A lot of people where
5
4809
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 must store a non-linear data structure (i.e. "payload") using pointers. Examples of these are binary trees, hash tables etc. Thus, the message itself contains only a pointer to the actual data. When the message is sent to the same processor, these pointers point to the original locations, which...
1
1658
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#? Posted Via Usenet.com Premium Usenet Newsgroup Services ---------------------------------------------------------- ** SPEED ** RETENTION ** COMPLETION ** ANONYMITY ** ---------------------------------------------------------- http://www.usenet.com
7
3135
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 keys. The Hashtable is too heavy for me. I also need to serialize data to Session state or View State (in ASP.NET). I think there must be a class in .NET I can use. What collection should I use?
1
2122
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 sort, but I can't figure out an easy structure for it. Requirements (in case you haven't used it): You are given 4 rows in a list view: , , , ]
2
1265
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' numbers have the same maximum frequency in the list, all those 'n' numbers are modes 2. If the maximum frequency is 1, the list does not have a mode. Understandably, this list can be potentially huge and so the list of modes can be huge. However, the number of modes in a list that contains...
1
2209
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 data pairs so that I can get the counterpart ? If I have peter then I want to know he is a manager.
0
9825
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
9672
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
10854
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
9388
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
7794
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
6981
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
5652
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
5829
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
4460
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system

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.