469,579 Members | 1,157 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,579 developers. It's quick & easy.

fastest way of storing structured data

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[i].nSFID == nSFID)
return fileInfo[i].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...

Aug 30 '05 #1
6 1662

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[i].nSFID == nSFID)
return fileInfo[i].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);

Aug 30 '05 #2
Vince wrote:
CMyClass::GetKey(int nSFID)
{
for*(int*i*=*0;*i*<*nItems;*i++){
if (fileInfo[i].nSFID == nSFID)
return fileInfo[i].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

Aug 30 '05 #3
"Vince" <vs**@caramail.com> wrote in message
news:43***********************@news.free.fr...
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[i].nSFID == nSFID)
return fileInfo[i].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
Aug 30 '05 #4
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
kb******@gascad.at
Aug 31 '05 #5
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
Aug 31 '05 #6

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.

Sep 1 '05 #7

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

5 posts views Thread by Loui Mercieca | last post: by
4 posts views Thread by Dharmesh | last post: by
6 posts views Thread by Kyle Teague | last post: by
6 posts views Thread by Klaas Vantournhout | last post: by
3 posts views Thread by Mohamed Yousef | last post: by
reply views Thread by suresh191 | last post: by
4 posts views Thread by guiromero | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.