Problem about efficient data representation

Discussion in 'C++' started by fgh.vbn.rty@gmail.com, Jul 1, 2008.

  1. Guest

    Here's the problem. Say I have:

    vector<int> vint;
    enum {R=0, O, Y, G, B, I, V} colors;

    I know that vint always has <= 10000 elements in the range [0, 9999]
    with no repetitions.

    I want to create an object called ColoredInt taking one element from
    vint and one element from colors. There can be multiple "Red integers"
    but the same integer cannot have multiple colors.

    Next I want to create a collection of ColoredInts (say "Bundle") that
    can be something like vector<ColoredInt> or map or something like
    that.

    And finally I have a collection of Bundle objects say vector<Bundle>
    Bundles.

    The input to my program is a Bundle. I need to check if any of the
    Bundles is equivalent to the incoming Bundle. If it is then I do
    nothing and if it's not then I update my collection of Bundles.

    What's the best way to represent ColoredInt? Right now I am using
    ColoredInt as a string representing the num/color combo as "123_R" for
    instance. And I'm using set<string> for Bundle (to keep the sorted
    order during equivalence checking) but it seems very inefficient.

    Is there a more efficient representation for this type of data?
     
    , Jul 1, 2008
    #1
    1. Advertising

  2. writes:

    > Here's the problem. Say I have:
    >
    > vector<int> vint;
    > enum {R=0, O, Y, G, B, I, V} colors;
    >
    > I know that vint always has <= 10000 elements in the range [0, 9999]
    > with no repetitions.
    >
    > I want to create an object called ColoredInt taking one element from
    > vint and one element from colors. There can be multiple "Red integers"
    > but the same integer cannot have multiple colors.
    >
    > Next I want to create a collection of ColoredInts (say "Bundle") that
    > can be something like vector<ColoredInt> or map or something like
    > that.
    >
    > And finally I have a collection of Bundle objects say vector<Bundle>
    > Bundles.
    >
    > The input to my program is a Bundle. I need to check if any of the
    > Bundles is equivalent to the incoming Bundle. If it is then I do
    > nothing and if it's not then I update my collection of Bundles.
    >
    > What's the best way to represent ColoredInt? Right now I am using
    > ColoredInt as a string representing the num/color combo as "123_R" for
    > instance. And I'm using set<string> for Bundle (to keep the sorted
    > order during equivalence checking) but it seems very inefficient.
    >
    > Is there a more efficient representation for this type of data?



    If you have almost 10000 elements, then you could use a vector:

    // Here, R is the universal gas constant, so let's use namespaces.
    namespace Color {
    enum Color { Null,Red,Orange,Yellow,Green,Blue,Indigo,Violet };
    };

    typedef std::vector<Color> Bundle;
    Bundle coloredInts;
    coloredInt[vint]=Color::Red;

    Add a Null color to your enum to indicate that k is not in vint:

    coloredInt[k]=Color::Null;


    If you have much less than 10000 elements, (eg. less than 1000), then
    you could use a map instead:

    typedef std::map<int,Color> Bundle;
    Bundle coloredInts;
    coloredInt[vint]=Color::Red;

    No need then to fill integers not in vint with a Null colors, they'll
    just be absent from the map.

    Testing if two bundles are equal is easier done with
    std::vector<Color>, but it's not much harder with maps.


    Also, to optimize space in the case of std::vector<Colors>, AFAIK
    sizeof(enums)==sizeof(int), so it could be better to use typedef
    std::vector<unsigned char> Bundle; as long has you have less than
    pow(2,CHAR_BITS)-1 colors.


    --
    __Pascal Bourguignon__
     
    Pascal J. Bourguignon, Jul 1, 2008
    #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. Peter
    Replies:
    1
    Views:
    375
    Steve C. Orr [MVP, MCSD]
    Nov 9, 2004
  2. Gabriel Genellina

    Efficient format for huge amount of data

    Gabriel Genellina, Jan 20, 2004, in forum: Java
    Replies:
    21
    Views:
    822
    Alan Chen
    Jan 23, 2004
  3. John Galt
    Replies:
    4
    Views:
    533
    Chris Smith
    Feb 13, 2004
  4. Charles T.

    Binary data representation

    Charles T., Feb 4, 2004, in forum: C++
    Replies:
    11
    Views:
    817
    Charles T.
    Feb 5, 2004
  5. Kris Caselden

    Data Representation?

    Kris Caselden, Oct 12, 2003, in forum: Python
    Replies:
    4
    Views:
    299
    Peter Otten
    Oct 12, 2003
Loading...

Share This Page