fastest way of storing structured data

V

Vince

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...
 
A

Alipha

Vince said:
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);
 
M

Marc Mutz

Vince said:
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
 
D

David Hilsee

Vince said:
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).
 
K

Karl Heinz Buchegger

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 );
 
C

Capstar

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
 
A

Alipha

Capstar said:
[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.
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top