473,320 Members | 1,713 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

stl::map lookup speed

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
8 6255
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
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

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

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

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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

3
by: Bart Kevelham | last post by:
Hi there, due to some compatibility issues I use char* for strings. I want to use an STL map where I use these char* as key. But somehow this doesn't seem to work. The first time I add something...
2
by: yccheok | last post by:
I have an immutable object, where I do not provide implementation on =operator. However, I am facing a problem when trying to use it with stl map. stl map requires the object to have =operator...
18
by: Jan | last post by:
Hi there, i've got an STL map with something like this ( map<string, Object*> xyz; ) What happens when I call xyz.clear()? Is only the map cleared or the map and the Objects, so that the memory...
5
by: vin b | last post by:
Hi, How would I invoke a method on a reference to an STL object (STL map in this case) In this contrived example, I want to invoke the insert() method on localmap? Thanks, Vin
2
by: Allerdyce.John | last post by:
I have a a stl map which use stl pair as the key class A; type map< pair<int, int>, A> MyMap; if I have function which add entry to the map: void func(int x, int y, MyMap& map, A& a) {...
8
by: olanglois | last post by:
Hi, I was asking myself to following question. What is better to erase an element from a STL map: calling (option #1) size_type erase(const key_type& k) or calling (option #2)
7
by: Christian Christmann | last post by:
Hi, I've profiled one of my C++ projects and figured out that the program spends a lot of time with STL map's function "find". One of my classes possesses an STL map of the structure map<...
2
by: rockkyy | last post by:
Hi all, ok here it goes.. I am going to implement a STL MAP.. say 'mapToken'..this is a GLOBAL map. This mapToken has many nodes with its keys ranging from t1,t2,t3 ....t100 . Now in...
7
by: Alexander Kotelnikov | last post by:
Hello. I faced the same problem which arose before Message-ID: <1124162913.832263.262410@g14g2000cwa.googlegroups.com>...
2
by: Rakesh Kumar | last post by:
I am encountering the following issue with STL map iterator - wrapped within a template. ( I am wrapping it withing a template since I want to hide the map implementation from the user . At a later...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.