Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > fastest way of storing structured data

Reply
Thread Tools

fastest way of storing structured data

 
 
Vince
Guest
Posts: n/a
 
      08-30-2005
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...





 
Reply With Quote
 
 
 
 
Alipha
Guest
Posts: n/a
 
      08-30-2005

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:airs, which makes the
initialization a little more awkward:

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

std::map<int, TFileInfo> mymap(init, init + 20);

 
Reply With Quote
 
 
 
 
Marc Mutz
Guest
Posts: n/a
 
      08-30-2005
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

 
Reply With Quote
 
David Hilsee
Guest
Posts: n/a
 
      08-30-2005
"Vince" <(E-Mail Removed)> wrote in message
news:4314a2c4$0$27050$(E-Mail Removed)...
> 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


 
Reply With Quote
 
Karl Heinz Buchegger
Guest
Posts: n/a
 
      08-31-2005
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
http://www.velocityreviews.com/forums/(E-Mail Removed)
 
Reply With Quote
 
Capstar
Guest
Posts: n/a
 
      08-31-2005
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
 
Reply With Quote
 
Alipha
Guest
Posts: n/a
 
      09-01-2005

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.

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Best way to store structured data achalk C++ 13 12-30-2010 09:02 AM
transmitting raw data vs. tree-structured data Max You Ruby 2 06-19-2010 09:06 PM
Best way to display and administer semi-structured data. single threaded ASP .Net Web Controls 1 06-17-2005 01:05 AM
Fastest 5 mp Digital Camera ? Fastest 4 mp Digital Camera? photoguysept102004@yahoo.com Digital Photography 6 10-28-2004 11:33 AM
Storing structured types in request Dharmesh ASP .Net 4 07-29-2004 04:51 PM



Advertisments