473,320 Members | 1,831 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.

organizing elements of two sets for efficient search.

Hi,
I am trying to do the following: I have two sets of integers(both are
disjoint). Based on some criteria, I choose one integer from each set
and do one computationally expensive operation using the two. Now, I do
not want to do the same operation more than once on same pair of
integers. So I was thinking of making up some kind of table of pairs of
two integers, one from each set, and checking in this table if the
operation has already been done. If yes, then I move on, and if not
then I attempt it.
Also, every now and then, I would want to remove all such pairs whose
first element is a given or whose second element is a given value. Also
if I find a new pair which is not already in the table, I would like to
insert it into the table.
For a bit more detail, the operation is linear program, and the set of
integers identify regions in N dimensional space.
So, as to be expected as N increases, the no of elements in the set
could be expected to rise exponentially.

Any suggestions, given this scenario, what might be best way in terms
of efficiency to do it. Of course, this would make sense as long as
searching through the table takes less time then solving the linear
program itself..

thanks,
--a.

Sep 23 '05 #1
1 1232
In article <11*********************@o13g2000cwo.googlegroups. com>,
"Amit" <am*********@gmail.com> wrote:
Hi,
I am trying to do the following: I have two sets of integers(both are
disjoint). Based on some criteria, I choose one integer from each set
and do one computationally expensive operation using the two. Now, I do
not want to do the same operation more than once on same pair of
integers. So I was thinking of making up some kind of table of pairs of
two integers, one from each set, and checking in this table if the
operation has already been done. If yes, then I move on, and if not
then I attempt it.
Also, every now and then, I would want to remove all such pairs whose
first element is a given or whose second element is a given value. Also
if I find a new pair which is not already in the table, I would like to
insert it into the table.
For a bit more detail, the operation is linear program, and the set of
integers identify regions in N dimensional space.
So, as to be expected as N increases, the no of elements in the set
could be expected to rise exponentially.

Any suggestions, given this scenario, what might be best way in terms
of efficiency to do it. Of course, this would make sense as long as
searching through the table takes less time then solving the linear
program itself..


Instead of a table, how about a std::set<pair<int, int> > or perhaps a
std::map<pair<int, int>, result>. If your pair<int, int> is reversible
(i.e. pair(x,y) == pair(y,x)) you could write a custom comparison
operator to reflect that.

The removal operation might be problematic if pair(x,y) != pair(y,x) for
searching on the second element of the pair. If the search domain is
large enough, and the search speed important enough, you could set up a
secondary map<int, map<pair<int, int>, result>::iterator> to help you
quickly find pairs that have a 'y' value. Or perhaps:

typedef list<pair<pair<int, int>, result> Db;
Db container; // unsorted
map<pair<pair<int, int>, Db::iterator> sorted_by_x_then_y;
map<pair<pair<int, int>, Db::iterator> sorted_by_y_then_x;

or some variation thereof. I'm not pretending to have offered a
completely thought out solution, just throwing out some possibilities in
case it helps.

-Howard
Sep 23 '05 #2

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

Similar topics

24
by: superprad | last post by:
Is there an easy way to grab the Unique elements from a list? For Example: data = what I am looking for is the unique elements 0.4 and 0.9 with their index from the list. Probably something...
3
by: Jamie | last post by:
Hi, Thanks for the excellent answer to my last question! One more: Does anyone have a method they follow for organizing stylesheets themselves? They seem like they can get bloated and hard to...
1
by: Andrea | last post by:
Hi All, I am looking for SOM running under WIN32 and Microsoft Visual Studio 6.0. Can anybody help me? Andrea p.s. I apologize for cross-posting, but I have to solve this problem quickly :|
4
by: omidmottaghi | last post by:
I need to disable/enable form elements in my form. the code i was developed works fine in FF, but in IE, its behaviour is very strange!! in the form, we have a lot of checkboxes, all of them...
10
by: Rada Chirkova | last post by:
Hi, at NC State University, my students and I are working on a project called "self-organizing databases," please see description below. I would like to use an open-source database system for...
2
by: Paminu | last post by:
I have a Linked-List and would like to create pointers to elements in this list. e.g I would like two pointers that point to each of their elements in the Linked-List. But there should always be...
12
by: Ju Hui | last post by:
I want to remove about 50000 elements from a list,which has 100000 elements. sample code like below: >>> a=range(10) >>> b=range(4) >>> for x in b: .... a.remove(x) .... >>> a
6
by: happyhondje | last post by:
Hello everyone, I've got a little issue, both programming and performance-wise. I have a set, containing objects that refer to other sets. For example, in a simple notation: (<a, b, c>, <d, e>)...
2
by: jehugaleahsa | last post by:
Hello: I have a bunch of related items that are either parents, children or not directly related to each other. In my case, I have a bunch of database tables joined with foreign keys. Another...
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...
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)...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
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.