fastest way of storing structured data

Discussion in 'C++' started by Vince, Aug 30, 2005.

  1. Vince

    Vince Guest

    Hi,

    I am working on a project involving contactless card and to read or
    write into these cards we need some parameters (Key to use for instance).
    My problem is to store these parameters in the most efficient way.

    I was thinking first in a c manner as a struct array like this :


    struct TFileInfo
    {
    int nSFID, // Short file ID
    int nLID, // Long File ID
    int nKey
    };


    // not sure of the syntax, it's been a long time I haven't used it
    TFileInfo fileInfo[] =
    {
    { 0x17, 0x3127, 0x0E },
    { 0x18, 0x3128, 0x08 },
    };


    and after I need to be able to get the values associated to nSFID.
    ex :
    CMyClass::GetKey(int nSFID)
    {
    for (int i = 0; i < nItems; i++){
    if (fileInfo.nSFID == nSFID)
    return fileInfo.nKey
    }
    }


    Or another solution would be to use a std::map<int, TFileInFo>
    but I am concerned about performance. Besides I don't find the
    initialization very elegant

    std::map<int, TFileInfo> fileInfo;

    TFileInfo stFileInfo;

    stFileInfo.nSFID = 0x17;
    stFileInfo.nLID = 0x3127;
    stFileInfo.nKey = 0x0E;
    fileInfo[0x17] = stFileInfo;

    stFileInfo.nSFID = 0x18;
    stFileInfo.nLID = 0x3128;
    stFileInfo.nKey = 0x0E;
    fileInfo[0x17] = stFileInfo;



    I must add that my numbers of items will be 20 max.


    If someone could inform me about this performance problem...
     
    Vince, Aug 30, 2005
    #1
    1. Advertising

  2. Vince

    Alipha Guest

    Vince wrote:
    > Hi,
    >
    > I am working on a project involving contactless card and to read or
    > write into these cards we need some parameters (Key to use for instance).
    > My problem is to store these parameters in the most efficient way.
    >
    > I was thinking first in a c manner as a struct array like this :
    >
    >
    > struct TFileInfo
    > {
    > int nSFID, // Short file ID
    > int nLID, // Long File ID
    > int nKey
    > };
    >
    >
    > // not sure of the syntax, it's been a long time I haven't used it
    > TFileInfo fileInfo[] =
    > {
    > { 0x17, 0x3127, 0x0E },
    > { 0x18, 0x3128, 0x08 },
    > };
    >
    >
    > and after I need to be able to get the values associated to nSFID.
    > ex :
    > CMyClass::GetKey(int nSFID)
    > {
    > for (int i = 0; i < nItems; i++){
    > if (fileInfo.nSFID == nSFID)
    > return fileInfo.nKey
    > }
    > }
    >


    this will take an average of 10 comparisions to find the value, if
    there's 20 elements. A std::map will take an average of 4 comparisions.
    And so, which is more efficient? A linear search is O(n) while a search
    on a std::map is O(log n).

    >
    > Or another solution would be to use a std::map<int, TFileInFo>
    > but I am concerned about performance. Besides I don't find the
    > initialization very elegant
    >
    > std::map<int, TFileInfo> fileInfo;
    >
    > TFileInfo stFileInfo;
    >
    > stFileInfo.nSFID = 0x17;
    > stFileInfo.nLID = 0x3127;
    > stFileInfo.nKey = 0x0E;
    > fileInfo[0x17] = stFileInfo;
    >
    > stFileInfo.nSFID = 0x18;
    > stFileInfo.nLID = 0x3128;
    > stFileInfo.nKey = 0x0E;
    > fileInfo[0x17] = stFileInfo;
    >
    >
    >
    > I must add that my numbers of items will be 20 max.
    >
    >
    > If someone could inform me about this performance problem...




    you might want to consider a std::set instead, since the key is
    embedded into the TFileInfo struct. Then give your struct a an
    operator<, or pass a functor as the 2nd template argument to std::set.

    In any case, you can initialize a std::set or std::map with an array:

    std::set<TFileInfo> myset(fileInfo, fileInfo + 20); // where fileInfo
    is the array you have above

    A std::map expects iterators to std::pairs, which makes the
    initialization a little more awkward:

    // you must give TFileInfo a constructor
    std::pair<int, TFileInfo> init[] =
    { std::make_pair(0x17, TFileInfo(0x17, 0x3127, 0x0E)),
    std::make_pair(... , TFileInfo( ... )),
    ...
    };

    std::map<int, TFileInfo> mymap(init, init + 20);
     
    Alipha, Aug 30, 2005
    #2
    1. Advertising

  3. Vince

    Marc Mutz Guest

    Vince wrote:

    > CMyClass::GetKey(int nSFID)
    > {
    > for (int i = 0; i < nItems; i++){
    > if (fileInfo.nSFID == nSFID)
    > return fileInfo.nKey
    > }
    > }
    >


    If you sort your array 'fileInfo' by the nSFID field, then
    you can have O(logN) lookup by using std::lower_bound().

    There's nothing wrong per se with POD arrays, esp. if they
    can be const, and thus be put into read-only memory.

    Marc
     
    Marc Mutz, Aug 30, 2005
    #3
  4. Vince

    David Hilsee Guest

    "Vince" <> wrote in message
    news:4314a2c4$0$27050$...
    > Hi,
    >
    > I am working on a project involving contactless card and to read or
    > write into these cards we need some parameters (Key to use for instance).
    > My problem is to store these parameters in the most efficient way.
    >
    > I was thinking first in a c manner as a struct array like this :
    >
    >
    > struct TFileInfo
    > {
    > int nSFID, // Short file ID
    > int nLID, // Long File ID
    > int nKey
    > };
    >
    >
    > // not sure of the syntax, it's been a long time I haven't used it
    > TFileInfo fileInfo[] =
    > {
    > { 0x17, 0x3127, 0x0E },
    > { 0x18, 0x3128, 0x08 },
    > };
    >
    >
    > and after I need to be able to get the values associated to nSFID.
    > ex :
    > CMyClass::GetKey(int nSFID)
    > {
    > for (int i = 0; i < nItems; i++){
    > if (fileInfo.nSFID == nSFID)
    > return fileInfo.nKey
    > }
    > }
    >
    >
    > Or another solution would be to use a std::map<int, TFileInFo>
    > but I am concerned about performance. Besides I don't find the
    > initialization very elegant
    >
    > std::map<int, TFileInfo> fileInfo;
    >
    > TFileInfo stFileInfo;
    >
    > stFileInfo.nSFID = 0x17;
    > stFileInfo.nLID = 0x3127;
    > stFileInfo.nKey = 0x0E;
    > fileInfo[0x17] = stFileInfo;
    >
    > stFileInfo.nSFID = 0x18;
    > stFileInfo.nLID = 0x3128;
    > stFileInfo.nKey = 0x0E;
    > fileInfo[0x17] = stFileInfo;
    >
    >
    >
    > I must add that my numbers of items will be 20 max.
    >
    >
    > If someone could inform me about this performance problem...


    Performance questions are best answered by performance tests. Since there's
    only 20 items, I'd bet that the difference between the array and std::map
    wouldn't be significant unless your application performs this lookup very
    frequently.

    As Marc pointed out, sorting the entries and using a search routine is
    another option. Also, if nSFID has a limited range, you could create an
    array that can be indexed by the nSFID, giving you O(1) lookup time (but
    possibly requiring a little more memory).

    --
    David Hilsee
     
    David Hilsee, Aug 31, 2005
    #4
  5. Vince wrote:
    >


    Others have already talked about your 'performance' issue.

    But ...

    > Besides I don't find the
    > initialization very elegant
    >
    > std::map<int, TFileInfo> fileInfo;
    >
    > TFileInfo stFileInfo;
    >
    > stFileInfo.nSFID = 0x17;
    > stFileInfo.nLID = 0x3127;
    > stFileInfo.nKey = 0x0E;
    > fileInfo[0x17] = stFileInfo;
    >
    > stFileInfo.nSFID = 0x18;
    > stFileInfo.nLID = 0x3128;
    > stFileInfo.nKey = 0x0E;
    > fileInfo[0x17] = stFileInfo;
    >


    .... this can easily be cured.
    Just provide your struct with a constructor:

    struct TFileInfo
    {
    TFileInfo( int SFID, int LID, int Key )
    : nSFID( SFID ), nLID( LID ), nKey( Key )
    {}

    int nSFID, // Short file ID
    int nLID, // Long File ID
    int nKey
    };

    and now you can ceasily create objects and initialize them
    on the fly:

    fileInfo[0x17] = TFileInfo( 0x17, 0x3127, 0x0E );
    fileInfo[0x18] = TFileInfo( 0x18, 0x3128, 0x0E );

    --
    Karl Heinz Buchegger
     
    Karl Heinz Buchegger, Aug 31, 2005
    #5
  6. Vince

    Capstar Guest

    Alipha wrote:
    > Vince wrote:
    >
    >>Hi,
    >>
    >>I am working on a project involving contactless card and to read or
    >>write into these cards we need some parameters (Key to use for instance).
    >>My problem is to store these parameters in the most efficient way.
    >>
    >>I was thinking first in a c manner as a struct array like this :
    >>
    >>
    >>struct TFileInfo
    >>{
    >> int nSFID, // Short file ID
    >> int nLID, // Long File ID
    >> int nKey
    >>};
    >>
    >>


    >
    >
    >
    >
    > you might want to consider a std::set instead, since the key is
    > embedded into the TFileInfo struct. Then give your struct a an
    > operator<, or pass a functor as the 2nd template argument to std::set.


    But how would you get the TFileInfo structure you're looking for? If I
    want to use set::find(), I need to pass a struct TFileInfo, but I just
    have a nSFID.

    Mark
     
    Capstar, Aug 31, 2005
    #6
  7. Vince

    Alipha Guest

    Capstar wrote:
    > [snip]
    >
    > But how would you get the TFileInfo structure you're looking for? If I
    > want to use set::find(), I need to pass a struct TFileInfo, but I just
    > have a nSFID.
    >
    > Mark


    create a TFileInfo with the nSFID field set to what you want then. If
    you give your struct a one-argument ctor (probably explicit), then it
    would be easy to do myset.find(TFileInfo(0x17)). Of course, you lose
    the ability to initialize your struct with { } initializers.
     
    Alipha, Sep 1, 2005
    #7
    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. Dharmesh

    Storing structured types in request

    Dharmesh, Jul 29, 2004, in forum: ASP .Net
    Replies:
    4
    Views:
    417
    Dharmesh
    Jul 29, 2004
  2. Gummy
    Replies:
    2
    Views:
    367
    Gummy
    Feb 8, 2007
  3. Replies:
    11
    Views:
    716
    Ian Collins
    Aug 8, 2007
  4. achalk
    Replies:
    13
    Views:
    1,042
    Nick Keighley
    Dec 30, 2010
  5. single threaded

    Best way to display and administer semi-structured data.

    single threaded, Jun 11, 2005, in forum: ASP .Net Web Controls
    Replies:
    1
    Views:
    131
    single threaded
    Jun 17, 2005
Loading...

Share This Page