By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,837 Members | 1,358 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,837 IT Pros & Developers. It's quick & easy.

stl::map lookup speed

P: n/a
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<BYTEvPix;
};
struct SeriesSink {
map<CString, ImageSinkmImages;
};
struct StudySink {
map<CString, SeriesSinkmSeries;
};
class CDatasetPixelMap {
public:
CDatasetPixelMap();
~CDatasetPixelMap();
// This contains all the pixel buffers which can be looked
up.
map<CString, StudySinkm_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

Aug 29 '06 #1
Share this Question
Share on Google+
8 Replies


P: n/a
markww wrote:
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<BYTEvPix;
};
struct SeriesSink {
map<CString, ImageSinkmImages;
};
struct StudySink {
map<CString, SeriesSinkmSeries;
};

map<CString, StudySinkm_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

Aug 29 '06 #2

P: n/a
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 wrote:
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<BYTEvPix;
};
struct SeriesSink {
map<CString, ImageSinkmImages;
};
struct StudySink {
map<CString, SeriesSinkmSeries;
};
class CDatasetPixelMap {
public:
CDatasetPixelMap();
~CDatasetPixelMap();
// This contains all the pixel buffers which can be looked
up.
map<CString, StudySinkm_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
Aug 29 '06 #3

P: n/a

Michiel.Salt...@tomtom.com wrote:
markww wrote:
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<BYTEvPix;
};
struct SeriesSink {
map<CString, ImageSinkmImages;
};
struct StudySink {
map<CString, SeriesSinkmSeries;
};

map<CString, StudySinkm_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
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

Aug 29 '06 #4

P: n/a
markww schrieb:
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<BYTEvPix;
};
struct SeriesSink {
map<CString, ImageSinkmImages;
};
struct StudySink {
map<CString, SeriesSinkmSeries;
};
[...]

You can make one map out of those:

typedef std::pair<std::pair<CString, CString>, CStringid3_t;
typedef std::vector<BYTEimage_t;

std::map<id3_t, image_tpixelMap;

Using it this way:

pixelMap[std::make_pair(std::make_pair(strStudyID,strSeries ID),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
Aug 29 '06 #5

P: n/a
Shooting schrieb:
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-lit...t.html#faq-5.4
http://www.parashift.com/c++-faq-lite/

--
Thomas
Aug 29 '06 #6

P: n/a
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.

"markww" <ma****@gmail.comwrote in message
news:11**********************@74g2000cwt.googlegro ups.com...
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<BYTEvPix;
};
struct SeriesSink {
map<CString, ImageSinkmImages;
};
struct StudySink {
map<CString, SeriesSinkmSeries;
};
class CDatasetPixelMap {
public:
CDatasetPixelMap();
~CDatasetPixelMap();
// This contains all the pixel buffers which can be looked
up.
map<CString, StudySinkm_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

Aug 29 '06 #7

P: n/a

markww wrote:
>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

Aug 29 '06 #8

P: n/a

Thomas J. Gritzan wrote:
Shooting schrieb:
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-lit...t.html#faq-5.4
http://www.parashift.com/c++-faq-lite/

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

Aug 29 '06 #9

This discussion thread is closed

Replies have been disabled for this discussion.