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<BYTEvPix ;
};
struct SeriesSink {
map<CString, ImageSinkmImage s;
};
struct StudySink {
map<CString, SeriesSinkmSeri es;
};


class CDatasetPixelMa p {


public:
CDatasetPixelMa p();
~CDatasetPixelM ap();


// This contains all the pixel buffers which can be looked
up.
map<CString, StudySinkm_Data setPixelMap;


vector<BYTE*Get PixelPointer(id ,id,id);
}


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


vector<BYTE*CDa tasetPixelMap:: GetPixelPointer (id, id, id)
{
return
&m_DatasetPixel Map[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@tomtom.com]

Re: stl::map lookup speed

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, ImageSinkmImage s;
};
struct StudySink {
map<CString, SeriesSinkmSeri es;
};
>
map<CString, StudySinkm_Data setPixelMap;

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]

Re: stl::map lookup speed

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, ImageSinkmImage s;
};
struct StudySink {
map<CString, SeriesSinkmSeri es;
};
>
>
class CDatasetPixelMa p {
>
>
public:
CDatasetPixelMa p();
~CDatasetPixelM ap();
>
>
// This contains all the pixel buffers which can be looked
up.
map<CString, StudySinkm_Data setPixelMap;
>
>
vector<BYTE*Get PixelPointer(id ,id,id);
}
>
>
Now I can get a pointer to the pixel data like:
>
>
vector<BYTE*CDa tasetPixelMap:: GetPixelPointer (id, id, id)
{
return
&m_DatasetPixel Map[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

[markww]

Re: stl::map lookup speed


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, ImageSinkmImage s;
};
struct StudySink {
map<CString, SeriesSinkmSeri es;
};

map<CString, StudySinkm_Data setPixelMap;

>

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*pvP ix =
&m_DatasetPixel Map[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]

Re: stl::map lookup speed

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, ImageSinkmImage s;
};
struct StudySink {
map<CString, SeriesSinkmSeri es;
};

[...]

You can make one map out of those:

typedef std::pair<std:: pair<CString, CString>, CStringid3_t;
typedef std::vector<BYT Eimage_t;

std::map<id3_t, image_tpixelMap ;

Using it this way:

pixelMap[std::make_pair( std::make_pair( strStudyID,strS eriesID),strImg ID)]

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

[Thomas J. Gritzan]

Re: stl::map lookup speed

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-lite/how-to-post.html#faq-5.4

http://www.parashift.com/c++-faq-lite/

--
Thomas

[B.C.]

Re: stl::map lookup speed

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" <markww@gmail.c omwrote in message
news:1156859709 .075958.260830@ 74g2000cwt.goog legroups.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, ImageSinkmImage s;
};
struct StudySink {
map<CString, SeriesSinkmSeri es;
};
>
>
class CDatasetPixelMa p {
>
>
public:
CDatasetPixelMa p();
~CDatasetPixelM ap();
>
>
// This contains all the pixel buffers which can be looked
up.
map<CString, StudySinkm_Data setPixelMap;
>
>
vector<BYTE*Get PixelPointer(id ,id,id);
}
>
>
Now I can get a pointer to the pixel data like:
>
>
vector<BYTE*CDa tasetPixelMap:: GetPixelPointer (id, id, id)
{
return
>

&m_DatasetPixel Map[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
>

[BigBrian]

Re: stl::map lookup speed


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

[Shooting]

Re: stl::map lookup speed


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-lite/how-to-post.html#faq-5.4

http://www.parashift.com/c++-faq-lite/

>
--
Thomas

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