Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Performance of the std::map during a search

Reply
Thread Tools

Performance of the std::map during a search

 
 
mveygman@gmail.com
Guest
Posts: n/a
 
      12-21-2007
Hi,

I am writing code that is using std::map and having a bit of an issue
with its performance.

It appears that the std::map is significantly slower searching for an
element then a sequential search in a vector.

Has anyone run into this before?

 
Reply With Quote
 
 
 
 
Ian Collins
Guest
Posts: n/a
 
      12-22-2007
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:
> Hi,
>
> I am writing code that is using std::map and having a bit of an issue
> with its performance.
>
> It appears that the std::map is significantly slower searching for an
> element then a sequential search in a vector.
>

The elements in a map are sorted on insertion, what are you attempting
to do?

--
Ian Collins.
 
Reply With Quote
 
 
 
 
Ron AF Greve
Guest
Posts: n/a
 
      12-22-2007
Hi,


<(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> Hi,
>
> I am writing code that is using std::map and having a bit of an issue
> with its performance.
>
> It appears that the std::map is significantly slower searching for an
> element then a sequential search in a vector.
>
> Has anyone run into this before?
>


Do you use map.find ? Otherwise post some code.

e.g.

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main(){
map<string, string> Dict;
Dict[ "boek" ] = "book";
Dict[ "winkel" ] = "shop";

map<string,string>::iterator Found = Dict.find( "boek" );
if( Found != Dict.end() )
{

cout << Found->first << " translates to " << Found->second << " (or
vice versa) " << endl;

}
else
{
cout << "No such word" << endl;
}
return 0;
}





Regards, Ron AF Greve

http://www.InformationSuperHighway.eu


 
Reply With Quote
 
Erik Wikström
Guest
Posts: n/a
 
      12-22-2007
On 2007-12-22 00:57, (E-Mail Removed) wrote:
> Hi,
>
> I am writing code that is using std::map and having a bit of an issue
> with its performance.
>
> It appears that the std::map is significantly slower searching for an
> element then a sequential search in a vector.


For small collections that might be true, but for larger sets map should
be faster (if used correctly), unless perhaps if the vector is sorted
and you use a binary search.

--
Erik Wikström
 
Reply With Quote
 
mveygman@gmail.com
Guest
Posts: n/a
 
      12-24-2007
On Dec 21, 7:01 pm, Ian Collins <(E-Mail Removed)> wrote:
> (E-Mail Removed) wrote:
> > Hi,

>
> > I am writing code that is using std::map and having a bit of an issue
> > with its performance.

>
> > It appears that the std::map is significantly slower searching for an
> > element then a sequential search in a vector.

>
> The elements in a map are sorted on insertion, what are you attempting
> to do?
>
> --
> Ian Collins.


I am attempting to do the following:

insert element into the map

find element in the map.

The elements for the test that I have done were inserted in sequential
order and the vector was then randomly shuffled.

In the real world code the element insertion into the map is not
necessarily ordered.
 
Reply With Quote
 
mveygman@gmail.com
Guest
Posts: n/a
 
      12-24-2007
On Dec 22, 8:46 am, Erik Wikstrm <(E-Mail Removed)> wrote:
> On 2007-12-22 00:57, (E-Mail Removed) wrote:
>
> > Hi,

>
> > I am writing code that is using std::map and having a bit of an issue
> > with its performance.

>
> > It appears that the std::map is significantly slower searching for an
> > element then a sequential search in a vector.

>
> For small collections that might be true, but for larger sets map should
> be faster (if used correctly), unless perhaps if the vector is sorted
> and you use a binary search.
>
> --
> Erik Wikstrm



Operating key word being "should".

The assumption that I went in with was that this was the case and
worst case scenario would be that serial search of the vector and
serial search of the map would be on par for time. They are not even
close.

Regards,

Mikhail
 
Reply With Quote
 
mveygman@gmail.com
Guest
Posts: n/a
 
      12-24-2007
On Dec 21, 8:07 pm, "Ron AF Greve" <ron@localhost> wrote:
> Hi,
>
> <(E-Mail Removed)> wrote in message
>
> news:(E-Mail Removed)...
>
> > Hi,

>
> > I am writing code that is using std::map and having a bit of an issue
> > with its performance.

>
> > It appears that the std::map is significantly slower searching for an
> > element then a sequential search in a vector.

>
> > Has anyone run into this before?

