organizing elements of two sets for efficient search.

Discussion in 'C++' started by Amit, Sep 23, 2005.

  1. Amit

    Amit Guest

    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.
     
    Amit, Sep 23, 2005
    #1
    1. Advertising

  2. In article <>,
    "Amit" <> 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
     
    Howard Hinnant, Sep 24, 2005
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    3
    Views:
    300
    wes weston
    Apr 8, 2005
  2. Replies:
    3
    Views:
    267
    Asun Friere
    Jul 10, 2007
  3. Replies:
    6
    Views:
    288
  4. ErichCart ErichCart

    Python sets which support multiple same elements

    ErichCart ErichCart, May 20, 2011, in forum: Python
    Replies:
    2
    Views:
    212
    Chris Angelico
    May 20, 2011
  5. java
    Replies:
    7
    Views:
    292
Loading...

Share This Page