Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Data Structures Question...

Reply
Thread Tools

Data Structures Question...

 
 
Saikrishna
Guest
Posts: n/a
 
      04-06-2004
Hi friends,
I am trying to choose the best possible data structure for the probelm
I am going to describe now.

I have lets say tens of thousands of numbers in file1 and tens of
thousands of numbers in another file2. file1 & file2 contents (only
numbers) can be entirely different.

Now the program should be able to read the files and give me a
difference file. Ofcourse this is a very easy implementation if I go
with primitive programming using "ifs" and "whiles".

This is what I need to do. First I need to rearrange the data in file1
in vary compact format so that my program uses as little RAM as
possible. SETS are one way of doing that.

For example if file1 contains 2,3,1,7,9,10,11,12,4,6,22 ( In reality
file1 may contain several thousand numbers) then I can rearrange them
like these sets

{1-4} // Numbers 1 to 4
{9-12} // Numbers 9 to 12
{6-7} // Numbers 6 to 7
{22} // Single number 22.

And similraly I need to rearrange contents of file2 in this format.

Now my question is the best possible method for storage of this
datastructure.
Linked Lists, Tree or others or simply use STLs? Also I will be happy
if somebody can give me an idea about the best way of doing
comparision process
between sets of file1 and file2 and produce the difference set in a
number format in a result file "file3".

Thanks,
Sai
 
Reply With Quote
 
 
 
 
Thomas Matthews
Guest
Posts: n/a
 
      04-06-2004
Saikrishna wrote:
> Hi friends,
> I am trying to choose the best possible data structure for the probelm
> I am going to describe now.
>
> I have lets say tens of thousands of numbers in file1 and tens of
> thousands of numbers in another file2. file1 & file2 contents (only
> numbers) can be entirely different.
>
> Now the program should be able to read the files and give me a
> difference file. Ofcourse this is a very easy implementation if I go
> with primitive programming using "ifs" and "whiles".
>
> This is what I need to do. First I need to rearrange the data in file1
> in vary compact format so that my program uses as little RAM as
> possible. SETS are one way of doing that.
>
> For example if file1 contains 2,3,1,7,9,10,11,12,4,6,22 ( In reality
> file1 may contain several thousand numbers) then I can rearrange them
> like these sets
>
> {1-4} // Numbers 1 to 4
> {9-12} // Numbers 9 to 12
> {6-7} // Numbers 6 to 7
> {22} // Single number 22.
>
> And similraly I need to rearrange contents of file2 in this format.
>
> Now my question is the best possible method for storage of this
> datastructure.
> Linked Lists, Tree or others or simply use STLs? Also I will be happy
> if somebody can give me an idea about the best way of doing
> comparision process
> between sets of file1 and file2 and produce the difference set in a
> number format in a result file "file3".
>
> Thanks,
> Sai


Your "sets" are also termed "runs" in a typical Merge Sort
algorithm.

This is possibly an algorithm issue, not a language issue.
My suggestion is to sort both files into a third, then
remove duplicates. Perhaps the folks in news:comp.programming
can offer better advice. Follow-ups set.

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book

 
Reply With Quote
 
 
 
 
Alexander Malkis
Guest
Posts: n/a
 
      04-06-2004
There are three DIFFerent methods to attack the problem.

The first method is to look at the implementation of the diff utility
for Linux/Unix.
The second is to look at the implemenation of the sequnce-alignment from
biological-computer-science. There they determine the best aligments of
the gene sequences and it may have smth to do with your problem.
The laziest method is to ask in some programming / algorithmics group,
since algorithms/data structures are

O F F - T O P I C

here. That means that people here are not always qualified enough to
reply. (No offence meant.)

--
Best regards,
Alex.

PS. To email me, remove "loeschedies" from the email address given.
 
Reply With Quote
 
Michael Mendelsohn
Guest
Posts: n/a
 
      04-08-2004


Thomas Matthews schrieb:
> Saikrishna wrote:
> > I am trying to choose the best possible data structure for the probelm
> > I am going to describe now.


> > For example if file1 contains 2,3,1,7,9,10,11,12,4,6,22 ( In reality
> > file1 may contain several thousand numbers) then I can rearrange them
> > like these sets
> >
> > {1-4} // Numbers 1 to 4
> > {9-12} // Numbers 9 to 12
> > {6-7} // Numbers 6 to 7
> > {22} // Single number 22.
> >
> > And similraly I need to rearrange contents of file2 in this format.
> >
> > Now my question is the best possible method for storage of this
> > datastructure.
> > Linked Lists, Tree or others or simply use STLs?


Have a look at the data structure called "discrete interval encoding
tree" or "diet"; I think that's what you're after.

See e.g. http://www.nist.gov/dads/HTML/discretintrv.html

Michael
--
Feel the stare of my burning hamster and stop smoking!
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
structures, structures and more structures (questions about nestedstructures) Alfonso Morra C Programming 11 09-24-2005 07:42 PM
Type Casting IPv4 and IPv6 structures to Generic Structures tweak C Programming 14 06-11-2004 02:43 PM
data structures in java reference learningjava Java 3 10-16-2003 07:31 AM
Data Structures help MIke Beam Java 5 10-14-2003 09:53 AM
sharing complex data structures between threads in mod_perl2 Dennis Gavrilov Perl 1 07-24-2003 07:22 AM



Advertisments