>
> Do you use map.find ? Otherwise post some code.
>
> e.g.
>
> #include <iostream>
> #include <string>
> #include <map>
> using namespace std;
>
> int main(){
> map<string, string> Dict;
> Dict[ "boek" ] = "book";
> Dict[ "winkel" ] = "shop";
>
> map<string,string>::iterator Found = Dict.find( "boek" );
> if( Found != Dict.end() )
> {
>
> cout << Found->first << " translates to " << Found->second << " (or
> vice versa) " << endl;
>
> }
> else
> {
> cout << "No such word" << endl;
> }
> return 0;
>
> }
>
> Regards, Ron AF Greve
>
> http://www.InformationSuperHighway.eu




Here is the test code:

#include <map>
#include <vector>
#include <iostream>
#include <ostream>
#include <sys/time.h> /* gettimeofday */

unsigned long get_current_time()
{
struct timeval tv;
long usec;
gettimeofday (&tv, NULL);
usec = tv.tv_sec * 1000000;
usec += tv.tv_usec;
return usec;
}

int main(int argc, char **argv)
{
std::map< unsigned int, unsigned int > test_map;
std::vector< unsigned int > test_vector;

std::cout << "Setting up the test" << std::endl;

for (unsigned int i=0; i < 1000000; ++i)
{
test_map[i]=i;
test_vector.push_back(i);
}
std::random_shuffle(test_vector.begin(), test_vector.end());

time_t seed = time(NULL);

srand(seed);
unsigned long vec_start = get_current_time();
for(unsigned int i=0; i < 500000; ++i)
{
unsigned int value_to_find = rand() % 1000000;
std::vector< unsigned int >::const_iterator end_itr =
test_vector.end();
std::vector< unsigned int >::const_iterator itr =
test_vector.begin();
for( ; itr == end_itr ; ++itr )
{
if( *itr == value_to_find )
{
break;
}
}
}
unsigned long vec_end = get_current_time();

srand(seed);
unsigned long map_start = get_current_time();
for(unsigned int i=0; i < 500000; ++i)
{
unsigned int value_to_find = rand() % 1000000;
std::map< unsigned int, unsigned int >::iterator itr =
test_map.find(value_to_find);
}
unsigned long map_end = get_current_time();

std::cout << "Vec Test took " << (vec_end - vec_start) << "
microseconds. Map test took " << (map_end - map_start) << "
microseconds." << std::endl;
}
 
Reply With Quote
 
Hans Bos
Guest
Posts: n/a
 
      12-24-2007

