stl::map lookup speed

[markww]

Hi,

This is a continuation of a dead post. I need to make a pixel map where
I can store pixel data for multiple images. Multiple windows in my app
may render the same image, so I want to keep one copy of the pixel data
and that's it (rather than multiple copies). Every image has a unique
StudyID, SeriesID, and then ImageID. So, I created a std::map that
looks like this:

struct ImageSink {
vector<BYTE> vPix;
};
struct SeriesSink {
map<CString, ImageSink> mImages;
};
struct StudySink {
map<CString, SeriesSink> mSeries;
};


class CDatasetPixelMap {


public:
CDatasetPixelMap();
~CDatasetPixelMap();


// This contains all the pixel buffers which can be looked
up.
map<CString, StudySink> m_DatasetPixelMap;


vector<BYTE> *GetPixelPointer(id,id,id);
}


Now I can get a pointer to the pixel data like:


vector<BYTE> *CDatasetPixelMap::GetPixelPointer(id, id, id)
{
return
&m_DatasetPixelMap[strStudyID].mSeries[strSeriesID].mImages[strImgID].vPix;

}


Is that complelety ridiculous? I'm worried about lookup speed (finding
the appropriate pixel buffer in the map with the 3 keys). But that
should be pretty fast right? Any ideas if this would be terribly slow?

Thanks,
Mark

 

[Michiel.Salters]

Hi,

This is a continuation of a dead post. I need to make a pixel map where
I can store pixel data for multiple images. Multiple windows in my app
may render the same image, so I want to keep one copy of the pixel data
and that's it (rather than multiple copies). Every image has a unique
StudyID, SeriesID, and then ImageID. So, I created a std::map that
looks like this:

struct ImageSink {
vector<BYTE> vPix;
};
struct SeriesSink {
map<CString, ImageSink> mImages;
};
struct StudySink {
map<CString, SeriesSink> mSeries;
};

map<CString, StudySink> m_DatasetPixelMap;

Is that complelety ridiculous? I'm worried about lookup speed (finding
the appropriate pixel buffer in the map with the 3 keys). But that
should be pretty fast right? Any ideas if this would be terribly slow?

Don't do it for over and over for every pixel in an Image. Given the
three
CString objects, you'll be doing O(log(N1*N2*N3)) comparisons where
Nx is the size of the x'th map. I.e. you're looking at roughly 3 to 30
string comparisons. A lot if that's per-pixel overhead, not a lot if
you
then do a million pixel ops on that single image.

Regards,
Michiel Salters

 

[Shooting]

Your code is too complex, the previous one is ok. It cost log time to
look up an item in the map because it is implemented by binary tree. If
your data scale is very large, you'd better not use so many map.
Considering the hash_map or the boost muti array

 

[markww]

Don't do it for over and over for every pixel in an Image. Given the
three
CString objects, you'll be doing O(log(N1*N2*N3)) comparisons where
Nx is the size of the x'th map. I.e. you're looking at roughly 3 to 30
string comparisons. A lot if that's per-pixel overhead, not a lot if
you
then do a million pixel ops on that single image.

Regards,
Michiel Salters

Hi Michiel,

I'd expect to use it like this:

vector<BYTE> *pvPix =
&m_DatasetPixelMap[strStudyID].mSeries[strSeriesID].mImages[strImgID].vPix;

for (int y = 0; y < cy; y++)
for (int x = 0; x < cx; x++) {
pvPix[y * cx + x] = 255; // Some per pixel operation using the
retrieved pointer.
}
// Done with pixel buffer, might go lookup another image to do same
operation on now.

As long as I retrieve the pointer to the buffer once for each image, it
should get around all the time consumption nastiness yeah?

Thanks

 

[Thomas J. Gritzan]

Hi,

This is a continuation of a dead post. I need to make a pixel map where
I can store pixel data for multiple images. Multiple windows in my app
may render the same image, so I want to keep one copy of the pixel data
and that's it (rather than multiple copies). Every image has a unique
StudyID, SeriesID, and then ImageID. So, I created a std::map that
looks like this:

struct ImageSink {
vector<BYTE> vPix;
};
struct SeriesSink {
map<CString, ImageSink> mImages;
};
struct StudySink {
map<CString, SeriesSink> mSeries;
};

[...]

You can make one map out of those:

typedef std:air<std:air<CString, CString>, CString> id3_t;
typedef std::vector<BYTE> image_t;

std::map<id3_t, image_t> pixelMap;

Using it this way:

pixelMap[std::make_pair(std::make_pair(strStudyID,strSeriesID),strImgID)]

Is that complelety ridiculous? I'm worried about lookup speed (finding
the appropriate pixel buffer in the map with the 3 keys). But that
should be pretty fast right? Any ideas if this would be terribly slow?

map-lookup is pretty fast. But you should consider a single integer index
instead of three strings.

 

[Thomas J. Gritzan]

Your code is too complex, the previous one is ok. It cost log time to

[...]

You are new to this group, aren't you?

Please don't top post here. The FAQ might be usefull:

http://www.parashift.com/c++-faq-lite/how-to-post.html#faq-5.4
http://www.parashift.com/c++-faq-lite/

 

[B.C.]

If I were you, and of course, given that there is time, I would experiment
with different solutions. Looking up stuff based on strings is a basic
computing operation. If you don't have a lot of time there are tones of
books about searching. Just take a look at Art of computer programming
volume 3 by Donald Knuth. It is about searching and sorting. See what
methods are recommened as fastest (given the domain values of your ids) for
searching and then find and use the corresponding implementation.

 

[BigBrian]

I'm worried about lookup speed (finding
the appropriate pixel buffer in the map with the 3 keys). But that
should be pretty fast right? Any ideas if this would be terribly slow?

Thanks,
Mark

Why should you have to ask us whether or not it's slow? What are your
requirements? Just measure it for yourself, and see if it meets your
requirements.

-Brian

 

[Shooting]

Your code is too complex, the previous one is ok. It cost log time to

[...]

You are new to this group, aren't you?

Please don't top post here. The FAQ might be usefull:

http://www.parashift.com/c++-faq-lite/how-to-post.html#faq-5.4
http://www.parashift.com/c++-faq-lite/

Yeah , sorry for that. I'll pay attention to that