Performance of the std::map during a search

[mveygman]

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?

[Ian Collins]

mv******@gmail.com 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.

[Ron AF Greve]

Hi,
<mv******@gmail.comwrote in message
news:1f**********************************@c4g2000h sg.googlegroups.com...

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, stringDict;
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

[=?UTF-8?B?RXJpayBXaWtzdHLDtm0=?=]

On 2007-12-22 00:57, mv******@gmail.com 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

[mveygman]

On Dec 22, 8:46 am, Erik Wikström <[e-mail]:

On 2007-12-22 00:57, [e-mail] 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

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

[mveygman]

On Dec 21, 8:07 pm, "Ron AF Greve" <ron@localhostwrote:

Hi,

<[e-mail] in message

news:1f**********************************@c4g2000h sg.googlegroups.com...

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, stringDict;
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;
}

[Hans Bos]

<mv******@gmail.comwrote in message
news:d2**********************************@s19g2000 prg.googlegroups.com...

On Dec 21, 8:07 pm, "Ron AF Greve" <ron@localhostwrote:

>Hi,

<[e-mail] in message

news:1f**********************************@c4g2000 hsg.googlegroups.com...

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

[mveygman]

On Dec 24, 11:44 am, "Hans Bos" <[e-mail]:

<[e-mail] in message

news:d2**********************************@s19g2000 prg.googlegroups.com...

On Dec 21, 8:07 pm, "Ron AF Greve" <ron@localhostwrote:

Hi,

<[e-mail] in message

>news:1f**********************************@c4g2000 hsg.googlegroups.com...

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. :)))

[=?UTF-8?B?RXJpayBXaWtzdHLDtm0=?=]

On 2007-12-24 17:04, mv******@gmail.com wrote:

On Dec 22, 8:46 am, Erik Wikström <[e-mail]:

>On 2007-12-22 00:57, [e-mail] 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

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.

Searching a map is O(log n) while a sequential search of a map is O(n),
which means that when the number of elements is large a map should be
faster. Exactly how many elements you need to have before the map is
faster depends on a lot of things but I would guess that with 1000
elements the map is almost always faster on a modern PC. On the other
hand if the vector is sorted then it might be faster searching the
vector using lower_bound() which is also O(log n), but most other
operations will still be faster on the map.

--
Erik Wikström