By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
459,292 Members | 1,354 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 459,292 IT Pros & Developers. It's quick & easy.

organizing elements of two sets for efficient search.

P: n/a
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
Share this Question
Share on Google+
1 Reply


P: n/a
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 discussion thread is closed

Replies have been disabled for this discussion.