<(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> On Dec 21, 8:07 pm, "Ron AF Greve" <ron@localhost> wrote:
>> Hi,
>>
>> <(E-Mail Removed)> wrote in message
>>
>> news:(E-Mail Removed)...
>>
>> > Hi,

>>
>> > I am writing code that is using std::map and having a bit of an issue
>> > with its performance.

>>
>> > It appears that the std::map is significantly slower searching for an
>> > element then a sequential search in a vector.

>>

> Here is the test code:
>

....
> int main(int argc, char **argv)
> {
> std::map< unsigned int, unsigned int > test_map;
> std::vector< unsigned int > test_vector;
>
> std::cout << "Setting up the test" << std::endl;
>
> for (unsigned int i=0; i < 1000000; ++i)
> {
> test_map[i]=i;
> test_vector.push_back(i);
> }
> std::random_shuffle(test_vector.begin(), test_vector.end());
>
> time_t seed = time(NULL);
>
> srand(seed);
> unsigned long vec_start = get_current_time();
> for(unsigned int i=0; i < 500000; ++i)
> {
> unsigned int value_to_find = rand() % 1000000;
> std::vector< unsigned int >::const_iterator end_itr =
> test_vector.end();
> std::vector< unsigned int >::const_iterator itr =
> test_vector.begin();
> for( ; itr == end_itr ; ++itr )


Since itr == end_itr is always false, the loop always exists immediatly, so you
don't search the vector at all.
This should be itr != end.
If I change this, the vector version takes a lot more time .

> {
> if( *itr == value_to_find )
> {
> break;
> }
> }
> }
> unsigned long vec_end = get_current_time();
>
> srand(seed);
> unsigned long map_start = get_current_time();
> for(unsigned int i=0; i < 500000; ++i)
> {
> unsigned int value_to_find = rand() % 1000000;
> std::map< unsigned int, unsigned int >::iterator itr =
> test_map.find(value_to_find);
> }
> unsigned long map_end = get_current_time();
>
> std::cout << "Vec Test took " << (vec_end - vec_start) << "
> microseconds. Map test took " << (map_end - map_start) << "
> microseconds." << std::endl;
> }


 
Reply With Quote
 
mveygman@gmail.com
Guest
Posts: n/a
 
      12-24-2007
On Dec 24, 11:44 am, "Hans Bos" <(E-Mail Removed)> wrote:
> <(E-Mail Removed)> wrote in message
>
> news:(E-Mail Removed)...
>
>
>
> > On Dec 21, 8:07 pm, "Ron AF Greve" <ron@localhost> wrote:
> >> Hi,

>
> >> <(E-Mail Removed)> wrote in message

>
> >>news:(E-Mail Removed)...

>
> >> > Hi,

>
> >> > I am writing code that is using std::map and having a bit of an issue
> >> > with its performance.

>
> >> > It appears that the std::map is significantly slower searching for an
> >> > element then a sequential search in a vector.

>
> > Here is the test code:

>
> ...
> > int main(int argc, char **argv)
> > {
> > std::map< unsigned int, unsigned int > test_map;
> > std::vector< unsigned int > test_vector;

>
> > std::cout << "Setting up the test" << std::endl;

>
> > for (unsigned int i=0; i < 1000000; ++i)
> > {
> > test_map[i]=i;
> > test_vector.push_back(i);
> > }
> > std::random_shuffle(test_vector.begin(), test_vector.end());

>
> > time_t seed = time(NULL);

>
> > srand(seed);
> > unsigned long vec_start = get_current_time();
> > for(unsigned int i=0; i < 500000; ++i)
> > {
> > unsigned int value_to_find = rand() % 1000000;
> > std::vector< unsigned int >::const_iterator end_itr =
> > test_vector.end();
> > std::vector< unsigned int >::const_iterator itr =
> > test_vector.begin();
> > for( ; itr == end_itr ; ++itr )

>
> Since itr == end_itr is always false, the loop always exists immediatly, so you
> don't search the vector at all.
> This should be itr != end.
> If I change this, the vector version takes a lot more time .
>
> > {
> > if( *itr == value_to_find )
> > {
> > break;
> > }
> > }
> > }
> > unsigned long vec_end = get_current_time();

>
> > srand(seed);
> > unsigned long map_start = get_current_time();
> > for(unsigned int i=0; i < 500000; ++i)
> > {
> > unsigned int value_to_find = rand() % 1000000;
> > std::map< unsigned int, unsigned int >::iterator itr =
> > test_map.find(value_to_find);
> > }
> > unsigned long map_end = get_current_time();

>
> > std::cout << "Vec Test took " << (vec_end - vec_start) << "
> > microseconds. Map test took " << (map_end - map_start) << "
> > microseconds." << std::endl;
> > }



That would explain everyting. ))
 
Reply With Quote
 
Ian Collins
Guest
Posts: n/a
 
      12-24-2007
(E-Mail Removed) wrote:
> On Dec 21, 7:01 pm, Ian Collins <(E-Mail Removed)> wrote:
>> (E-Mail Removed) wrote:
>>> Hi,
>>> I am writing code that is using std::map and having a bit of an issue
>>> with its performance.
>>> It appears that the std::map is significantly slower searching for an
>>> element then a sequential search in a vector.

>> The elements in a map are sorted on insertion, what are you attempting
>> to do?
>>

*Please* don't quote signatures.
>
> I am attempting to do the following:
>
> insert element into the map
>
> find element in the map.
>

How?

> The elements for the test that I have done were inserted in sequential
> order and the vector was then randomly shuffled.
>
> In the real world code the element insertion into the map is not
> necessarily ordered.


Then your implementation of std::map is broken.

--
Ian Collins.
 
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
Warning during generating classes through WSIMPORT & Error during xmlvalidation traveller Java 0 01-08-2008 07:00 AM
Does numarray search for blas and lapack during installation? Edward C. Jones Python 1 04-23-2005 08:16 PM
search within a search within a search - looking for better way...my script times out Abby Lee ASP General 5 08-02-2004 04:01 PM
Datagrid not updated during delete, but updated during insert and update Dmitry Korolyov ASP .Net Datagrid Control 0 09-22-2003 10:57 AM



Advertisments